Bipolaarinen suuntaus

Suuntaamattoman graafin bipolaarinen orientaatio tai st - orientaatio  on orientaation määrittäminen kullekin reunalle ( orientation ), joka muuttaa graafin suunnatuksi asykliseksi graafiksi , jossa on yksi lähde s ja yksi nielu t , ja st -numerointi graafi on topologinen lajittelu tuloksena saadusta suunnatusta asyklisestä graafista [1] [2] .

Määritelmät ja olemassaolo

Antaa olla suuntaamaton graafi, jossa on pisteitä. Graafin G orientaatio on suunnan osoittaminen graafin G  kullekin reunalle , mikä muuttaa sen suunnatuksi graafiksi . Orientaatio on asyklinen , jos tuloksena olevalla suunnatulla graafilla ei ole suunnattuja jaksoja . Jokaisella asyklisellä suunnatulla graafilla on vähintään yksi lähde (piste, josta ei tule kaaria) ja vähintään yksi nielu (kärki, josta ei synny kaaria). Suunta on bipolaarinen, jos siinä on täsmälleen yksi lähde ja tasan yksi nielu. Joissakin tilanteissa G voidaan antaa yhdessä valittujen pisteiden s ja t kanssa . Tässä tapauksessa bipolaarisessa orientaatiossa tulisi olla s ainoana lähteenä ja t :n ainoana nieluna [1] [2] .

Graafin G st -numerointi (jälleen, kaksi kärkeä s ja t korostettuina ) on kokonaislukujen 1 - n osoittaminen graafin G kärkiin siten, että

Graafilla on bipolaarinen suunta silloin ja vain, jos sillä on st -numerointi. Jos graafilla on bipolaarinen orientaatio, niin st -numerointi voidaan muodostaa etsimällä suunnatun asyklisen graafin topologinen lajike orientaatiolla ja numeroimalla jokainen kärki sen sijainnin mukaan tässä järjestyksessä. Päinvastaisessa suunnassa mikä tahansa st -numerointi generoi topologisen järjestyksen, jossa graafin G jokainen reuna on suunnattu pienempinumeroisesta päätepisteestä suurempinumeroiseen päätepisteeseen [1] [2] . Graafissa, joka sisältää reunan st , orientaatio on bipolaarinen silloin ja vain silloin, kun se on asyklinen ja reunan st kääntämisellä muodostettu orientaatio on täysin syklinen [2] .

Yhdistetyllä graafilla G , jolla on erotetut kärjet s ja t , on bipolaarinen orientaatio ja st -numerointi silloin ja vain, jos graafista G , joka on muodostettu lisäämällä reuna s :stä t :hen, on 2-pisteinen [3] . Yhdessä suunnassa, jos tämä graafi on 2-vertex-kytketty, niin bipolaarinen orientaatio voidaan saada orientoimalla peräkkäin kutakin korvaa graafin korvahajotelmassa [ 4] . Toisessa suunnassa, jos graafi ei ole 2-kärkikytketty, niin siinä on artikuloiva kärki v , joka erottaa jonkin G : n bi-kytketyn komponentin s :stä ja t :stä . Jos tämä komponentti sisältää kärjen, jonka lukumäärä on pienempi kuin v , niin komponentin pienimmän numeron pisteellä ei voi olla naapuria, jolla on pienempi luku, ja symmetrisesti, jos se sisältää kärjen, jonka lukumäärä on suurempi kuin v , niin korkein- Komponentin numeroidulla kärjellä ei voi olla naapuria, jolla on suuri numero.

Sovellukset tasomaisuuteen

Lempel, Even ja Zederbaum [3] muotoilivat st - numeroinnin osana tasomaisuuden tarkistusalgoritmia [3] , kun taas Rosenstiel [ 5] ja Tarjan [1] muotoilivat bipolaarisen orientaation osana tasograafin laatoitusalgoritmia [1] .

