Ciklikus rang

Az irányított gráf ciklikus rangja egy digráf konnektivitásának mértéke , amelyet Eggan és Buchi [1] javasolt . Ez a fogalom intuitív módon rögzíti, hogy egy digráf milyen közel van egy irányított aciklikus gráfhoz (DAG, en:DAG), ha a DAG ciklikus rangja nulla, míg az n -es rendű irányított digráfnak , amelyben minden csúcsban hurkok vannak, ciklikus rangja n . Az irányított gráf ciklikus rangja szorosan összefügg az irányítatlan gráf famélységével és a reguláris nyelvek iterációs magasságával . . A ciklikus rangot ritka mátrixszámításokban (lásd Bodlaender, Gilbert, Hafsteinsson, Kloks, 1995 ) és logikában is alkalmazták [2] .

Definíció

A G = ( V , E ) digráf r ( G ) ciklikus rangját induktív módon a következőképpen definiáljuk

Ha G aciklikus, akkor r ( G ) = 0 .
Ha G erősen összefüggő és E nem üres, akkor

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

ahol a v csúcs és minden v -vel kezdődő vagy végződő él eltávolításával kapott digráf .

Gv

Ha G nem erősen kapcsolódó komponens, akkor r ( G ) egyenlő a G összes erősen kapcsolódó komponense közötti maximális ciklikus ranggal .

Az irányítatlan gráf famélysége nagyon hasonló definícióval rendelkezik, irányítatlan kapcsolattal és összekapcsolt komponensekkel az erős kapcsolat és az erősen kapcsolódó komponensek helyett.

Történelem

A ciklikus rangot Eggan [1] vezette be a reguláris nyelvek iterációs magasságával összefüggésben . A ciklikus rangot Aizenshtat és Liu [3] fedezte fel újra a fa irányítatlan mélységének általánosításaként . A koncepciót az 1980-as évek eleje óta fejlesztették ki, és ritka mátrixokkal való munkavégzésre használták [4] .

Példák

Egy irányított aciklikus gráf ciklikus rangja 0, míg egy n -es rendű teljes digráf, amelynek minden csúcsában van egy hurok, ciklikus rangja n . Ezen a két eseten kívül számos más digráf ciklikus rangja ismert: egy n - rendű irányítatlan út, amelynek élszimmetria-relációja van, és nincs ciklus, ciklikus rangja [5] . Orientált -tórus esetén, azaz két m és n hosszúságú orientált körvonal közvetlen szorzata, és m ≠ n eseté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$

Ciklikus rangszámítás

A ciklikus rang kiszámítása nehéz feladat. Gruber [7] bebizonyította, hogy a megfelelő megoldhatósági probléma NP-teljes még a 2-es maximális kiesési fokozatú ritka digráfoknál is. A jó hír az, hogy a feladat időben megoldható a maximum 2 -es kiugró digráfokon és időben az általános digráfokon is. Létezik egy közelítő algoritmus közelítési együtthatóval . $O(1,9129^{n})$ $O^{*}(2^{n})$ $O((\log n)^{\frac {3}{2)))$

Alkalmazások

Szabályos nyelvek iterációs magassága

A ciklikus rang első alkalmazása a formális nyelvek elméletében volt a reguláris nyelvek nyelvének iterációs magasságának tanulmányozására . Eggan [1] kapcsolatot hozott létre a reguláris kifejezés-elméletek, a véges automaták és az irányított gráfok között . A következő években ez az összefüggés Eggan tételeként vált ismertté [8] . Az automataelméletben egy nem determinisztikus véges automatát c ε-átmenetekkel (ε-NFA) úgy definiálunk, mint egy 5 , ( Q , Σ, δ , q 0 , F ), amely a következőkből áll.

Q állapotok véges halmaza
bemeneti szimbólumok véges halmaza Σ (ábécé)
δ címkézett élek halmazai , úgynevezett átmeneti relációk : Q × (Σ ∪{ε}) × Q . Itt ε az üres karakterláncot jelenti .
kezdeti állapot q 0 ∈ Q
állapothalmazok F ( elnyelő állapotok ) F ⊆ Q.

Egy w ∈ Σ * szót megenged egy ε-NCF automata, ha van egy irányított út a q 0 kezdeti állapotból egy F -ből valamilyen végső állapotba a δ élei segítségével , így az összes címke összefűzése az útvonal mentén egy w szót eredményez. . Az automata által elfogadott Σ * feletti összes szó halmaza az A automata által elfogadott nyelv .

