Bipoláris orientáció

Az irányítatlan gráf bipoláris orientációja vagy st - orientációja  egy orientáció hozzárendelése minden élhez ( orientation ), amely a gráfot irányított aciklikus gráfrá alakítja, egyetlen s forrással és egyetlen t nyelővel , és az st - számozással. a gráf a kapott irányított aciklikus gráf topológiai rendezése [1] [2] .

Definíciók és létezés

Legyen egy irányítatlan gráf csúcsokkal. A G gráf orientációja  egy irány hozzárendelése a G gráf minden éléhez, amely irányított gráfrá alakítja . Egy orientáció aciklikus , ha az eredményül kapott irányított gráfnak nincsenek irányított ciklusai . Bármely aciklikus irányított gráfnak van legalább egy forrása (egy csúcs, amelyből nem jön ki ív) és legalább egy nyelő (olyan csúcs, amelyből nem jön ív). Egy tájolás akkor bipoláris, ha pontosan egy forrás és pontosan egy nyelő van. Bizonyos helyzetekben G megadható a kiválasztott s és t csúcsokkal együtt . Ebben az esetben a bipoláris orientációnak az s -nek kell lennie az egyetlen forrásnak és a t -nek az egyetlen nyelőnek [1] [2] .

A G gráf st -számozása (ismét a két s és t csúcs kiemelve ) az 1-től n -ig terjedő egész számok hozzárendelése a G gráf csúcsaihoz úgy, hogy

Egy gráfnak akkor és csak akkor van bipoláris orientációja, ha van st -számozása. Ha a gráf bipoláris orientációval rendelkezik, akkor st -számozás állítható elő úgy, hogy megkeressük az irányított aciklikus gráf topológiai fajtáját az orientáció alapján, és az egyes csúcsokat a helyzetük szerint számozzuk ebben a sorrendben. Ellenkező irányban bármely st - számozás egy topológiai sorrendet generál, amelyben a G gráf minden éle egy alacsonyabb számú végponttól egy magasabb számú végpont felé orientálódik [1] [2] . Az st élt tartalmazó gráfban egy orientáció akkor és csak akkor bipoláris, ha aciklikus, és az st él megfordításával létrejött orientáció teljesen ciklikus [2] .

Az s és t megkülönböztetett csúcsokkal rendelkező összefüggő G gráf akkor és csak akkor rendelkezik bipoláris orientációval és st számozással, ha a G -ből egy s -ből t -hez egy él hozzáadásával képzett gráf 2-csúccsal kapcsolódik [3] . Egy irányban, ha ez a gráf 2 csúcshoz kapcsolódik, akkor bipoláris orientáció érhető el, ha a gráf füldekompozíciójában minden fület szekvenciálisan orientálunk [ 4 ] . A másik irányban, ha a gráf nem 2-csúccsal összefüggő, akkor van egy v artikuláló csúcsa, amely elválasztja G valamely bi-összekapcsolt komponensét s - től és t -től . Ha ez a komponens v -nél kisebb számú csúcsot tartalmaz , akkor a komponensben lévő legalacsonyabb számú csúcsnak nem lehet kisebb számú szomszédja, és szimmetrikusan, ha v -nél nagyobb számú csúcsot tartalmaz , akkor a legmagasabb- a komponensben lévő számozott csúcsnak nem lehet nagy számú szomszédja.

Alkalmazások a síkságra

Lempel, Even és Zederbaum [3] a síkosság-ellenőrző algoritmus részeként st -számozásokat [3] , míg Rosenstiel [5] és Tarjan [1] a síkgráf csempézési algoritmus részeként [1] a bipoláris orientációt .

A síkgráf bipoláris orientációja egy st - planar gráfot eredményez , egy irányított aciklikus síkgráfot egy forrással és egy nyelővel. Ezek a gráfok fontos szerepet játszanak a rácselméletben , valamint a gráfok megjelenítésében  – a kétdimenziós rács Hasse-diagramja szükségszerűen st -síkú, és bármely tranzitívan redukált st -síkú gráf kétdimenziós rácsot jelent. ilyen módon [6] . Egy irányított aciklikus G gráf akkor és csak akkor rendelkezik növekvő síkbeli ábrázolással , ha a G gráf egy st -síkú gráf részgráfja [7] .

Algoritmusok

Egy adott gráf st - számozása és bipoláris orientációja megkülönböztetett s és t csúcsokkal lineáris időben megkereshető mélységi kereséssel [8] [9] [10] . A Tarjan-féle algoritmus [10] mélységi keresést használ, amely az s csúcsnál kezdődik . Akárcsak a gráf kettős kapcsolatának ellenőrzésére szolgáló mélységi keresési algoritmusban, ez az algoritmus először átad egy pre( v ) értéket a v csúcshoz , amely a v csúcs mélységi áthaladási előrendelési száma , és egy alacsony( v ) számot. , amely a legkisebb előrendelési szám, amelyet úgy lehet elérni, hogy egy mélységi keresési fában egy élt követünk a v -tól. Mindkét szám kiszámolható lineáris időben a mélységi keresés részeként. Egy adott gráf akkor és csak akkor lesz bikapcsolt (és bipoláris orientációjú), ha t az s csúcs egyetlen gyermeke a mélység-első keresési fában, és minden v csúcsra , kivéve az s -t . Miután ezeket a számokat kiszámolta, Tarjan algoritmusa végrehajt egy második df-fa átadást, fenntartva egy számjelet ( v ) minden v csúcshoz, és egy összekapcsolt csúcslistát, amely végül elkészíti a gráf összes csúcsának listáját a megadott sorrendben. a st -számozás. Kezdetben a lista s és t és . Ha az első lépésben v megtalálható, a v bekerül a listába a szülő p( v ) elé vagy után a mélységi keresési fában a jel(low( v )) szerint. Ekkor a jel(p( v )) -jel(low( v )) lesz beállítva . Amint azt Tarjan megmutatta, az ebből az eljárásból származó csúcsok sorrendje adja az adott gráf st -számozását [10] .

