Bipolar orientering

Den bipolære orientering eller st - orientering af en urettet graf er tildelingen af en orientering til hver kant ( orientering ), som gør grafen til en rettet acyklisk graf med en enkelt kilde s og en enkelt synk t , og st -nummereringen af grafen er en topologisk sortering af den resulterende rettede acykliske graf [1] [2] .

Definitioner og eksistens

Lade være en urettet graf med toppunkter. Orienteringen af en graf G er tildelingen af en retning til hver kant af grafen G , hvilket gør den til en rettet graf . En orientering er acyklisk , hvis den resulterende rettede graf ikke har nogen rettede cyklusser . Enhver acyklisk rettet graf har mindst én kilde (en top, hvorfra ingen buer kommer ind) og mindst én sink (en top, hvorfra ingen buer stammer). En orientering er bipolær, hvis der er præcis én kilde og præcis én vask. I nogle situationer kan G gives sammen med udvalgte toppunkter s og t . I dette tilfælde bør den bipolære orientering have s som eneste kilde og t som eneste synk [1] [2] . $G=(V,E)$ $n=|V|$

St -nummereringen af grafen G (igen, med de to toppunkter s og t fremhævet ) er tildelingen af heltal fra 1 til n til toppunkterne på grafen G , således at

alle hjørner får forskellige tal,
node s er tildelt nummer 1,
node t er tildelt nummer n ,
hvis node v tildeles nummer i ( ), så tildeles mindst én nabo til v et tal mindre end i , og én nabo tildeles et nummer større end [1] [2] [3] . $1<i<n$

En graf har en bipolær orientering, hvis og kun hvis den har en st -nummerering. Hvis grafen har en bipolær orientering, kan en st -nummerering konstrueres ved at finde den topologiske slags af den rettede acykliske graf givet orienteringen, og nummerere hvert toppunkt i henhold til dets position i den rækkefølge. I den modsatte retning genererer enhver st -nummerering en topologisk rækkefølge, hvor hver kant af grafen G er orienteret fra et lavere nummereret endepunkt til et højere nummereret endepunkt [1] [2] . I en graf, der indeholder kantst , er en orientering bipolær, hvis og kun hvis den er acyklisk, og orienteringen dannet ved at vende kantst er fuldstændig cyklisk [2] .

En forbundet graf G med adskilte toppunkter s og t har en bipolær orientering og st -nummerering, hvis og kun hvis grafen dannet ud fra G ved at tilføje en kant fra s til t er 2-vertex-forbundet [3] . I én retning, hvis denne graf er 2-vertex-forbundet, så kan en bipolær orientering opnås ved sekventielt at orientere hvert øre i ørenedbrydningen af grafen [4] . I den anden retning, hvis grafen ikke er 2-vertex-forbundet, så har den et artikulerende toppunkt v , der adskiller en eller anden bi-forbundet komponent af G fra s og t . Hvis denne komponent indeholder et toppunkt med et lavere tal end v , så kan det lavest nummererede toppunkt i komponenten ikke have en nabo med et lavere tal, og symmetrisk, hvis den indeholder et toppunkt med et højere tal end v , så er den højeste- nummereret toppunkt i komponenten kan ikke have nabo med et stort tal.

Ansøgninger til planaritet

Lempel, Even og Zederbaum [3] formulerede st -nummereringer som en del af planaritetskontrolalgoritmen [ 3 ] , mens Rosenstiel [5] og Tarjan [1] formulerede bipolær orientering som en del af den plane grafflisealgoritme [1] .

Den bipolære orientering af en plan graf resulterer i en st - plan graf , en rettet acyklisk plan graf med én kilde og én synk. Disse grafer spiller en vigtig rolle i gitterteori såvel som i visualisering af grafer - Hasse-diagrammet af et todimensionalt gitter er nødvendigvis st -plan, og enhver transitivt reduceret st -plan graf repræsenterer et todimensionalt gitter på denne måde [6] . En rettet acyklisk graf G har en stigende plan repræsentation, hvis og kun hvis grafen G er en undergraf til en st -plan graf [7] .

Algoritmer

Man kan finde st -nummereringen og den bipolære orientering af en given graf med adskilte hjørner s og t i lineær tid ved at bruge dybde-først søgning [8] [9] [10] . Tarjans algoritme [10] bruger en dybde-først søgning, der starter ved toppunktet s . Som i dybde-først søgealgoritmen til at kontrollere, om en graf er dobbelt forbundet, sender denne algoritme først en værdi pre( v ) for vertex v , som er dybdepass- forudbestillingsnummeret for vertex v , og et tal lavt ( v ) , som er det mindste forudbestillingsnummer, der kan opnås ved at følge en kant fra v i et dybde-først søgetræ. Begge disse tal kan beregnes i lineær tid som en del af en dybde-først-søgning. En given graf vil være bi-forbundet (og have en bipolær orientering), hvis og kun hvis t er det eneste underordnede af et toppunkt s i dybde-første søgetræet og for alle hjørner v bortset fra s . Når disse tal er blevet beregnet, udfører Tarjans algoritme en anden df-træ-passage, idet den opretholder et taltegn( v ) for hvert vertex v og en sammenkædet liste over knudepunkter, der til sidst producerer en liste over alle knudepunkter i grafen i rækkefølgen givet af st -nummereringen . Til at begynde med indeholder listen s og t og . Når v findes på det første gennemløb, indsættes v i listen enten før eller efter dets overordnede p( v ) i dybde-første søgetræet i henhold til tegn(low( v )). Derefter sættes sign(p( v )) til -sign(low( v )). Som vist af Tarjan giver den resulterende rækkefølge af hjørner fra denne procedure st -nummereringen af den givne graf [10] . $\mathrm {lav} (v)<\mathrm {pre} (v)$ $\mathrm {tegn} (s)=-1$

