Cyklisk rang

Den cykliske rangering af en rettet graf er et mål for forbindelsen af en digraf foreslået af Eggan og Buchi [1] . Dette koncept fanger intuitivt, hvor tæt en digraf er på en rettet acyklisk graf (DAG, en:DAG), når DAG'ens cykliske rangorden er nul, mens en rettet digraf af orden n med sløjfer ved hvert toppunkt har cyklisk rangorden n . Den cykliske rangorden af en rettet graf er tæt forbundet med trædybden af en urettet graf og iterationshøjden af regulære sprog .. Den cykliske rang har også fundet anvendelse i sparsomme matrixberegninger (se Bodlaender, Gilbert, Hafsteinsson, Kloks, 1995 ) og logik [2] .

Definition

Den cykliske rangorden r ( G ) af en digraf G = ( V , E ) er induktivt defineret som følger

Hvis G er acyklisk, så er r ( G ) = 0 .
Hvis G er stærkt forbundet , og E ikke er tom, så

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

hvor er digrafen opnået ved at fjerne toppunktet v og alle kanter, der starter eller slutter på v .

Gv

Hvis G ikke er en stærkt forbundet komponent, så er r ( G ) lig med den maksimale cykliske rangorden blandt alle stærkt forbundne komponenter i G.

Trædybden af en urettet graf har en meget lignende definition med urettet forbindelse og forbundne komponenter i stedet for stærk forbindelse og stærkt forbundne komponenter.

Historie

Den cykliske rang blev introduceret af Eggan [1] i forbindelse med iterationshøjden af regulære sprog . Den cykliske rang blev genopdaget af Aizenshtat og Liu [3] som en generalisering af den urettede dybde af et træ . Konceptet er udviklet siden begyndelsen af 1980'erne og er blevet brugt til at arbejde med sparsomme matricer [4] .

Eksempler

Den cykliske rangorden af en rettet acyklisk graf er 0, mens en komplet digraf af orden n med en sløjfe ved hvert toppunkt har en cyklisk rangorden på n . Ud over disse to tilfælde kendes den cykliske rangorden af adskillige andre digrafer: en urettet bane af orden n , der har en kantsymmetrirelation, og ingen sløjfer har en cyklisk rangorden [5] . For en orienteret -torus , dvs. direkte produkt af to orienterede konturer af længden m og n , vi har og for m ≠ n [1] [6] . $P_{n}$ $\lfloor \log n\rfloor$ $(m\times n)$ ${\displaystyle T_{m,n))$ $r(T_{n,n})=n$ $r(T_{m,n})=\min\{m,n\}+1$

Cyklisk rangberegning

At beregne den cykliske rang er en vanskelig opgave. Gruber [7] beviste, at det tilsvarende løselighedsproblem er NP-komplet selv for sparsomme digrafer med maksimal udgrad 2. Den gode nyhed er, at problemet kan løses i tid på digrafer med maksimal udgrad 2 og i tid på generelle digrafer. Der er en tilnærmelsesalgoritme med en tilnærmelseskoefficient . $O(1,9129^{n})$ $O^{*}(2^{n})$ $O((\log n)^{\frac {3}{2)))$

Ansøgninger

Iterationshøjde af regulære sprog

Den første anvendelse af cyklisk rang var i teorien om formelle sprog for at studere iterationshøjden af sproget i regulære sprog . Eggan [1] etablerede et forhold mellem teorier om regulære udtryk, endelige automater og rettede grafer . I de efterfølgende år blev dette forhold kendt som Eggans sætning [8] . I automatteori er en ikke-deterministisk endelig automat med c ε-overgange (ε-NFA) defineret som en 5 , ( Q , Σ, δ , q 0 , F ) bestående af

endeligt sæt af tilstande Q
endeligt sæt af inputsymboler Σ (alfabet)
sæt af mærkede kanter δ , kaldet overgangsrelationer : Q × (Σ ∪{ε}) × Q . Her betyder ε den tomme streng .
begyndelsestilstand q 0 ∈ Q _
sæt af tilstande F ( absorberende tilstande ) F ⊆ Q .