Alternatív megoldásként hatékony soros és párhuzamos algoritmusok alapulhatnak füldekompozíción [4] [11] . Egy adott gráf nyitott fülű dekompozíciója megkülönböztetett s és t csúcsokkal úgy definiálható, mint a gráf éleinek partíciója az úgynevezett "füleknek" nevezett útvonalsorozatra, amelyben az első fül végpontjai s és t , a gráf végpontjai minden következő fül a sorozat előző füleihez tartozik, és minden fül minden belső csúcsa először abban a fülben jelenik meg. Nyitott fül dekompozíció akkor és csak akkor létezik, ha az st él összeadásával kapott gráf bikapcsolt (ugyanaz a feltétel, mint a bipoláris orientáció fennállása esetén), és lineáris időben megtalálható. st -A tájolást úgy kaphatjuk meg, hogy minden fülnek megfelelő irányt adunk, ügyelve arra, hogy ha az előző fülben már van egy orientált út, amely ugyanazt a két végpontot köti össze, akkor az új fülnek azonos irányúnak kell lennie. Ennek közvetlen ellenőrzése elérhetőségi számítással azonban lassú lesz. Mahon, Shiber és Vyshkin [4] egy összetett, de lokalizált keresési eljárást adott az egyes fülek megfelelő tájolásának meghatározására, amely (ellentétben a DFS megközelítéssel) alkalmas párhuzamos számításokra [4] .

Papamentow és Tollis [12] algoritmusokat számol be az irányított utak hosszának szabályozására egy adott gráf bipoláris orientációjában, ami viszont egyes gráfvizualizációk hosszának és magasságának szabályozásához vezet [ 12] .

Az összes tájolás tere

A 3-as csúcshoz kapcsolódó, megkülönböztetett s és t csúcsokkal rendelkező gráfok esetén bármely két bipoláris orientáció összekapcsolható egy műveletsorral, amely megfordítja egy ív irányát, minden lépésben megtartva a bipoláris orientációt [2] . Szigorúbban, síkbeli, 3 összekapcsolt gráfok esetén a bipoláris orientációk halmaza megadható egy véges disztributív rács szerkezete a rács [ en] lefedettségi viszonyának megfelelő ív irányának megfordításával 2] . Bármely, dedikált forrással és nyelővel rendelkező gráf esetén az összes bipoláris orientáció halmaza megszámlálható orientációnkénti polinomidőben [2] .

Jegyzetek

  1. ↑ 1 2 3 4 5 6 Pierre Rosentiehl, Robert Tarjan. Síkgráfok egyenes vonalú síkbeli elrendezései és bipoláris orientációi  // Discrete and Computational Geometry . - 1986. - T. 1 , szám. 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. A bipoláris orientációk újralátogatása // Discrete Applied Mathematics. - 1995. - T. 56 , sz. 2-3 . – S. 157–179 . - doi : 10.1016/0166-218X(94)00085-R .
  3. ↑ 1 2 3 4 Abraham Lempel, Shimon Even, Cederbaum I. An algorithm for planarity testing of graphs // 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. Parallel ear decomposition search (EDS) és ST-számozás grafikonokban // Theoretical Computer Science . - 1986. - T. 47 , sz. 3 . - doi : 10.1016/0304-3975(86)90153-2 .
  5. ↑ A Rosentiehl vezetéknév német eredetű, németül Rosenstiel néven olvasható. Magyarul úgy hangzik, mint Rosenstiel
  6. ↑ Platt CR Planar lattices and planar graphs // Journal of Combinatorial Theory . - 1976. - T. 21 , sz. 1 . – S. 30–39 . - doi : 10.1016/0095-8956(76)90024-1 .
  7. ↑ Giuseppe Di Battista, Roberto Tamassia. Algoritmusok aciklikus digráfok síkbeli ábrázolásához // Elméleti számítástechnika . - 1988. - T. 61 , sz. 2-3 . – S. 175–198 . - doi : 10.1016/0304-3975(88)90123-5 .
  8. ↑ Ebert J. st -a bikapcsolt gráfok csúcsainak rendezése // Számítástechnika . - 1983. - T. 30 , sz. 1 . – S. 19–33 . - doi : 10.1007/BF02253293 .
  9. ↑ Shimon Even, Robert Tarjan. Egy st -számozás számítása // Elméleti számítástechnika . - 1976. - 2. évf. , szám. 3 . – S. 339–344 . - doi : 10.1016/0304-3975(76)90086-4 .
  10. ↑ 1 2 3 Robert Tarjan. Két egyszerűsített mélységi keresési algoritmus // Fundamenta Informaticae . - 1986. - T. 9 , sz. 1 . – S. 85–94 .
  11. ↑ Hillel Gazit. Optimális EREW párhuzamos algoritmusok a sík gráfok összekapcsolhatóságához, füldekompozíciójához és st-számozásához // Proc. 5. Nemzetközi Párhuzamos Feldolgozó Szimpózium. - 1991. - S. 84-91. - doi : 10.1109/IPPS.1991.153761 .
  12. ↑ 1 2 Charalampos Papamanthou, Ioannis G. Tollis. Paraméterezett st -orientációk alkalmazásai gráfrajzi algoritmusokban // Graph Drawing: 13th International Symposium, GD 2005, Limerick, Ireland, 2005. szeptember 12–14., Revised Papers . - Berlin: Springer, 2006. - T. 3843. - S. 355–367. — (Számítástechnikai előadásjegyzetek). - doi : 10.1007/11618058_32 .