Cyklická hodnost

Cyklická hodnost orientovaného grafu je mírou konektivity digrafu navrženého Egganem a Buchi [1] . Tento koncept intuitivně zachycuje, jak blízko je digraf k orientovanému acyklickému grafu (DAG, en:DAG), když je cyklická hodnost DAG nulová, zatímco řízený digraf řádu n se smyčkami v každém vrcholu má cyklickou hodnost n . Cyklická hodnost orientovaného grafu úzce souvisí s hloubkou stromu neorientovaného grafu a iterační výškou regulárních jazyků .. Cyklická hodnost také našla uplatnění ve výpočtech s řídkou maticí (viz Bodlaender, Gilbert, Hafsteinsson, Kloks, 1995 ) a logice [2] .

Definice

Cyklická hodnost r ( G ) digrafu G = ( V , E ) je induktivně definována následovně

Je-li G acyklické, pak r ( G ) = 0 .
Pokud je G pevně spojeno a E není prázdné, pak

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

kde je digraf získaný odstraněním vrcholu v a všech hran začínajících nebo končících na v .

Gv

Pokud G není silně spojená složka, pak r ( G ) se rovná maximálnímu cyklickému pořadí mezi všemi silně spojenými složkami G.

Hloubka stromu neorientovaného grafu má velmi podobnou definici s neorientovanou konektivitou a připojenými komponentami namísto silné konektivity a silně propojených komponent.

Historie

Cyklickou pozici zavedl Eggan [1] v souvislosti s iterační výškou regulárních jazyků . Cyklickou hodnost znovu objevili Aizenshtat a Liu [3] jako zobecnění neorientované hloubky stromu . Koncept byl vyvíjen od počátku 80. let a byl používán pro práci s řídkými maticemi [4] .

Příklady

Cyklická hodnost orientovaného acyklického grafu je 0, zatímco úplný digraf řádu n se smyčkou v každém vrcholu má cyklickou hodnost n . Kromě těchto dvou případů je známa cyklická hodnost několika dalších digrafů: neorientovaná cesta řádu n , která má vztah symetrie hrany a žádné smyčky nemá cyklickou hodnost [5] . Pro orientovaný -torus , tzn. přímý součin dvou orientovaných vrstevnic délky m an , máme a pro 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$

Výpočet cyklického pořadí

Výpočet cyklického pořadí je obtížný úkol. Gruber [7] dokázal, že odpovídající problém řešitelnosti je NP-úplný i pro řídké digrafy s maximálním přesahem 2. Dobrou zprávou je, že problém je řešitelný v čase na digrafech s maximálním přesahem 2 a v čase na obecných digrafech. Existuje aproximační algoritmus s aproximačním koeficientem . $O(1,9129^{n})$ $O^{*}(2^{n})$ $O((\log n)^{\frac {3}{2)))$

Aplikace

Iterační výška regulárních jazyků

První aplikace cyklické hodnosti byla v teorii formálních jazyků ke studiu iterační výšky jazyka regulárních jazyků . Eggan [1] vytvořil vztah mezi teoriemi regulárních výrazů, konečnými automaty a orientovanými grafy . V následujících letech se tento vztah stal známým jako Egganův teorém [8] . V teorii automatů je nedeterministický konečný automat s c ε-přechody (ε-NFA) definován jako 5 , ( Q , Σ, δ , q 0 , F ) sestávající z

konečná množina stavů Q
konečná množina vstupních symbolů Σ (abeceda)
množiny označených hran δ , nazývané přechodové vztahy : Q × (Σ ∪{ε}) × Q . Zde ε znamená prázdný řetězec .
počáteční stav q 0 ∈ Q
množiny stavů F ( absorbující stavy ) F ⊆ Q .

Slovo w ∈ Σ * je povoleno automatem ε-NCF, pokud existuje řízená cesta z počátečního stavu q 0 do nějakého konečného stavu z F pomocí hran z δ , takže zřetězení všech značek podél cesty dá slovo w . Množina všech slov nad Σ * akceptovaná automatem je jazyk akceptovaný automatem A .

