St-tasograafi

St - tasograafi on tasograafin bipolaarinen orientaatio, jossa sekä orientaation lähde että nielu ovat graafin ulkopinnalla. Eli se on suunnattu graafi, joka on piirretty ilman leikkauspisteitä tasolle siten, että graafissa ei ole suunnattuja jaksoja, tarkalleen yhdessä graafin kärjessä ei ole sisääntulokaaria, tarkalleen yhdessä graafin kärjessä ei ole lähteviä kaaria, ja molemmat nämä kaksi erityistä kärkeä sijaitsevat ulkopinnan sarakkeessa [1] .

Piirustuksessa graafin jokaisella pinnalla on oltava sama rakenne - on yksi kärki, joka toimii kasvojen lähteenä, yksi kärki toimii kasvojen nieluna ja kaikki kasvojen sisällä olevat reunat on suunnattu kahta polkua pitkin lähde pesualtaaseen. Jos piirretään lisäreuna st -tasograafin nielusta takaisin lähteeseen ulkopintaa pitkin ja sitten muodostetaan duaaligraafi ( suuntaamalla jokainen kaksoisreuna myötäpäivään suhteessa alkuperäiseen reunaan), niin saadaan taas st -taso. graafia laajennettu lisäreunalla samalla tavalla [1 ] .

Tilausteoria

Nämä graafit liittyvät läheisesti osittain järjestyneisiin joukkoihin ja hiloihin . Posetin Hasse-diagrammi on suunnattu asyklinen graafi, jonka kärjet ovat joukko elementtejä, joissa on reuna x :stä y :ään jokaiselle parille x , y elementeille, joilla on osittainen järjestys, mutta joille ei ole z :tä. c . Poset muodostaa täydellisen hilan, jos ja vain jos jollakin elementtien osajoukolla on yksi suurin alaraja ja yksi pienin yläraja, ja posetin järjestysmitta on pienin määrä lineaarisia järjestettyjä joukkoja samassa joukossa. elementtejä, joiden leikkauspiste on annettu osajärjestys. Jos st -tasograafin kärjet ovat osittain saavutettavissa olevaa järjestystä, niin tämä järjestys muodostaa aina kaksiulotteisen täydellisen hilan, jonka Hasse-kaavio on annetun graafin transitiivinen supistuminen . Sitä vastoin minkä tahansa kaksiulotteisen täydellisen hilan Hasse-diagrammi on aina st - tasograafi [2] .

Kaavioiden piirtäminen

Tämän kaksiulotteisen osittaisen järjestyksen ominaisuuden perusteella mikä tahansa st -tasograafi voidaan esittää hallitsevana kuviona , jossa jokaiselle kahdelle kärjelle u ja v on polku u :sta v :iin, jos ja vain jos molemmat koordinaatit u ovat pienempi kuin, kuin vastaavat koordinaatit v [3] . Tällaisen piirustuksen koordinaatteja voidaan käyttää tietorakenteena , jolla voidaan tarkistaa, että st -tasograafin kärjestä on mahdollista saavuttaa toinen kärki vakioajassa per pyyntö. Kuvaa kiertämällä 45° saadaan kaaviosta nouseva tasoesitys . Suunnatulla asyklisellä graafilla G on nouseva tasoesitys silloin ja vain, jos G on st - tasograafin aligraafi [4] .

Muistiinpanot

1. ↑ 1 2 Giuseppe Di Battista, Peter Eades, Roberto Tamassia, Ioannis G. Tollis. 4.2 Tasomaisten asyklisten digrafien ominaisuudet // Graafipiirustus: Algoritmit graafien visualisoimiseksi. - Prentice Hall , 1998. - S. 89-96. — ISBN 978-0-13-301615-4 . .
2. ↑ 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 . .
3. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , s. 112–127 §4.7 Dominanssipiirrokset.
4. ↑ Giuseppe Di Battista, Roberto Tamassia. Asyklisten digrafien tasoesitysten algoritmit // Tietojenkäsittelyteoria . - 1988. - T. 61 , no. 2-3 . - doi : 10.1016/0304-3975(88)90123-5 . .