Alternativt kan effektive serielle og parallelle algoritmer være baseret på ørenedbrydning [4] [11] . En åben ørenedbrydning af en given graf med adskilte toppunkter s og t kan defineres som en opdeling af grafens kanter i en sekvens af stier kaldet "ører", hvor endepunkterne af det første øre er s og t , endepunkterne for hvert næste øre hører til de foregående ører i sekvensen, og hvert indre hjørne af hvert øre vises først i det øre. En åben ørenedbrydning eksisterer, hvis og kun hvis grafen opnået ved at tilføje kantst er biforbundet (samme betingelse som for eksistensen af en bipolær orientering) og kan findes i lineær tid. st -Orientering kan opnås ved at give en passende retning for hvert øre, idet man tager den forholdsregel, at hvis der allerede er en orienteret sti, der forbinder de samme to endepunkter i de tidligere ører, så skal det nye øre have samme retning. Det vil dog være langsomt at kontrollere dette direkte med en tilgængelighedsberegning . Mahon, Shiber og Vyshkin [4] har givet en kompleks, men lokaliseret søgeprocedure til at bestemme den passende orientering for hvert øre, som (i modsætning til DFS-tilgangen) er velegnet til parallel databehandling [4] .

Papamentow og Tollis [12] rapporterer algoritmer til at kontrollere længderne af rettede veje i en bipolær orientering af en given graf, hvilket igen fører til kontrol for længden og højden af nogle grafvisualiseringer [12] .

Rummet for alle orienteringer

For vertex-3-forbundne grafer med adskilte toppunkter s og t , kan alle to bipolære orienteringer forbindes med hinanden ved en sekvens af operationer, der vender retningen af en bue, og bibeholder den bipolære orientering ved hvert trin [2] . Mere strengt, for plane 3-forbundne grafer, kan sættet af bipolære orienteringer gives strukturen af et endeligt distributivt gitter med operationen med at vende retningen af buen svarende til dækningsrelationen gitteret [ en] 2] . For enhver graf med en dedikeret kilde og synk kan sættet af alle bipolære orienteringer opregnes i polynomisk tid pr. orientering [2] .

Noter

↑ 1 2 3 4 5 6 Pierre Rosentiehl, Robert Tarjan. Retlineære plane layouts og bipolære orienteringer af plane grafer // Diskret og beregningsgeometri . - 1986. - T. 1 , udg. 4 . — S. 343–353 . - doi : 10.1007/BF02187706 . .
↑ 1 2 3 4 5 6 7 8 Hubert de Fraysseix, Patrice Ossona de Mendez, Pierre. Bipolære orienteringer revisited // Diskret anvendt matematik. - 1995. - T. 56 , no. 2-3 . — S. 157–179 . - doi : 10.1016/0166-218X(94)00085-R .
↑ 1 2 3 4 Abraham Lempel, Shimon Even, Cederbaum I. En algoritme til planaritetstest af grafer // Theory of Graphs (Internat. Sympos., Rom, 1966). - New York: Gordon and Breach, 1967. - S. 215-232.
↑ 1 2 3 4 Maon Y., Schieber B., Vishkin U. Parallel ørenedbrydningssøgning (EDS) and ST-numbering in graphs // Theoretical Computer Science . - 1986. - T. 47 , no. 3 . - doi : 10.1016/0304-3975(86)90153-2 .
↑ Efternavnet Rosentiehl er af tysk oprindelse og på tysk læses det som Rosenstiel. På engelsk kan det lyde som Rosenstiel
↑ Platt CR Plane gitter og plane grafer // Journal of Combinatorial Theory . - 1976. - T. 21 , no. 1 . — S. 30–39 . - doi : 10.1016/0095-8956(76)90024-1 .
↑ Giuseppe Di Battista, Roberto Tamassia. Algoritmer til planrepræsentationer af acykliske digrafer // Teoretisk datalogi . - 1988. - T. 61 , no. 2-3 . — S. 175–198 . - doi : 10.1016/0304-3975(88)90123-5 .
↑ Ebert J. st -ordner hjørnerne af toforbundne grafer // Computing . - 1983. - T. 30 , no. 1 . — S. 19–33 . - doi : 10.1007/BF02253293 .
↑ Shimon Even, Robert Tarjan. Beregning af en st -nummerering // Teoretisk datalogi . - 1976. - Bind 2 , udgave. 3 . — S. 339–344 . - doi : 10.1016/0304-3975(76)90086-4 .
↑ 1 2 3 Robert Tarjan. To strømlinede dybde-først søgealgoritmer // Fundamenta Informaticae . - 1986. - T. 9 , no. 1 . — S. 85–94 .
↑ Hillel Gazit. Optimale EREW parallelle algoritmer til forbindelse, ørenedbrydning og st-nummerering af plane grafer // Proc. 5. Internationale Parallel Processing Symposium. - 1991. - S. 84-91. - doi : 10.1109/IPPS.1991.153761 .
↑ 1 2 Charalampos Papamanthou, Ioannis G. Tollis. Anvendelser af parametriserede st -orienteringer i graftegningsalgoritmer // Graph Drawing: 13th International Symposium, GD 2005, Limerick, Ireland, September 12-14, 2005, Revised Papers . - Berlin: Springer, 2006. - T. 3843. - S. 355–367. — (Forelæsningsnotater i datalogi). - doi : 10.1007/11618058_32 .