St-sík gráf

Az st - planar gráf egy sík gráf bipoláris orientációja, amelynél az orientáció forrása és nyelője is a gráf külső oldalán található. Azaz egy irányított gráf, amely metszéspontok nélkül van megrajzolva a síkon úgy, hogy a gráfban nincsenek irányított ciklusok, pontosan a gráf egy csúcsának nincs bemeneti íve, pontosan egy csúcsának nincs kimenő íve, és ez a két speciális csúcs a külső homlokoszlopon fekszik [1] .

A rajzon a gráf minden oldalának azonos szerkezetűnek kell lennie - van egy csúcs, amely az arc forrásaként szolgál, egy csúcs az arc nyelőjeként szolgál, és a lapon belüli összes él két út mentén irányul a forrás a mosogatóhoz. Ha az st -sík gráf nyelőjéből egy további élt rajzolunk vissza a forráshoz a külső felület mentén, majd megszerkesztjük a duális gráfot (minden kettős élt az óramutató járásával megegyező irányba orientálva az eredeti élhez képest), akkor ismét egy st -síkú gráfot kapunk. ugyanígy további éllel bővített gráf [1 ] .

Rendelmélet

Ezek a gráfok szorosan kapcsolódnak részlegesen rendezett halmazokhoz és rácsokhoz . Egy poset Hasse-diagramja egy irányított aciklikus gráf, amelynek csúcsai azon elemek halmaza, amelyekben minden x párnak van egy éle x -től y- ig , y olyan elemeknek , amelyeknek van részleges sorrendje, de nincs z . c . Egy póz akkor és csak akkor alkot teljes rácsot, ha az elemek bármely részhalmazának egyetlen legnagyobb alsó és egyetlen legkisebb felső korlátja van, és a poset ordinális dimenziója a legkisebb számú lineárisan rendezett halmaz ugyanazon a halmazon. olyan elemek, amelyek metszéspontja az adott részrend. Ha egy st -sík gráf csúcsai részben elérhető-rendezettek, akkor ez a rendezés mindig egy kétdimenziós teljes rácsot alkot, amelynek Hasse-diagramja az adott gráf tranzitív összehúzódása . Ezzel szemben bármely kétdimenziós teljes rács Hasse-diagramja mindig egy st - sík gráf [2] .

Grafikonok rajzolása

E kétdimenziós részleges rend tulajdonság alapján bármely st -sík gráf ábrázolható domináns mintaként , amelyben minden két u és v csúcsra akkor és csak akkor van út u -ból v -be , ha mindkét u koordináta kisebb, mint a megfelelő koordináták v [3] . Egy ilyen rajz koordinátái felhasználhatók adatstruktúraként , amellyel ellenőrizhető, hogy egy st -sík gráf csúcsából kérésenként konstans időben el lehet-e érni egy másik csúcsot . Az ábra 45°-kal történő elforgatása a grafikon növekvő síkbeli ábrázolását eredményezi. Egy irányított aciklikus G gráf akkor és csak akkor rendelkezik növekvő síkbeli ábrázolással , ha G egy st -síkú gráf részgráfja [4] .

Jegyzetek

1. ↑ 1 2 Giuseppe Di Battista, Peter Eades, Roberto Tamassia, Ioannis G. Tollis. 4.2 A síkbeli aciklikus digráfok tulajdonságai // Grafikonrajz: Grafikonok megjelenítésének algoritmusai. - Prentice Hall , 1998. - S. 89-96. — ISBN 978-0-13-301615-4 . .
2. ↑ 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 . .
3. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , p. 112–127. §4.7 Dominanciarajzok.
4. ↑ 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 . - doi : 10.1016/0304-3975(88)90123-5 . .