Skæv-symmetrisk graf

En skæv-symmetrisk graf er en rettet graf, der er isomorf til sin egen transponerede graf . Denne graf er dannet ved at invertere alle buer med isomorfi og er en involution uden fikspunkter . Skævsymmetriske grafer er identiske med dobbeltdækninger af tovejsgrafer .

Skæv-symmetriske grafer blev først introduceret under navnet antisymmetriske digrafer af Tutt [1] , senere under navnet dobbeltdækkende grafer af polære grafer blev de brugt af Zelinka [2] , og senere under navnet dobbeltdækkende grafer af tovejsgrafer brugt af Zaslavsky [3] . De opstår for eksempel ved modellering af søgningen efter alternerende stier og cyklusser , i algoritmer til at finde matchninger i grafer til test, i problemet med at dekomponere en konfiguration i Game of Life i mindre komponenter, i grafvisualiseringsproblemet og i problemet med at konstruere outputgrafer bruges til effektivt at løse 2-tilfredshedsproblemet .

Definition

Som defineret, for eksempel af Goldberg og Karzanov [4] , er en skæv-symmetrisk graf en rettet graf sammen med en funktion , der kortlægger grafens hjørner til dens andre hjørner og opfylder egenskaberne: $G$ $\sigma$ $G$

Til enhver top $v,\sigma (v)\neq v$
Til enhver top $v,\sigma (\sigma (v))=v$
For enhver bue skal også være en bue. $(u,v),(\sigma (v),\sigma (u))$

Du kan bruge den tredje egenskab til at udvide til funktionen til vending af grafbueorientering . $\sigma$ $G$

Den transponerede graf af en graf er den graf, der dannes ved at vende hver kant af grafen , og definerer en isomorfi fra til den transponerede graf. For en skæv-symmetrisk graf er der dog et yderligere krav om, at isomorfien tager hvert toppunkt til et andet toppunkt uden at tillade et toppunkt at kortlægge sig selv, eller at gruppere mere end to toppunkter i en isomorficyklus. $G$ $G$ $\sigma$ $G$

En sti eller cyklus i en skæv-symmetrisk graf siges at være regulær , hvis det tilsvarende toppunkt ikke er en del af stien eller cyklussen for hvert hjørne af stien eller cyklussen. $v$ $\sigma (v)$

Eksempler

Enhver orienteret sti med et lige antal hjørner er skævsymmetrisk i henhold til den symmetri, der udveksler de to ender af stien. Stier med et ulige antal hjørner er dog ikke skævsymmetriske, fordi den omvendte orienteringssymmetri af denne graf kortlægger det midterste hjørne af denne graf ind i sig selv, hvilket ikke er tilladt for skævsymmetriske grafer.

På samme måde er en orienteret cyklus skævsymmetrisk, hvis og kun hvis den har et lige antal hjørner. I dette tilfælde er antallet af forskellige kortlægninger , der implementerer grafens skævhedssymmetri, lig med halvdelen af cyklussens længde. $\sigma$

Polære grafer og stipile, dobbeltdækningsgrafer og tovejsgrafer

En skæv-symmetrisk graf kan på tilsvarende måde defineres som en graf af et dobbeltdæksel af en polær graf (introduceret af Zelinka [5] [6] , og Cook kaldet path arrow graphs [7] [8] ), som er urettede grafer og hvor kanterne, der støder op til hvert toppunkt, er opdelt i to delmængder. Hvert hjørne af en polær graf svarer til to hjørner af en skævsymmetrisk graf, og hver kant på en polær graf svarer til to kanter på en skævsymmetrisk graf. Denne ækvivalens blev brugt af Goldberg og Karzanov [4] til at modellere matchende problemer i form af skæv-symmetriske grafer. I en sådan applikation er de to undersæt af kanter ved hvert toppunkt matchende og ikke-matchende kanter. Zelinka (ifølge F. Zaitek) og Cook visualiserede hjørnerne af den polære graf som punkter, hvor flere jernbanespor konvergerer hvis et tog kører ind i et sporskifte på et jernbanespor, der kommer fra én retning, skal det køre ud gennem sporet i anden retning. Problemet med at finde ikke-selvskærende glatte kurver mellem givne punkter på et jernbanespor opstår, når man kontrollerer, om en form for grafvisualisering er tilladt [9] , og kan modelleres som at finde en regulær sti i en skævsymmetrisk graf.