Tasograafin bipolaarinen orientaatio johtaa st - planaariseen graafiin , joka on suunnattu asyklinen tasograafi, jossa on yksi lähde ja yksi nielu. Näillä kaavioilla on tärkeä rooli hilateoriassa sekä graafien visualisoinnissa  - kaksiulotteisen hilan Hasse-kaavio on välttämättä st -tasoinen, ja mikä tahansa transitiivisesti pelkistetty st -tasograafi edustaa kaksiulotteista hilaa tällä tavalla [6] . Suunnatulla asyklisellä graafilla G on nouseva tasoesitys silloin ja vain, jos graafi G on st - tasograafin aligraafi [7] .

Algoritmit

Tietyn graafin st - numerointi ja bipolaarinen orientaatio voidaan löytää lineaarisessa ajassa käyttämällä syvyyshakua [ 8 ] [ 9] [10] . Tarjanin algoritmi [10] käyttää syvyyshakua, joka alkaa kärjestä s . Kuten syvyys-ensimmäinen hakualgoritmi, jolla tarkistetaan, onko graafi kaksinkertaisesti kytketty, tämä algoritmi välittää ensin arvon pre( v ) kärjelle v , joka on kärjen v syvyyspäästön ennakkotilausnumero , ja luvun alhainen( v ) , joka on pienin ennakkotilausluku, joka voidaan saavuttaa seuraamalla yhtä reunaa v :stä syvyysensimmäisessä hakupuussa. Molemmat näistä luvuista voidaan laskea lineaarisessa ajassa osana syvyyshakua. Tietty graafi on bi-kytketty (ja sillä on bipolaarinen suuntaus) jos ja vain jos t on kärjen s ainoa lapsi syvyysensimmäisessä hakupuussa ja kaikille vertekseille v , paitsi s . Kun nämä luvut on laskettu, Tarjanin algoritmi suorittaa toisen df-puun läpiviennin säilyttäen numeromerkin ( v ) jokaiselle pisteelle v ja linkitetyn pisteluettelon, joka lopulta tuottaa luettelon kaikista graafin pisteistä graafin antamassa järjestyksessä. st -numerointi . Aluksi luettelo sisältää s ja t ja . Kun v löytyy ensimmäisellä kierrolla, v lisätään luetteloon joko ennen tai jälkeen sen emoarvon p( v ) syvyysensimmäisessä hakupuussa merkin(low( v )) mukaisesti. Sitten merkki(p( v )) asetetaan arvoon -sign(low( v )). Kuten Tarjan on osoittanut, tästä proseduurista saatu pisteiden järjestys antaa annetun graafin st -numeroinnin [10] .

Vaihtoehtoisesti tehokkaat sarja- ja rinnakkaisalgoritmit voivat perustua korvadekompositioon [4] [11] . Tietyn graafin avoimen korvan hajotelma, jossa on erotetut kärjet s ja t , voidaan määritellä graafin reunojen jakamiseksi polkujonoksi, jota kutsutaan "korviksi", jossa ensimmäisen korvan päätepisteet ovat s ja t , päätepisteet jokainen seuraava korva kuuluu sarjan edellisiin korviin, ja kunkin korvan jokainen sisäinen kärki näkyy ensin kyseisessä korvassa. Avoimen korvan hajoaminen on olemassa, jos ja vain, jos reunan st lisäämisellä saatu graafi on kaksikytkentäinen (sama ehto kuin bipolaarisen orientaation olemassaololle) ja se löytyy lineaarisessa ajassa. st -Orientaatio voidaan saada antamalla kullekin korvalle sopiva suunta ottaen huomioon, että jos on jo suunnattu polku, joka yhdistää samat kaksi päätepistettä edellisissä korvissa, niin uuden korvan on oltava sama suunta. Tämän tarkastaminen suoraan saavutettavuuslaskelman avulla on kuitenkin hidasta. Mahon, Shiber ja Vyshkin [4] ovat antaneet monimutkaisen mutta paikallisen hakumenettelyn oikean suunnan määrittämiseksi kullekin korvalle, joka (toisin kuin DFS-lähestymistapa) sopii rinnakkaislaskentaan [4] .

Papamentow ja Tollis [12] raportoivat algoritmeja suunnattujen polkujen pituuksien ohjaamiseksi tietyn graafin bipolaarisessa orientaatiossa, mikä puolestaan ​​johtaa joidenkin graafin visualisointien pituuden ja korkeuden säätelyyn [12] .

