Cykel rang

I grafteorin är cykelrankningen för en riktad graf ett mått på digrafanslutning som först föreslagits av Eggan och Büchi ( Eggan 1963) . Intuitivt mäter detta koncept hur nära en digraf är en riktad acyklisk graf (DAG), i den meningen att en DAG har cykelrang noll, medan en komplett digraf av ordningen n med en självslinga vid varje vertex har cykelrang n . Cykelgraden för en riktad graf är nära relaterad till träddjupet för en oriktad graf och till stjärnhöjden för ett vanligt språk . Den har också funnit användning i glesa matrisberäkningar (se Bodlaender et al. 1995 ) och logik ( Rossman 2008 ).

Definition

Cykelrangen r ( G ) för en digraf $G = (V, E)$ definieras induktivt enligt följande:

Om G är acyklisk så $är r (G) = 0$ .
Om G är starkt kopplat och E är icke-tom, då

r(G)=1+\min _{v\in V}r(Gv),\,

där

Gv

är digrafen som är resultatet av radering av vertex

v

och alla kanter som börjar eller slutar på

v

.

Om G inte är starkt ansluten, då är r ( G ) lika med den maximala cykelrangen bland alla starkt anslutna komponenter i G.

Träddjupet för en oriktad graf har en mycket liknande definition, och använder oriktad anslutning och anslutna komponenter istället för stark anslutning och starkt anslutna komponenter .

Historia

Cykelrankning introducerades av Eggan (1963) i samband med stjärnhöjden för vanliga språk . Det återupptäcktes av ( Eisenstat & Liu 2005 ) som en generalisering av oriktat träddjup , som hade utvecklats med början på 1980-talet och tillämpats på glesa matrisberäkningar ( Schreiber 1982 ).

Exempel

Cykelgraden för en riktad acyklisk graf är 0, medan en komplett digraf av ordningen n med en självslinga vid varje vertex har cykelrankningen n . Bortsett från dessa är cykelrankningen för några andra digrafer känd: den oriktade banan $P_{n}$ av ordningen n , som har en symmetrisk kantrelation och inga självslingor, har cykelrang $\lfloor \log n\rfloor$ ( McNaughton 1969) . För den riktade $(m\times n)$ -torus $T_{m,n}$ , dvs den kartesiska produkten av två riktade kretsar med längderna m och n , vi har $r(T_{n,n})=n$ och $r(T_{ m,n})=\min\{m,n\}+1$ för m ≠ n ( Eggan 1963 , Gruber & Holzer 2008) .

Beräknar cykelrankningen

Att beräkna cykelrankningen är beräkningsmässigt svårt: Gruber (2012) bevisar att motsvarande beslutsproblem är NP-komplett , även för glesa digrafer med maximal utgrad på högst 2. På den positiva sidan är problemet lösbart i tid $O(1.9129^{n})$ på digrafer med maximal utgrad på högst 2, och i tiden $O^{*}(2^{n})$ på allmänna digrafer. Det finns en approximationsalgoritm med approximationsförhållande $O((\log n)^{\frac {3}{2}})$ .

Ansökningar

Stjärnhöjd för vanliga språk

Den första tillämpningen av cykelrankning var i formell språkteori , för att studera stjärnhöjden för vanliga språk . Eggan (1963) etablerade en relation mellan teorierna om reguljära uttryck, finita automater och riktade grafer . Under de följande åren blev detta förhållande känt som Eggans sats , jfr. Sakarovitch (2009) . I automatteorin definieras en icke-deterministisk finit automat med ε-rörelser (ε-NFA) som en 5-tupel , ( Q , Σ, δ , q ₀ , F ), bestående av

en ändlig uppsättning tillstånd Q
en ändlig uppsättning ingångssymboler Σ
en uppsättning märkta kanter δ , hänvisad till som övergångsrelation : Q × (Σ ∪{ε}) × Q . Här betecknar ε det tomma ordet .
ett initialtillstånd q ∈ Q _ ₀
en uppsättning tillstånd F särskiljs som accepterande tillstånd F ⊆ Q .