Et nært beslægtet koncept er tovejsgrafen Edmonds og Johnson [10] (en "polariseret graf" i Zelinkas [5] [6] terminologi ), en graf, hvor hver af de to hjørner af enhver kant kan være enten begyndelsen eller slutningen, uanset fra en anden top. En tovejsgraf kan fortolkes som en polær graf, hvis kanterne på hvert toppunkt er opdelt i overensstemmelse med orienteringen af kanten ved det pågældende toppunkt - begyndelsen eller slutningen. Udvekslingen af roller for begyndelser og ender i et separat vertex ("skift" af et vertex i Zaslavskys terminologi [3] ) giver dog en anden tovejsgraf, men den samme polære graf.

For overensstemmelsen mellem tovejsgrafer og skævsymmetriske grafer, se Zaslavsky [11] eller Babenko [12] .

For at danne en dobbelt dækningsgraf (det vil sige den tilsvarende skævsymmetriske graf) ud fra en polær graf , opretter vi to hjørner fra hvert hjørne af grafen , og , og lader . For hver grafkant skal du oprette to rettede kanter i den dækkende graf, en fra til og en fra til . Hvis den er i den første delmængde af kanter i , går disse to buer fra til og fra til , men hvis den tilhører en anden delmængde, vil buerne være fra til og fra til . Omvendt, givet en skæv-symmetrisk graf , kan man danne en polær graf, der har et toppunkt for ethvert tilsvarende par af hjørner i grafen , og en urettet kant for hvert tilsvarende par kanter i . Urettede kanter ved hvert hjørne af den polære graf kan opdeles i to delmængder, alt efter hvilket toppunkt på den originale graf buen forlader og går ind. $G$ $v$ $G$ $v_{0}$ $v_{1}$ $\sigma (v_{i})=v_{1-i}$ $e=(u,v)$ $G$ $u$ $v$ $v$ $u$ $e$ $v$ $u_{0}$ $v_{0}$ $v_{1}$ $u_{1}$ $e$ $u_{0}$ $v_{1}$ $v_{0}$ $u_{1}$ $G$ $G$ $G$

En regulær sti eller cyklus i en skæv-symmetrisk graf svarer til en sti eller cyklus i en polær graf, der bruger højst en kant fra hver undergruppe af kanter ved hver af dens hjørner.

Matchende

Når man konstruerer en matchning i en ikke-rettet graf, er det vigtigt at finde en vekslende sti , en sti gennem knudepunkter, der starter og slutter ved spidser, der ikke hører til matchningen, og hvis kanter ved ulige positioner af stien ikke hører til denne delvis matchning, og hvis kanter ved lige positioner af stien er kanter af matchningen. Ved at fjerne fra matchningen kanterne fra den sti, der hører til matchningen, og tilføje de resterende kanter af stien til den, kan størrelsen af matchningen øges. På samme måde er cyklusser, der veksler mellem matchende og ikke-matchende kanter, vigtige i vægtede matchningsproblemer. Som Goldberg og Karzanov [4] har vist , kan en vekslende sti eller cyklus i en urettet graf modelleres som en regulær sti eller cyklus i en skævsymmetrisk rettet graf. For at skabe en skæv-symmetrisk graf ud fra en urettet graf med en given matchning skal du betragte grafen som en pilegraf, hvor kanterne ved hvert hjørne er opdelt i at høre til og ikke høre til kombinationen. En vekslende sti i en graf er så en regulær sti i den pilegraf, og en vekslende cyklus i grafen er en regulær cyklus i pilegrafen. $G$ $M$ $G$ $G$ $G$

Goldberg og Karzanov [4] generaliserede alternerende stialgoritmer for at vise, at eksistensen af en regulær sti mellem to vilkårlige hjørner af en skæv-symmetrisk graf kan verificeres i lineær tid. Hvis der derudover er givet en ikke-negativ længdefunktion på grafens kanter, der tildeler en kant og en kant lige længder , er den korteste regulære vej, der forbinder et givet par knudepunkter i en skævsymmetrisk graf med kanter og hjørner kan findes i tide . Hvis længdefunktionen kan tage negative værdier, kan eksistensen af en negativ regulær cyklus verificeres i polynomiel tid . $e$ $\sigma (e)$ $m$ $n$ $O(m\log n)$

