Skev-symmetrisk graf

En skevsymmetrisk graf  är en riktad graf som är isomorf till sin egen transponerade graf . Denna graf bildas genom att invertera alla bågar med isomorfism och är en involution utan fixpunkter . Skevsymmetriska grafer är identiska med dubbla omslag av dubbelriktade grafer .

Skevsymmetriska grafer introducerades först under namnet antisymmetriska digrafer av Tutt [1] , senare under namnet dubbla täckande grafer av polära grafer användes de av Zelinka [2] , och senare under namnet dubbla täckande grafer av dubbelriktade grafer används av Zaslavsky [3] . De uppstår till exempel vid modellering av sökningen efter alternerande vägar och cykler , i algoritmer för att hitta matchning i grafer för testning, i problemet med att bryta ner en konfiguration i Game of Life i mindre komponenter, i problemet med grafvisualiseringoch i problemet med att konstruera inferensgrafer , som används för att effektivt lösa 2-satisfiability-problemet .

Definition

Som definierats av till exempel Goldberg och Karzanov [4] är en skevsymmetrisk graf  en riktad graf tillsammans med en funktion som mappar grafens hörn till dess andra hörn och uppfyller egenskaperna:

  1. För vilken topp som helst
  2. För vilken topp som helst
  3. För varje båge måste också vara en båge.

Du kan använda den tredje egenskapen för att utöka till funktionen för omvändning av grafbågsorientering .

Den transponerade grafen för en graf är den graf som bildas genom att vända varje kant av grafen och definierar en isomorfism från till den transponerade grafen. Men för en skevsymmetrisk graf finns det ett ytterligare krav att isomorfismen tar varje vertex till en annan vertex utan att tillåta en vertex att mappa in i sig själv, eller att gruppera mer än två hörn i en isomorfismcykel.

En bana eller cykel i en skevsymmetrisk graf sägs vara regelbunden om, för varje hörn av banan eller cykeln, motsvarande hörn inte är en del av banan eller cykeln.

Exempel

Varje orienterad bana med ett jämnt antal hörn är snedsymmetrisk, enligt den symmetri som byter ut banans två ändar. Banor med ett udda antal hörn är dock inte snedsymmetriska eftersom den omvända orienteringssymmetrin för denna graf mappar mitten av denna graf i sig själv, vilket inte är tillåtet för skevsymmetriska grafer.

På liknande sätt är en orienterad cykel skevsymmetrisk om och endast om den har ett jämnt antal hörn. I det här fallet är antalet olika mappningar som implementerar skevningssymmetrin i grafen lika med halva cykelns längd.

Polära grafer och vägpilar, dubbla täckningsdiagram och dubbelriktade grafer

En skevsymmetrisk graf kan på motsvarande sätt definieras som en graf av en dubbel täckning av en polär graf (introducerad av Zelinka [5] [6] , och Cook kallade path arrow graphs [7] [8] ), som är oriktade grafer och där kanterna intill varje vertex är uppdelade i två delmängder. Varje hörn av en polär graf motsvarar två hörn i en skevsymmetrisk graf, och varje kant av en polär graf motsvarar två kanter av en skevsymmetrisk graf. Denna ekvivalens användes av Goldberg och Karzanov [4] för att modellera matchningsproblem i form av skevsymmetriska grafer. I en sådan applikation är de två underuppsättningarna av kanter vid varje vertex matchande och icke-matchande kanter. Zelinka (enligt F. Zaitek) och Cook visualiserade polargrafens hörn som punkter där flera järnvägsspår konvergerar  om ett tåg kommer in i en spårväxel på ett järnvägsspår som kommer från en riktning måste det gå ut genom spåret i annan riktning. Problemet med att hitta icke-självkorsande jämna kurvor mellan givna punkter på ett järnvägsspår uppstår när man kontrollerar om någon form av grafvisualisering är tillåten [9] , och kan modelleras som att hitta en vanlig bana i en skevsymmetrisk graf.