₀ Ett ord w ∈ Σ ^* accepteras av ε-NFA om det finns en riktad väg från initialtillståndet q till något sluttillstånd i F med kanter från δ , så att sammanlänkningen av alla etiketter som besöks längs vägen ger ordet w . Mängden av alla ord över Σ ^* som accepteras av automaten är det språk som accepteras av automaten A .

När vi talar om digrafegenskaper hos en icke-deterministisk finit automat A med tillståndsmängd Q , adresserar vi naturligtvis digrafen med vertexuppsättning Q inducerad av dess övergångsrelation. Nu anges satsen enligt följande.

Eggans sats : Stjärnhöjden för ett reguljärt språk L är lika med den minsta cykelrangen bland alla icke-deterministiska finita automater med ε-rörelser som accepterar L .

Bevis för detta teorem ges av Eggan (1963) och på senare tid av Sakarovitch (2009) .

Cholesky faktorisering i glesa matrisberäkningar

En annan tillämpning av detta koncept ligger i glesa matrisberäkningar , nämligen för att använda kapslad dissektion för att beräkna Cholesky-faktoriseringen av en (symmetrisk) matris parallellt. En given gles $(n\times n)$ -matris M kan tolkas som närliggande matris för någon symmetrisk digraf G på n hörn, på ett sätt så att matrisens ingångar som inte är noll är i en-till-en-överensstämmelse med kanterna på G . Om cykelrankningen för digrafen G är högst k , så kan Cholesky-faktoriseringen av M beräknas i högst k steg på en parallell dator med $n$ -processorer ( Dereniowski & Kubale 2004 ).

Se även

Krets rang

Bodlaender, Hans L. ; Gilbert, John R.; Hafsteinsson, Hjálmtýr; Kloks, Ton (1995), shortest elimination tree" , of Algorithms , 18 (2): 238–255, doi : 10.1006/jagm.1995.1009 , Zbl 01818 ^{Journal and ] [} .
Dereniowski, Dariusz; Kubale, Marek (2004), "Cholesky Factorization of Matrices in Parallel and Ranking of Graphs", 5th International Conference on Parallell Processing and Applied Mathematics (PDF) , Lecture Notes on Computer Science, vol. 3019, Springer-Verlag, s. 985–992, doi : 10.1007/978-3-540-24669-5_127 , Zbl 1128.68544 , arkiverad från originalet (PDF) den 2011-07-127 .
Eggan, Lawrence C. (1963), "Transition graphs and the star-height of regular events", Michigan Mathematical Journal , 10 (4): 385–397, doi : 10.1307/mmj/1028998975 , Zbl 0173.01504 .
Eisenstat, Stanley C.; Liu, Joseph WH (2005), "Teorin om elimineringsträd för glesa osymmetriska matriser", SIAM Journal on Matrix Analysis and Applications , 26 ( 3): 686–705, doi : 10.1137/S089547980240563X .
Gruber, Hermann (2012), "Digraph Complexity Measures and Applications in Formal Language Theory" (PDF) , Discrete Mathematics & Theoretical Computer Science , 14 (2): 189–204 .
Gruber, Hermann; Holzer, Markus (2008), "Finite automata, digraph connectivity, and regular expression size" (PDF) , Proc. 35th International Colloquium on Automata, Languages and Programming , Lecture Notes on Computer Science, vol. 5126, Springer-Verlag, s. 39–50, doi : 10.1007/978-3-540-70583-3_4 .
McNaughton, Robert (1969), "The loop complexity of regular events", Information Sciences , 1 (3): 305–328, doi : 10.1016/S0020-0255(69)80016-2 .
Rossman, Benjamin (2008), "Homomorphism preservation theorems", Journal of the ACM , 55 (3): Artikel 15, doi : 10.1145/1379759.1379763 .
Sakarovitch, Jacques (2009), Elements of Automata Theory , Cambridge University Press, ISBN 0-521-84425-8
Schreiber, Robert (1982), "A new implementation of sparse Gaussian elimination" (PDF) , ACM Transactions on Mathematical Software , 8 ( 3): 256–276, doi : 10.1145/356004.356006 , arkiverad från originalet (PDF) på 2011 -06-07 , hämtad 2010-01-04 .