Ud over problemer med stier, der opstår, når man arbejder med matchninger, blev skæv-symmetriske generaliseringer af maksimum flow og minimum cut-sætning [1] [13] også undersøgt .

Theory of the Game of Life

Cook [8] viste, at en konfiguration i Game of Life kan opdeles i to mindre konfigurationer, hvis og kun hvis grafen for den tilhørende rejsepilegraf indeholder en regulær cyklus. For pilegrafer, der ikke indeholder mere end tre kanter pr. vertex, kan dette kontrolleres i polynomisk tid ved at fjerne en efter en broer (kanter, hvis fjernelse gør grafen afbrudt) og hjørner, hvor alle kanter tilhører den samme del af partitionen, mens der er mulighed for at gennemføre sådanne forenklinger. Hvis resultatet er en tom graf, er der ingen regelmæssig cyklus i grafen. Ellers kan en regelmæssig cyklus findes i enhver ikke-brokoblet komponent. Søgningen efter broer i denne algoritme kan udføres effektivt ved hjælp af den dynamiske Sorup-algoritme [14] . En lignende teknik til at fjerne broer i forbindelse med matchninger blev tidligere overvejet af Gabov, Kaplan og Tarjan [15] .

Gennemførlighed

2 -tilfredshedsproblemet , det vil sige et udtryk i konjunktiv normalform med to variable eller deres negation, kan transformeres til en outputgraf ved at erstatte hvert udtryk med to implikationer og . I denne graf repræsenterer hvert hjørne en variabel eller dens negation, og hver rettet kant repræsenterer en implikation. Grafen er konstruktionsmæssigt skæv-symmetrisk med en funktion , der kortlægger hver variabel til dens negation. Som Asvall, Plass og Tarjan [16] har vist , svarer det at finde et tilfredsstillende sæt værdier for et tilfælde af et 2-tilfredshedsproblem til at opdele denne outputgraf i to delmængder af toppunkter, og , så ingen bue starter kl og slutter kl . Hvis en sådan opdeling eksisterer, kan et tilfredsstillende sæt af værdier opnås ved at tildele en sand værdi til hver variabel i og en falsk værdi til hver variabel i . Dette kan gøres, hvis og kun hvis ingen stærkt forbundet komponent i grafen indeholder både et toppunkt og dets komplementære toppunkt . Hvis to hjørner tilhører den samme stærkt forbundne komponent, er de tilsvarende variable eller deres negationer nødvendigvis lig med hinanden i ethvert tilfredsstillende sæt af værdier i en instans af 2-tilfredshedsproblemet. Den samlede tid for at kontrollere for stærk forbindelse og finde en partition af outputgrafen er lineær i størrelsen af et givet 2-CNF-udtryk. $u\lor v$ $(\likke u)\Rightarrow v$ $(\lnot v)\Rightarrow u$ $\sigma$ $S$ $\sigma (S)$ $S$ $\sigma (S)$ $S$ $\sigma (S)$ $v$ $\sigma (v)$

Anerkendelse

Problemet med at erkende, om en given rettet graf er skævsymmetrisk, er NP-komplet . Dette følger af Lalondes resultat [17] , at problemet med at finde en farvevendende involution i en todelt graf er NP-komplet, hvis og kun hvis den rettede graf givet ved orienteringen af hver kant fra en farveklasse til en anden er skævsymmetrisk . Denne kompleksitet påvirker ikke stifindende algoritmer for skæv-symmetriske grafer, da disse algoritmer antager, at den skæv-symmetriske struktur er givet som en del af algoritmens input, snarere end afledt fra grafen alene.

Noter

↑ 1 2 Tutte, 1967 .
↑ Zelinka, 1976b .
↑ 12 Zaslavsky , 1991 .
↑ 1 2 3 4 Goldberg, Karzanov, 1996 .
↑ 1 2 Zelinka, 1974 .
↑ 12 Zelinka , 1976a .
↑ Turnout- grafen kommer fra repræsentationen af grafen som analog med jernbanespor, med krydsene mellem individuelle grene som skiftepile.
↑ 12 Cook , 2003 .
↑ Hui, Schäfer, Štefankovič, 2004 .
↑ Edmonds, Johnson, 1970 .
↑ Zaslavsky, 1991 , s. Afsnit 5.
↑ Babenko, 2006 .
↑ Goldberg, Karzanov, 2004 .
↑ Thorup, 2000 .
↑ Gabow, Kaplan, Tarjan, 1999 .
↑ Aspvall, Plass, Tarjan, 1979 .
↑ Lalonde, 1981 .