Et ord w ∈ Σ * er tilladt af en ε-NCF automat, hvis der er en rettet vej fra en begyndelsestilstand q 0 til en eller anden sluttilstand fra F ved hjælp af kanter fra δ , så sammenkædning af alle etiketter langs stien giver et ord w . Mængden af alle ord over Σ * accepteret af automaten er det sprog , der accepteres af automaten A .

Når man taler om egenskaberne af digrafer af en ikke-deterministisk endelig automat A med et sæt tilstande Q , mener man naturligvis en digraf med et sæt toppunkter Q genereret af overgangsrelationen.

Eggans sætning : Iterationshøjden af et regulært sprogsprog L er lig med den mindste cykliske rangorden blandt alle ikke-deterministiske endelige automater med ε-overgange (med tomme overgange), der accepterer sproget L.

Beviser for denne teorem blev givet af Eggan [1] og senere af Sakarovich [8] .

Kolesky nedbrydning for sparsomme matricer

En anden anvendelse af dette koncept ligger inden for sparse matrix computing , nemlig at bruge nestet dissektion til at beregne Cholesky-nedbrydningen af en (symmetrisk) matrix ved hjælp af en parallel algoritme. Den givne sparsomme matrix M kan fortolkes som nabomatrixen af en eller anden symmetrisk digraf G med n hjørner, således at de ikke-nul elementer i matricen svarer en-til-en til kanterne af grafen G . Hvis den cykliske rangorden af digrafen G ikke overstiger k , så kan den Cholesky-dekomponering af matrixen M beregnes i højst k trin på en parallel computer med processorer [9] . $(n\ gange n)$ $n$

Se også

Kontur rang

Litteratur

Hans L. Bodlaender, John R. Gilbert, Hjálmtyr Hafsteinsson, Ton Kloks. Tilnærmelse af træbredde, stibredde, frontstørrelse og korteste elimineringstræ // Journal of Algorithms. - 1995. - T. 18 , no. 2 . - S. 238-255 . - doi : 10.1006/jagm.1995.1009 .
Dariusz Dereniowski, Marek Kubale. Cholesky faktorisering af matricer i parallel og rangering af grafer // 5. internationale konference om parallel bearbejdning og anvendt matematik . - Springer-Verlag, 2004. - T. 3019. - S. 985-992. — (Forelæsningsnotater om datalogi). - doi : 10.1007/978-3-540-24669-5_127 . .
Lawrence C. Eggan. Overgangsgrafer og stjernehøjden for regelmæssige begivenheder // Michigan Mathematical Journal . - 1963. - T. 10 , no. 4 . - S. 385-397 . - doi : 10.1307/mmj/1028998975 .
Stanley C. Eisenstat, Joseph W.H. Liu. Teorien om eliminationstræer for sparsomme usymmetriske matricer // SIAM Journal on Matrix Analysis and Applications. - 2005. - T. 26 , no. 3 . - S. 686-705 . - doi : 10.1137/S089547980240563X .
Hermann Gruber. Digraph kompleksitetsmål og anvendelser i formel sprogteori // Teoretisk datalogi. - 2012. - Bd. 14 . - S. 189-204 . .
Hermann Gruber, Markus Holzer. Finite automater, digrafforbindelser og regulære udtryksstørrelser //Proc. 35. internationale kollokvium om automater, sprog og programmering . - Springer-Verlag, 2008. - T. 5126. - S. 39-50. — (Forelæsningsnotater om datalogi). - doi : 10.1007/978-3-540-70583-3_4 .
Robert McNaughton. Løkkekompleksiteten af regelmæssige begivenheder // Informationsvidenskab. - 1969. - Bind 1 , udgave. 3 . - S. 305-328 . - doi : 10.1016/S0020-0255(69)80016-2 .
Benjamin Rossman. Homomorphism bevaring teoremer // Journal of the ACM . - 2008. - T. 55 , no. 3 . — C. Artikel 15 . doi : 10.1145 / 1379759.1379763 .
Jacques Sakarovitch. Elementer af automatteori. - Cambridge University Press, 2009. - ISBN 0-521-84425-8 .
Robert Schreiber. En ny implementering af sparsom gaussisk eliminering // ACM-transaktioner på matematisk software . - 1982. - T. 8 , no. 3 . - S. 256-276 . - doi : 10.1145/356004.356006 . Arkiveret fra originalen den 7. juni 2011.