Bipolär orientering

Den bipolära orienteringen eller st - orienteringen av en oriktad graf  är tilldelningen av en orientering till varje kant ( orientering ), vilket förvandlar grafen till en riktad acyklisk graf med en enda källa s och en enda sänkning t , och st -numreringen av grafen är en topologisk sortering av den resulterande riktade acykliska grafen [1] [2] .

Definitioner och existens

Låta vara en oriktad graf med hörn. Orienteringen av en graf G  är tilldelningen av en riktning till varje kant av grafen G , vilket gör den till en riktad graf . En orientering är acyklisk om den resulterande riktade grafen inte har några riktade cykler . Varje acykliskt riktad graf har minst en källa (en vertex från vilken inga bågar kommer in) och minst en sänka (en vertex från vilken inga bågar kommer). En orientering är bipolär om det finns exakt en källa och exakt en sänka. I vissa situationer kan G ges tillsammans med valda hörn s och t . I detta fall bör den bipolära orienteringen ha s som enda källa och t som enda sänka [1] [2] .

St -numreringen av grafen G (återigen, med de två hörnen s och t markerade ) är tilldelningen av heltal från 1 till n till hörnen i grafen G så att

En graf har en bipolär orientering om och endast om den har en st -numrering. Om grafen har en bipolär orientering, kan en st -numrering konstrueras genom att hitta den topologiska sorten av den riktade acykliska grafen givet orienteringen och numrera varje vertex enligt dess position i den ordningen. I motsatt riktning genererar varje st -numrering en topologisk ordning i vilken varje kant av grafen G är orienterad från en lägre numrerad slutpunkt till en högre numrerad slutpunkt [1] [2] . I en graf som innehåller kantst är en orientering bipolär om och endast om den är acyklisk och orienteringen som bildas genom att vända kantst är helt cyklisk [2] .

En sammankopplad graf G med distingerade hörn s och t har en bipolär orientering och st -numrering om och endast om grafen som bildas av G genom att lägga till en kant från s till t är 2-vertexkopplad [3] . I en riktning, om denna graf är 2-vertex-ansluten, kan en bipolär orientering erhållas genom att sekventiellt orientera varje öra i öronupplösningen av grafen [4] . I den andra riktningen, om grafen inte är 2-vertex-ansluten, så har den en artikulerande vertex v som separerar någon dubbelkopplad komponent av G från s och t . Om denna komponent innehåller en vertex med ett lägre tal än v , kan den lägsta numrerade vertexen i komponenten inte ha en granne med ett lägre tal, och symmetriskt, om den innehåller en vertex med ett högre tal än v , då den högsta- numrerad vertex i komponenten kan inte ha granne med ett stort tal.

Applikationer till planaritet

Lempel, Even och Zederbaum [3] formulerade st -numrering som en del av planaritetskontrollalgoritmen [ 3] , medan Rosenstiel [5] och Tarjan [1] formulerade bipolär orientering som en del av algoritmen för planar grafplattor [1] .

Den bipolära orienteringen av en plan graf resulterar i en st -planär graf , en riktad acyklisk plan graf med en källa och en sjunka. Dessa grafer spelar en viktig roll i gitterteorin , såväl som i visualisering av grafer  - Hasse-diagrammet för ett tvådimensionellt gitter är nödvändigtvis st -planar, och varje transitivt reducerad st -planar graf representerar ett tvådimensionellt gitter på detta sätt [6] . En riktad acyklisk graf G har en stigande plan representation om och endast om grafen G är en subgraf till en st -planär graf [7] .

Algoritmer

Man kan hitta st -numreringen och den bipolära orienteringen för en given graf med distingerade hörn s och t i linjär tid genom att använda djup-först-sökning [8] [9] [10] . Tarjans algoritm [10] använder en djup-först-sökning som börjar vid vertex s . Liksom i sökalgoritmen för djup-först för att kontrollera om en graf är dubbelkopplad, skickar denna algoritm först ett värde pre( v ) för vertex v , vilket är djuppass- förbeställningsnumret för vertex v , och ett tal lågt ( v ) , vilket är det minsta förbeställningsnummer som kan uppnås genom att följa en kant från v i ett djup-först sökträd. Båda dessa tal kan beräknas i linjär tid som en del av en djup-först-sökning. En given graf kommer att vara dubbelkopplad (och ha en bipolär orientering) om och endast om t är det enda underordnade av ett hörn s i djupet-första sökträdet och för alla hörn v andra än s . När dessa siffror väl har beräknats utför Tarjans algoritm en andra df-trädpassering, och bibehåller ett taltecken( v ) för varje vertex v och en länkad lista med hörn som så småningom ger en lista över alla hörn i grafen i den ordning som ges av st -numreringen . Till en början innehåller listan s och t och . När v hittas vid det första passet, infogas v i listan antingen före eller efter dess överordnade p( v ) i sökträdet djup-först enligt tecken(låg( v )). Sedan sätts sign(p( v )) till -sign(low( v )). Som visas av Tarjan ger den resulterande ordningen av hörn från denna procedur st -numreringen av den givna grafen [10] .