Ett närbesläktat begrepp är den dubbelriktade grafen Edmonds och Johnson [10] (en "polariserad graf" i Zelinkas [5] [6] terminologi ), en graf där var och en av de två hörnen på vilken kant som helst kan vara antingen början eller slutet, oavsett från en annan topp. En dubbelriktad graf kan tolkas som en polär graf om kanterna på varje vertex är uppdelade enligt orienteringen av kanten vid den vertexen - början eller slutet. Utbytet av roller för början och slut i en separat vertex ("byte" av en vertex i Zaslavskijs terminologi [3] ) ger dock en annan dubbelriktad graf, men samma polära graf.

För överensstämmelse mellan dubbelriktade grafer och skevsymmetriska grafer, se Zaslavsky [11] eller Babenko [12] .

För att bilda en dubbeltäckningsgraf (det vill säga motsvarande skevsymmetriska graf) från en polär graf skapar vi två hörn från varje hörn av grafen , och , och låter . För varje grafkant skapar du två riktade kanter i den täckande grafen, en från till och en från till . Om den är i den första delmängden av kanter i går dessa två bågar från till och från till , men om den tillhör en annan delmängd kommer bågarna att vara från till och från till . Omvänt, givet en skev-symmetrisk graf , kan man bilda en polär graf som har en vertex för vilket motsvarande par av hörn i grafen , och en oriktad kant för varje motsvarande par av kanter i . Oriktade kanter vid varje hörn av den polära grafen kan delas in i två delmängder beroende på vilken vertex på den ursprungliga grafen bågen lämnar och går in.

En vanlig bana eller cykel i en skevsymmetrisk graf motsvarar en bana eller cykel i en polär graf som använder högst en kant från varje delmängd av kanter vid var och en av sina hörn.

Matchar

När man konstruerar en matchning i en oriktad graf är det viktigt att hitta en alternerande bana , en bana genom hörn som börjar och slutar vid hörn som inte hör till matchningen, och vars kanter vid udda positioner av banan inte hör till denna partiell matchning, och vars kanter vid jämna positioner av banan är kanter av matchningen. Genom att ta bort från matchningen kanterna från den banan som hör till matchningen och lägga till de återstående kanterna av banan till den, kan storleken på matchningen ökas. På liknande sätt är cykler som växlar mellan matchande och icke-matchande kanter viktiga i viktade matchningsproblem. Som Goldberg och Karzanov [4] har visat kan en alternerande bana eller cykel i en oriktad graf modelleras som en vanlig bana eller cykel i en skevsymmetrisk riktad graf. För att skapa en skevsymmetrisk graf från en oriktad graf med en given matchning , betrakta grafen som en pilgraf där kanterna vid varje vertex är uppdelade i att tillhöra och inte tillhöra kombinationen. En alternerande bana i en graf är då en vanlig bana i den pilgrafen, och en alternerande cykel i grafen är en vanlig cykel i pilgrafen.

Goldberg och Karzanov [4] generaliserade algoritmer för alternerande vägar för att visa att förekomsten av en regelbunden väg mellan två hörn av en skevsymmetrisk graf kan verifieras i linjär tid. Om dessutom en icke-negativ längdfunktion på grafens kanter ges som tilldelar lika längder till en kant och en kant , den kortaste vanliga vägen som förbinder ett givet nodpar i en skevsymmetrisk graf med kanter och hörn kan hittas i tid . Om längdfunktionen kan ta negativa värden kan förekomsten av en negativ regelbunden cykel verifieras i polynomtid .

Förutom problem med banor som uppstår när man arbetar med matchningar, studerades också skev-symmetriska generaliseringar av maximalt flöde och minimum cut-sats [1] [13] .

Theory of the Game of Life