Hovoříme-li o vlastnostech digrafů nedeterministického konečného automatu A s množinou stavů Q , máme na mysli přirozeně digraf s množinou vrcholů Q generovaných přechodovou relací.

Egganův teorém : Iterační výška regulárního jazyka L je rovna minimální cyklické hodnosti mezi všemi nedeterministickými konečnými automaty s ε-přechody (s prázdnými přechody) akceptujícími jazyk L.

Důkazy této věty podal Eggan [1] a později Sakarovich [8] .

Choleského rozklad pro řídké matice

Další aplikace tohoto konceptu spočívá v oblasti počítání s řídkými maticemi , konkrétně použít vnořenou disekci při výpočtu Choleského rozkladu (symetrické) matice pomocí paralelního algoritmu. Danou řídkou matici M lze interpretovat jako matici sousednosti nějakého symetrického digrafu G s n vrcholy, takže nenulové prvky matice odpovídají jedna ku jedné hranám grafu G . Pokud cyklická hodnost digrafu G nepřesáhne k , pak lze Choleského rozklad matice M spočítat nanejvýš k krocích na paralelním počítači s procesory [9] . $(n\krát n)$ $n$

Viz také

Pořadí vrstevnic

Literatura

Hans L. Bodlaender, John R. Gilbert, Hjálmtyr Hafsteinsson, Ton Kloks. Přibližování šířky stromu, šířky cesty, velikosti fronty a nejkratšího eliminačního stromu // Journal of Algorithms. - 1995. - T. 18 , no. 2 . - S. 238-255 . - doi : 10.1006/jagm.1995.1009 .
Dariusz Dereniowski, Marek Kubale. Cholesky faktorizace matic v paralele a řazení grafů // 5. mezinárodní konference paralelního zpracování a aplikované matematiky . - Springer-Verlag, 2004. - T. 3019. - S. 985-992. — (Poznámky z informatiky). - doi : 10.1007/978-3-540-24669-5_127 . .
Lawrence C. Eggan. Přechodové grafy a hvězdná výška pravidelných událostí // Michigan Mathematical Journal . - 1963. - T. 10 , čís. 4 . - S. 385-397 . - doi : 10,1307/mmj/1028998975 .
Stanley C. Eisenstat, Joseph W. H. Liu. Teorie eliminačních stromů pro řídké nesymetrické matice // SIAM Journal on Matrix Analysis and Applications. - 2005. - T. 26 , no. 3 . - S. 686-705 . - doi : 10.1137/S089547980240563X .
Hermann Gruber. Digraph míry složitosti a aplikace v teorii formálních jazyků // Teoretická informatika. - 2012. - Sv. 14 . - S. 189-204 . .
Hermann Gruber, Markus Holzer. Konečné automaty, konektivita digrafů a velikost regulárních výrazů //Proč. 35. mezinárodní kolokvium o automatech, jazycích a programování . - Springer-Verlag, 2008. - T. 5126. - S. 39-50. — (Poznámky z informatiky). - doi : 10.1007/978-3-540-70583-3_4 .
Robert McNaughton. Složitost smyčky pravidelných událostí // Informační vědy. - 1969. - svazek 1 , vydání. 3 . - S. 305-328 . - doi : 10.1016/S0020-0255(69)80016-2 .
Benjamin Rossman. Věty o zachování homomorfismu // Journal of the ACM . - 2008. - T. 55 , no. 3 . — C. Článek 15 . doi : 10.1145 / 1379759.1379763 .
Jacques Sakarovič. Prvky teorie automatů. - Cambridge University Press, 2009. - ISBN 0-521-84425-8 .
Robert Schreiber. Nová implementace řídké gaussovské eliminace // ACM Transactions on Mathematical Software . - 1982. - T. 8 , no. 3 . - S. 256-276 . - doi : 10.1145/356004.356006 . Archivováno z originálu 7. června 2011.