Alternativt kan effektiva seriella och parallella algoritmer baseras på öronnedbrytning [4] [11] . En öppen öronupplösning av en given graf med distingerade hörn s och t kan definieras som en uppdelning av grafens kanter i en sekvens av banor som kallas "öron", där ändpunkterna för det första örat är s och t , ändpunkterna för varje nästa öra tillhör de föregående öronen i sekvensen, och varje inre hörn av varje öra dyker först upp i det örat. En sönderdelning av öppet öra existerar om och endast om grafen som erhålls genom att addera kantst är dubbelkopplad (samma villkor som för förekomsten av en bipolär orientering) och kan hittas i linjär tid. st -Orientering kan erhållas genom att ge en lämplig riktning för varje öra, med försiktighetsåtgärden att om det redan finns en orienterad bana som förbinder samma två ändpunkter i de tidigare öronen, så måste det nya örat ha samma riktning. Att kontrollera detta direkt med en nåbarhetsberäkning kommer dock att gå långsamt. Mahon, Shiber och Vyshkin [4] har gett en komplex men lokaliserad sökprocedur för att bestämma lämplig orientering för varje öra, som (till skillnad från DFS-metoden) är lämplig för parallell beräkning [4] .

Papamentow och Tollis [12] rapporterar algoritmer för att styra längden på riktade banor i en bipolär orientering av en given graf, vilket i sin tur leder till kontroll för längden och höjden på vissa grafvisualiseringar [12] .

Utrymmet för alla orienteringar

För vertex-3-kopplade grafer med distingerade hörn s och t , ​​kan två valfria bipolära orienteringar kopplas till varandra genom en sekvens av operationer som vänder om riktningen för en båge och bibehåller den bipolära orienteringen vid varje steg [2] . Mer strikt, för plana 3-kopplade grafer, kan uppsättningen av bipolära orienteringar ges strukturen av ett ändligt fördelningsgitter med operationen att vända riktningen på bågen som motsvarar täckningsrelationen gittret [ en] 2] . För vilken graf som helst med en dedikerad källa och sänka kan uppsättningen av alla bipolära orienteringar räknas upp i polynomtid per orientering [2] .

Anteckningar

  1. ↑ 1 2 3 4 5 6 Pierre Rosentiehl, Robert Tarjan. Riktlinjiga plana layouter och bipolära orienteringar av plana grafer  // Diskret och beräkningsgeometri . - 1986. - T. 1 , nummer. 4 . — S. 343–353 . - doi : 10.1007/BF02187706 . .
  2. ↑ 1 2 3 4 5 6 7 8 Hubert de Fraysseix, Patrice Ossona de Mendez, Pierre. Bipolära orienteringar återbesökt // Diskret tillämpad matematik. - 1995. - T. 56 , nr. 2-3 . — S. 157–179 . - doi : 10.1016/0166-218X(94)00085-R .
  3. ↑ 1 2 3 4 Abraham Lempel, Shimon Even, Cederbaum I. En algoritm för planaritetstestning av grafer // Theory of Graphs (Internat. Sympos., Rome, 1966). - New York: Gordon and Breach, 1967. - S. 215-232.
  4. ↑ 1 2 3 4 Maon Y., Schieber B., Vishkin U. Parallell öronnedbrytningssökning (EDS) och ST-numrering i grafer // Teoretisk datavetenskap . - 1986. - T. 47 , nr. 3 . - doi : 10.1016/0304-3975(86)90153-2 .
  5. ↑ Efternamnet Rosentiehl är av tyskt ursprung och på tyska läses det som Rosenstiel. På engelska kan det låta som Rosenstiel
  6. ↑ Platt CR Plana gitter och plana grafer // Journal of Combinatorial Theory . - 1976. - T. 21 , nr. 1 . — S. 30–39 . - doi : 10.1016/0095-8956(76)90024-1 .
  7. ↑ Giuseppe Di Battista, Roberto Tamassia. Algoritmer för planrepresentationer av acykliska digrafer // Teoretisk datavetenskap . - 1988. - T. 61 , nr. 2-3 . — S. 175–198 . - doi : 10.1016/0304-3975(88)90123-5 .
  8. ↑ Ebert J. st -ordning av hörn av bikopplade grafer // Computing . - 1983. - T. 30 , nr. 1 . — S. 19–33 . - doi : 10.1007/BF02253293 .
  9. ↑ Shimon Even, Robert Tarjan. Beräkna en st -numrering // Teoretisk datavetenskap . - 1976. - Vol. 2 , nummer. 3 . — S. 339–344 . - doi : 10.1016/0304-3975(76)90086-4 .
  10. ↑ 1 2 3 Robert Tarjan. Två strömlinjeformade djup-först sökalgoritmer // Fundamenta Informaticae . - 1986. - T. 9 , nr. 1 . — S. 85–94 .
  11. ↑ Hillel Gazit. Optimala EREW parallella algoritmer för anslutning, öronupplösning och st-numrering av plana grafer // Proc. 5:e internationella symposiet för parallell bearbetning. - 1991. - S. 84-91. - doi : 10.1109/IPPS.1991.153761 .
  12. ↑ 1 2 Charalampos Papamanthou, Ioannis G. Tollis. Tillämpningar av parametriserade st -orienteringar i grafritningsalgoritmer // Graph Drawing: 13th International Symposium, GD 2005, Limerick, Irland, 12–14 september 2005, Revised Papers . - Berlin: Springer, 2006. - T. 3843. - S. 355–367. — (Föreläsningsanteckningar i datavetenskap). - doi : 10.1007/11618058_32 .