Cook [8] visade att en konfiguration i Game of Life kan delas upp i två mindre konfigurationer om och endast om grafen för den tillhörande resepilgrafen innehåller en vanlig cykel. För pilgrafer som inte innehåller mer än tre kanter per vertex kan detta kontrolleras i polynomtid genom att ta bort en och en broar (kanter vars borttagning gör att grafen kopplas bort) och hörn där alla kanter tillhör samma del av partitionen, medan det finns en möjlighet att genomföra sådana förenklingar. Om resultatet är en tom graf, finns det ingen regelbunden cykel i grafen. Annars kan en regelbunden cykel hittas i alla icke-bryggade komponenter. Sökandet efter broar i denna algoritm kan göras effektivt med den dynamiska Sorup-algoritmen [14] . En liknande teknik för att ta bort broar i samband med matchningar övervägdes tidigare av Gabov, Kaplan och Tarjan [15] .

Genomförbarhet

2-tillfredsställbarhetsproblemet , det vill säga ett uttryck i konjunktiv normalform med två variabler eller deras negation, kan omvandlas till en utdatagraf genom att ersätta varje uttryck med två implikationer och . I denna graf representerar varje vertex en variabel eller dess negation, och varje riktad kant representerar en implikation. Grafen är genom konstruktion skevsymmetrisk med en funktion som mappar varje variabel till dess negation. Som Asvall, Plass och Tarjan [16] har visat , är att hitta en tillfredsställande uppsättning värden för en instans av ett 2-tillfredsställelseproblem ekvivalent med att dela upp denna utgångsgraf i två delmängder av hörn, och , så att ingen båge startar kl och slutar kl . Om en sådan uppdelning finns, kan en tillfredsställande uppsättning värden erhållas genom att tilldela ett True-värde till varje variabel i och ett False-värde till varje variabel i . Detta kan göras om och endast om ingen starkt sammankopplad komponent i grafen innehåller både en vertex och dess komplementära vertex . Om två hörn hör till samma starkt sammankopplade komponent, är motsvarande variabler eller deras negationer nödvändigtvis lika med varandra i någon tillfredsställande uppsättning värden för en instans av 2-tillfredsställbarhetsproblemet. Den totala tiden för att kontrollera för stark anslutning och hitta en partition av utdatagrafen är linjär i storleken på ett givet 2-CNF-uttryck.

Erkännande

Problemet med att känna igen om en given riktad graf är skevsymmetrisk är NP-komplett . Detta följer av Lalondes resultat [17] att problemet med att hitta en färgomvänd involution i en tvådelad graf är NP-komplett om och endast om den riktade grafen som ges av orienteringen av varje kant från en färgklass till en annan är skevsymmetrisk . Denna komplexitet påverkar inte sökvägsalgoritmer för skevsymmetriska grafer, eftersom dessa algoritmer antar att den skevsymmetriska strukturen ges som en del av algoritmens indata, snarare än härledd från enbart grafen.

Anteckningar

  1. ↑ 1 2 Tutte, 1967 .
  2. ↑ Zelinka, 1976b .
  3. ↑ 12 Zaslavsky , 1991 .
  4. ↑ 1 2 3 4 Goldberg, Karzanov, 1996 .
  5. ↑ 1 2 Zelinka, 1974 .
  6. ↑ 12 Zelinka , 1976a .
  7. ↑ Växlingsgrafen kommer från representationen av grafen som analog med järnvägsspår, med korsningarna mellan enskilda grenar som växlingspilar.
  8. ↑ 12 Cook , 2003 .
  9. ↑ Hui, Schaefer, Štefankovič, 2004 .
  10. ↑ Edmonds, Johnson, 1970 .
  11. ↑ Zaslavsky, 1991 , sid. Avsnitt 5.
  12. ↑ Babenko, 2006 .
  13. ↑ Goldberg, Karzanov, 2004 .
  14. ↑ Thorup, 2000 .
  15. ↑ Gabow, Kaplan, Tarjan, 1999 .
  16. ↑ Aspvall, Plass, Tarjan, 1979 .
  17. ↑ Lalonde, 1981 .

Litteratur