Amikor egy Q állapothalmazú nemdeterminisztikus véges automata digráfjainak tulajdonságairól beszélünk , akkor természetesen az átmeneti reláció által generált Q csúcshalmazú digráfot értünk .

Eggan tétele : Egy L reguláris nyelv iterációs magassága megegyezik az L nyelvet elfogadó ε-átmenetekkel (üres átmenetekkel) rendelkező összes nemdeterminisztikus véges automata minimális ciklikus rangjával .

Ezt a tételt Eggan [1] , majd Sakarovich [8] bizonyította .

Cholesky-felbontás ritka mátrixokhoz

Ennek a fogalomnak egy másik alkalmazása a ritka mátrixszámítás területén rejlik , nevezetesen a beágyazott disszekció alkalmazása egy (szimmetrikus) mátrix Cholesky-féle dekompozíciójának párhuzamos algoritmussal történő kiszámításához. Az adott M ritka mátrix értelmezhető valamilyen n csúcsú G szimmetrikus digráf szomszédsági mátrixaként , így a mátrix nem nulla elemei egytől egyig megfelelnek a G gráf éleinek . Ha a G digráf ciklikus rangja nem haladja meg a k -t, akkor az M mátrix Cholesky-féle dekompozíciója legfeljebb k lépésben számítható ki egy párhuzamos processzoros számítógépen [9] . $(n\x n)$ $n$

Lásd még

Kontúr rang

Irodalom

Hans L. Bodlaender, John R. Gilbert, Hjálmtyr Hafsteinsson, Ton Kloks. Faszélesség, útvonalszélesség, frontméret és legrövidebb eliminációs fa közelítése // Journal of Algorithms. - 1995. - T. 18 , sz. 2 . - S. 238-255 . - doi : 10.1006/jagm.1995.1009 .
Dariusz Dereniowski, Marek Kubale. Cholesky-féle mátrixok párhuzamosítása és gráfok rangsorolása // 5. nemzetközi konferencia a párhuzamos feldolgozásról és az alkalmazott matematikáról . - Springer-Verlag, 2004. - T. 3019. - S. 985-992. — (Előadási jegyzetek a számítástechnikáról). - doi : 10.1007/978-3-540-24669-5_127 . .
Lawrence C. Eggan. Átmeneti grafikonok és a rendszeres események csillagmagassága // Michigan Mathematical Journal . - 1963. - T. 10 , sz. 4 . - S. 385-397 . - doi : 10.1307/mmj/1028998975 .
Stanley C. Eisenstat, Joseph W. H. Liu. Az eliminációs fák elmélete ritka aszimmetrikus mátrixokhoz // SIAM Journal on Matrix Analysis and Applications. - 2005. - T. 26 , sz. 3 . - S. 686-705 . - doi : 10.1137/S089547980240563X .
Hermann Gruber. Digráf-komplexitás mérései és alkalmazásai a formális nyelvelméletben // Elméleti számítástechnika. - 2012. - Kt. 14 . - P. 189-204 . .
Hermann Gruber, Markus Holzer. Véges automaták, digráf kapcsolat és reguláris kifejezés mérete //Proc. 35. Nemzetközi Kollokvium automatákkal, nyelvekkel és programozással . - Springer-Verlag, 2008. - T. 5126. - S. 39-50. — (Előadási jegyzetek a számítástechnikáról). - doi : 10.1007/978-3-540-70583-3_4 .
Robert McNaughton. A rendszeres események hurokbonyolultsága // Információtudomány. - 1969. - 1. évf. , szám. 3 . - S. 305-328 . - doi : 10.1016/S0020-0255(69)80016-2 .
Benjamin Rossman. Homomorfizmus megőrzési tételek // Journal of the ACM . - 2008. - T. 55 , sz. 3 . — C. 15. cikk . doi : 10.1145 / 1379759.1379763 .
Jacques Sakarovitch. Az automataelmélet elemei. - Cambridge University Press, 2009. - ISBN 0-521-84425-8 .
Robert Schreiber. A ritka Gauss-elimináció új megvalósítása // ACM Transactions on Mathematical Software . - 1982. - T. 8 , sz. 3 . - S. 256-276 . - doi : 10.1145/356004.356006 . Archiválva az eredetiből 2011. június 7-én.