Kaikkien suuntausten tila

Vertex-3-liitetyissä graafisissa, joissa on erotetut kärjet s ja t , mitkä tahansa kaksi bipolaarista orientaatiota voidaan yhdistää toisiinsa operaatiosarjalla, joka kääntää yhden kaaren suunnan ja säilyttää bipolaarisen orientaation jokaisessa vaiheessa [2] . Tarkemmin sanottuna tasomaisissa 3-liitetyissä graafisissa bipolaaristen orientaatioiden joukolle voidaan antaa äärellisen distributiivisen hilan rakenne, jossa kaaren suunta käännetään vastaten hilan peittosuhdetta [ en 2] . Jokaiselle kuvaajalle, jolla on oma lähde ja nielu, kaikkien bipolaaristen orientaatioiden joukko voidaan laskea polynomiaikana orientaatiota kohden [2] .

Muistiinpanot

  1. ↑ 1 2 3 4 5 6 Pierre Rosentiehl, Robert Tarjan. Tasograafien suoraviivaiset tasomaiset asettelut ja kaksinapaiset orientaatiot  // Diskreetti ja laskennallinen geometria . - 1986. - T. 1 , numero. 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. Kaksisuuntaiset suuntaukset uudelleen // Discrete Applied Mathematics. - 1995. - T. 56 , no. 2-3 . — S. 157–179 . - doi : 10.1016/0166-218X(94)00085-R .
  3. ↑ 1 2 3 4 Abraham Lempel, Shimon Even, Cederbaum I. Algoritmi graafien tasomaisuustestaukseen // Theory of Graphs (Internat. Sympos., Rooma, 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) ja ST-numerointi kaavioissa // Theoretical Computer Science . - 1986. - T. 47 , no. 3 . - doi : 10.1016/0304-3975(86)90153-2 .
  5. ↑ Sukunimi Rosentiehl on saksalaista alkuperää ja saksaksi se luetaan nimellä Rosenstiel. Englanniksi se saattaa kuulostaa Rosenstieliltä
  6. ↑ Platt CR Tasomaiset hilat ja tasograafit // Journal of Combinatorial Theory . - 1976. - T. 21 , no. 1 . - S. 30-39 . - doi : 10.1016/0095-8956(76)90024-1 .
  7. ↑ Giuseppe Di Battista, Roberto Tamassia. Asyklisten digrafien tasoesitysten algoritmit // Tietojenkäsittelyteoria . - 1988. - T. 61 , no. 2-3 . — S. 175–198 . - doi : 10.1016/0304-3975(88)90123-5 .
  8. ↑ Ebert J. st -kaksikytkentäisten graafien kärkien järjestys // Computing . - 1983. - T. 30 , no. 1 . - S. 19-33 . - doi : 10.1007/BF02253293 .
  9. ↑ Shimon Even, Robert Tarjan. St -numeroinnin laskeminen // Tietojenkäsittelyteoria . - 1976. - Osa 2 , numero. 3 . — S. 339–344 . - doi : 10.1016/0304-3975(76)90086-4 .
  10. ↑ 1 2 3 Robert Tarjan. Kaksi virtaviivaista syvyys-ensin hakualgoritmia // Fundamenta Informaticae . - 1986. - T. 9 , no. 1 . — S. 85–94 .
  11. ↑ Hillel Gazit. Optimaaliset EREW-rinnakkaisalgoritmit tasokaavioiden liitettävyydelle, korvahajotelle ja st-numerointiin // Proc. 5th International Parallel Processing Symposium. - 1991. - S. 84-91. - doi : 10.1109/IPPS.1991.153761 .
  12. ↑ 1 2 Charalampos Papamanthou, Ioannis G. Tollis. Parametrisoitujen st -orientaatioiden sovellukset graafinpiirtoalgoritmeissa // Graph Drawing: 13th International Symposium, GD 2005, Limerick, Ireland, September 12–14, 2005, Revised Papers . - Berliini: Springer, 2006. - T. 3843. - S. 355-367. — (Luentomuistiinpanot tietojenkäsittelytieteestä). - doi : 10.1007/11618058_32 .