Cyklisk rang

Den cykliska rangordningen för en riktad graf är ett mått på anslutningsmöjligheten för en digraf som föreslås av Eggan och Buchi [1] . Detta koncept fångar intuitivt hur nära en digraf är en riktad acyklisk graf (DAG, en:DAG) när den cykliska rangordningen för DAG är noll, medan en riktad digraf av ordningen n med slingor vid varje vertex har cyklisk rang n . Den cykliska rangordningen för en riktad graf är nära relaterad till träddjupet för en oriktad graf och iterationshöjden för vanliga språk . Den cykliska rangordningen har även funnit tillämpning i glesa matrisberäkningar (se Bodlaender, Gilbert, Hafsteinsson, Kloks, 1995 ) och logik [2] .

Definition

Den cykliska rangordningen r ( G ) för en digraf G  = ( V ,  E ) definieras induktivt enligt följande

var är digrafen som erhålls genom att ta bort vertex v och alla kanter som börjar eller slutar på v .

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

Historik

Den cykliska rangen introducerades av Eggan [1] i samband med iterationshöjden för reguljära språk . Den cykliska rangen återupptäcktes av Aizenshtat och Liu [3] som en generalisering av ett träds oriktade djup . Konceptet har utvecklats sedan början av 1980-talet och har använts för att arbeta med glesa matriser [4] .

Exempel

Den cykliska rangordningen för en riktad acyklisk graf är 0, medan en komplett digraf av ordningen n med en slinga vid varje vertex har en cyklisk rangordning på n . Förutom dessa två fall är den cykliska rangordningen för flera andra digrafer känd: en oriktad ordningsbana n som har en kantsymmetrirelation och inga loopar har en cyklisk rangordning [5] . För en orienterad -torus , dvs. direkt produkt av två orienterade konturer med längden m och n , vi har och för m ≠ n [1] [6] .

Cyklisk rangberäkning

Att beräkna den cykliska rangen är en svår uppgift. Gruber [7] bevisade att motsvarande lösbarhetsproblem är NP-komplett även för glesa digrafer med maximal utgrad 2. Den goda nyheten är att problemet är lösbart i tid på digrafer med maximal utgrad 2 och i tid på allmänna digrafer. Det finns en approximationsalgoritm med en approximationskoefficient .

Applikationer

Iterationshöjd för vanliga språk

Den första tillämpningen av cyklisk rang var i teorin om formella språk för att studera iterationshöjden för språket i vanliga språk . Eggan [1] etablerade ett förhållande mellan teorier om reguljära uttryck, finita automater och riktade grafer . Under de följande åren blev detta förhållande känt som Eggans sats [8] . I automatteorin definieras en icke-deterministisk finit automat med c ε-övergångar (ε-NFA) som en 5 , ( Q , Σ, δ , q 0 , F ) bestående av

Ett ord w ∈ Σ * tillåts av en ε-NCF-automat om det finns en riktad väg från ett initialtillstånd q 0 till något sluttillstånd från F med kanter från δ , så att sammanlänkning av alla etiketter längs vägen ger ett ord w . Mängden av alla ord över Σ * som accepteras av automaten är det språk som accepteras av automaten A .

När man talar om egenskaperna hos digrafer för en icke-deterministisk finit automat A med en uppsättning tillstånd Q , menar man naturligtvis en digraf med en uppsättning av hörn Q genererad av övergångsrelationen.

Eggans sats : Iterationshöjden för ett reguljärt språk L är lika med den minsta cykliska rangordningen bland alla icke-deterministiska finita automater med ε-övergångar (med tomma övergångar) som accepterar språket L.

Bevis för detta teorem gavs av Eggan [1] och senare av Sakarovich [8] .

Cholesky nedbrytning för glesa matriser

En annan tillämpning av detta koncept ligger inom området gles matrisberäkning , nämligen att använda kapslad dissektion för att beräkna Cholesky-nedbrytningen av en (symmetrisk) matris med hjälp av en parallell algoritm. Den givna glesa matrisen M kan tolkas som närliggande matris för någon symmetrisk digraf G med n hörn, så att matrisens element som inte är noll motsvarar en-till-en kanterna på grafen G . Om den cykliska rangordningen för digrafen G inte överstiger k , så kan den Cholesky-nedbrytningen av matrisen M beräknas i högst k steg på en parallell dator med processorer [9] .

Se även

Anteckningar

  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 .

Litteratur