Rang ciclic

Rangul ciclic al unui graf direcționat este o măsură a conectivității unui digraf propus de Eggan și Buchi [1] . Acest concept surprinde intuitiv cât de aproape este un digraf de un grafic aciclic direcționat (DAG, en:DAG) atunci când rangul ciclic al DAG este zero, în timp ce un digraf direcționat de ordin n cu bucle la fiecare vârf are rang ciclic n . Rangul ciclic al unui grafic direcționat este strâns legat de adâncimea arborelui unui grafic nedirecționat și de înălțimea de iterație a limbajelor obișnuite . Rangul ciclic și-a găsit aplicație și în calculele matrice rare (vezi Bodlaender, Gilbert, Hafsteinsson, Kloks, 1995 ) și în logica [2] .

Definiție

Rangul ciclic r ( G ) al unui digraf G  = ( V ,  E ) este definit inductiv după cum urmează

unde este digraful obținut prin îndepărtarea vârfului v și a tuturor muchiilor care încep sau se termină în v .

Adâncimea arborelui unui graf nedirecționat are o definiție foarte similară cu conectivitate nedirecționată și componente conectate în loc de conectivitate puternică și componente puternic conectate.

Istorie

Rangul ciclic a fost introdus de Eggan [1] în contextul înălțimii de iterație a limbilor obișnuite . Rangul ciclic a fost redescoperit de Aizenshtat și Liu [3] ca o generalizare a adâncimii nedirecționate a unui copac . Conceptul a fost dezvoltat încă de la începutul anilor 1980 și a fost folosit pentru a lucra cu matrici rare [4] .

Exemple

Rangul ciclic al unui graf aciclic direcționat este 0, în timp ce un digraf complet de ordin n cu o buclă la fiecare vârf are un rang ciclic de n . În plus față de aceste două cazuri, este cunoscut rangul ciclic al mai multor alte digrafe: un drum nedirecționat de ordin n care are o relație de simetrie a muchiei și nicio buclă are un rang ciclic [5] . Pentru un -tor orientat , i.e. produs direct al două contururi orientate de lungime m și n , avem și pentru m ≠ n [1] [6] .

Calculul rangului ciclic

Calcularea rangului ciclic este o sarcină dificilă. Gruber [7] a dovedit că problema de solubilitate corespunzătoare este NP-completă chiar și pentru digrafele rare cu gradul maxim 2. Vestea bună este că problema este rezolvabilă în timp pe digrafele cu gradul maxim 2 și în timp pe digrafele generale. Există un algoritm de aproximare cu un coeficient de aproximare .

Aplicații

Înălțimea iterației limbilor obișnuite

Prima aplicare a rangului ciclic a fost în teoria limbilor formale pentru a studia înălțimea de iterație a limbajului limbilor obișnuite . Eggan [1] a stabilit o relație între teoriile expresiei regulate, automatele finite și graficele direcționate . În anii următori, această relație a devenit cunoscută ca teorema lui Eggan [8] . În teoria automatelor , un automat finit nedeterminist cu c ε-tranziții (ε-NFA) este definit ca un 5 , ( Q , Σ, δ , q 0 , F ) constând din

Un cuvânt w ∈ Σ * este permis de un automat ε-NCF dacă există o cale direcționată de la o stare inițială q 0 la o stare finală din F folosind muchii de la δ , astfel încât concatenarea tuturor etichetelor de-a lungul căii produce un cuvânt w . Mulțimea tuturor cuvintelor peste Σ * acceptate de automat este limbajul acceptat de automatul A .

Când se vorbește despre proprietățile digrafelor unui automat finit nedeterminist A cu o mulțime de stări Q , se înțelege în mod firesc un digraf cu o mulțime de vârfuri Q generate de relația de tranziție.

Teorema lui Eggan : Înălțimea de iterație a unui limbaj regulat L este egală cu rangul ciclic minim dintre toate automatele finite nedeterministe cu ε-tranziții (cu tranziții goale) acceptând limbajul L.

Demonstrațiile acestei teoreme au fost date de Eggan [1] și, mai târziu, de Sakarovich [8] .

Descompunerea Cholesky pentru matrici rare

O altă aplicație a acestui concept constă în domeniul calculului cu matrice rare , și anume folosirea disecției imbricate în calcularea descompunerii Cholesky a unei matrice (simetrice) folosind un algoritm paralel. Matricea rară dată M poate fi interpretată ca matricea de adiacență a unui digraf simetric G cu n vârfuri, astfel încât elementele nenule ale matricei să corespundă unu la unu muchiilor graficului G . Dacă rangul ciclic al digrafului G nu depășește k , atunci descompunerea Cholesky a matricei M poate fi calculată în cel mult k pași pe un computer paralel cu procesoare [9] .

Vezi și

Note

  1. ↑ 1 2 3 4 5 Eggan, 1963 .
  2. ↑ Rossman, 2008 .
  3. ↑ Eisenstat, Liu, 2005 .
  4. ↑ Schreiber, 1982 .
  5. ↑ McNaughton, 1969 .
  6. ↑ Gruber, Holzer, 2008 .
  7. ↑ Gruber, 2012 .
  8. ↑ 12 Sakarovitch , 2009 .
  9. ↑ Dereniowski, Kubale, 2004 .

Literatură