Litteratur

Bengt Aspvall, Michael F. Plass, Robert E. Tarjan. En lineær-tidsalgoritme til at teste sandheden af visse kvantificerede booleske formler // Information Processing Letters. - 1979. - T. 8 , no. 3 . — S. 121–123 . - doi : 10.1016/0020-0190(79)90002-4 .
Maxim A. Babenko. Acykliske tovejs- og skævsymmetriske grafer: algoritmer og struktur // Datalogi - Teori og applikationer. - Springer-Verlag, 2006. - T. 3967. - S. 23-34. — (Forelæsningsnotater i datalogi). - ISBN 978-3-540-34166-6 . - doi : 10.1007/11753728_6 .
Norman L. Biggs. Algebraisk grafteori. — London: Cambridge University Press, 1974.
Matthew Cook. Stillebenteori // Nye konstruktioner i cellulære automater. - Santa Fe Institute Studies in the Sciences of Complexity, Oxford University Press, 2003. - s. 93–118. .
Jack Edmonds, Ellis L. Johnson. Matching: en velløst klasse af lineære programmer // Combinatorial Structures and their Applications: Proceedings of the Calgary Symposium, juni 1969. - Gordon and Breach, 1970. Genoptrykt i "Combinatorial Optimization - Eureka, You Shrink!", Springer-Verlag , Lecture Notes in Computer Science 2570, 2003, pp. 27-30, doi : 10.1007/3-540-36478-1_3 .
Harold N. Gabow, Haim Kaplan, Robert E. Tarjan . Unikke maksimale matchende algoritmer // Proc. 31. ACM Symp. Theory of Computing (STOC). - 1999. - S. 70-78. — ISBN 1-58113-067-8 . - doi : 10.1145/301250.301273 .
Andrew V. Goldberg, Alexander V. Karzanov. Stiproblemer i skævsymmetriske grafer // Combinatorica. - 1996. - T. 16 , no. 3 . — S. 353–382 . - doi : 10.1007/BF01261321 .
Andrew V. Goldberg, Alexander V. Karzanov. Maksimale skævsymmetriske flows og matchninger // Matematisk programmering. - 2004. - T. 100 , no. 3 . — S. 537–568 . - doi : 10.1007/s10107-004-0505-z . — arXiv : math/0304290 .
Peter Hui, Marcus Schaefer, Daniel Štefankovič. Togspor og sammenløbstegninger // Proc. 12. Int. Symp. Graftegning . - Springer-Verlag, 2004. - T. 3383. - S. 318-328. — (Forelæsningsnotater i datalogi).
Francois Lalonde. Le problème d'étoiles pour graphes est NP-complet // Diskret matematik. - 1981. - T. 33 , no. 3 . — S. 271–280 . - doi : 10.1016/0012-365X(81)90271-5 .
Mikkel Thorup. Næsten optimal fuldt dynamisk [ sic ] grafforbindelse // Proc. 32. ACM-symposium om teori om computing . - 2000. - S. 343-350 . — ISBN 1-58113-184-4 . - doi : 10.1145/335305.335345 .
Tutte WT Antisymmetriske digrafier // Canadian Journal of Mathematics. - 1967. - T. 19 . — S. 1101–1117 . - doi : 10.4153/CJM-1967-101-8 .
Thomas Zaslavsky. Signerede grafer // Diskret anvendt matematik. - 1982. - T. 4 . — s. 47–74 . - doi : 10.1016/0166-218X(82)90033-6 .
Thomas Zaslavsky. Orientering af signerede grafer // European Journal of Combinatorics. - 1991. - T. 12 . — S. 361–375 . - doi : 10.1016/s0195-6698(13)80118-7 .
Bohdan Zelinka. Polære grafer og jernbanetrafik // Aplikace Matematicy. - 1974. - T. 19 . — S. 169–176 .
Bohdan Zelinka. Isomorfismer af polære og polariserede grafer // Czechoslovak Mathematical Journal. - 1976a. - T. 26 . — S. 339–351 .
Bohdan Zelinka. Analog af Mengers sætning for polære og polariserede grafer // Czechoslovak Mathematical Journal. - 1976b. - T. 26 . — S. 352–360 .