Asyklinen orientaatio

Suuntaamattoman graafin asyklinen orientaatio on suunnan osoittamista kullekin reunalle ( orientaatiolle ), jossa ei muodostu suunnattua sykliä , ja siksi tällainen orientaatio muuttaa graafin suunnatuksi asykliseksi graafiksi . Jokaisella graafilla on asyklinen suuntaus.

Minkä tahansa graafin kromaattinen luku on yhtä suuri kuin maksimipolun minimipituus kaikkien asyklisten suuntausten joukossa. Asykliset orientaatiot liittyvät väritykseen kromaattisen polynomin avulla, joka laskee sekä asykliset orientaatiot että värjäykset. Tasokaavioissa asykliset orientaatiot ovat täysin syklisten orientaatioiden kaksoiskaavioita ja päinvastoin. Tietyn graafin asyklisten orientaatioiden joukolle voidaan antaa osakuution rakenne , jossa kaksi syklistä orientaatiota on vierekkäin, jos ne eroavat vain yhden reunan suunnasta.

Puiden suuntaukset ovat aina asyklisiä ja ovat monipuita . Täydellisten kaavioiden asyklisiä suuntauksia kutsutaan transitiivisiksi turnauksiksi . Bipolaariset suuntaukset ovat asyklisten suuntausten erikoistapauksia, joissa on täsmälleen yksi lähde ja yksi nielu. Kaikki transitiivinen turnaus on kaksinapainen.

Rakentaminen

Jokaisella graafilla on asyklinen suuntaus. Yksi tapa luoda asyklisiä orientaatioita on järjestää kärjet ja sitten orientoida jokainen reuna luettelon aikaisimmasta kärjestä viimeisimpään. Piikkien sekvenssistä tulee sitten tuloksena olevan suunnatun asyklisen graafin (DAG) topologinen järjestys , ja mikä tahansa tämän DAG:n topologinen lajittelu muodostaa saman suuntauksen.

Koska millä tahansa OAG:lla on topologinen lajittelu, mikä tahansa asyklinen orientaatio voidaan saada tällä tavalla. Erilaiset kärkisekvenssit voivat kuitenkin johtaa samoihin asyklisiin orientaatioihin, jos tuloksena olevalla OAG:lla on useita topologisia lajikkeita. Esimerkiksi syklissä , jossa on neljä kärkeä (näkyy kuvassa), on 24 erilaista sekvenssiä, mutta vain 14 mahdollista asyklistä orientaatiota.

Linkki väritykseen

Gallai-Hasse-Roy-Vitaver-lause sanoo, että graafilla on asyklinen orientaatio, jossa maksimipolulla on enintään k kärkeä, jos ja vain jos graafi voidaan värjätä enintään k värillä [1] .

Asyklisten orientaatioiden lukumäärä voidaan laskea käyttämällä kromaattista polynomia , jonka arvo positiiviselle kokonaisluvulle k on yhtä suuri kuin graafin k -väritysten lukumäärä. Millä tahansa graafilla G on täsmälleen erilaiset asykliset orientaatiot [2] , joten tässä mielessä asykliset orientaatiot voidaan ymmärtää värityksenä −1 värillä. ${\näyttötyyli \chi _{G}}$ $|\chi _{G}(-1)|$

Kaksinaisuus

Tasokaavioissa asykliset orientaatiot ovat kaksois- tai täysin syklisiä orientaatioita , orientaatioita, joissa jokainen reuna kuuluu suunnattuun sykliin - if on tasograafi , ja orientaatiot muunnetaan kaksoisgraafin orientaatioiksi kiertämällä kutakin reunaa 90 astetta myötäpäivään, sitten täysin syklinen graafin orientaatio vastaa näin saadun kaksoisgraafin asyklistä orientaatiota ja päinvastoin [3] . $G$ $G$ $G$ $G$

Kuten kromaattista polynomia, myös Tatta-graafipolynomia voidaan käyttää asyklisten orientaatioiden lukumäärän laskemiseen . Tasograafien asyklisten ja täysin syklisten suuntausten välinen kaksinaisuus voidaan laajentaa samalla tavalla ei-tasograafisiin graafisiin — tasograafin kaksoisgraafin Tutt-polynomi saadaan vaihtamalla polynomin argumentteja ja graafin täysin sykliset orientaatiot on , joka saadaan vaihtamalla argumentteja asyklisten orientaatioiden lukumäärän kaavassa [4] . $T_{G}$ $G$ $G$ ${\näyttötyyli T_{G}(2,0)}$ $T_{G}$ $G$ $T_{G}(0,2)$

Rib Flipping

Tietyn graafin asyklisten orientaatioiden joukolle voidaan antaa osittaiskuutiorakenne , jossa kaksi syklistä orientaatiota on vierekkäin, jos ne eroavat vain yhden reunan suunnasta [5] . Tästä seuraa, että jos saman graafin kaksi erilaista asyklistä orientaatiota poikkeavat toisistaan k reunan suunnassa, on mahdollista muuttaa toinen orientaatioista toiseksi sarjalla k muutosta yhden reunan orientaatiossa siten, että jokainen välitila on asyklinen suuntaus.

Erikoistapaukset

Mikä tahansa puun suunta on asyklinen. Tällaisella orientaatiolla saatua suunnattua asyklistä graafia kutsutaan polypuuksi [6] .

Täydellisen graafin asyklistä orientaatiota kutsutaan transitiiviseksi turnaukseksi ja se vastaa graafin kärkien täydellistä järjestystä . Tällaisessa suunnassa on erityisesti yksi lähde ja yksi pesuallas.

Mielivaltaisen graafin asyklistä orientaatiota, jolla on ainutlaatuinen lähde ja ainutlaatuinen nielu, kutsutaan bipolaariseksi orientaatioksi [7] .

Graafin transitiivinen suunta on asyklinen orientaatio, joka on sen transitiivinen sulkeminen . Kaikilla kaavioilla ei ole transitiivinen suunta. Transitiivisesti orientoidut graafit ovat vertailukäyriä [8] . Täydelliset kaaviot ovat vertailukelpoisten kaavioiden erikoistapaus, ja transitiiviset turnaukset ovat erikoistapauksia transitiivisista suuntauksista.

Muistiinpanot

↑ Nešetřil, Ossona de Mendez, 2012 , s. 42.
↑ Stanley, 1973 , s. 171-178.
↑ Wales, 1997 , s. 287-323.
↑ Las Vergnas, 1980 , s. 231-243.
↑ Fukuda, Prodon, Sakuma, 2001 , s. 9–16.
↑ Dasgupta, 1999 , s. 134-141.
↑ de Fraysseix, Ossona de Mendez, Rosentiehl, 1995 , s. 157-179.
↑ Ghouila-Houri, 1962 , s. 1370-1371.

Kirjallisuus

Richard P Stanley. Graafisten asykliset orientaatiot // Diskreetti matematiikka. - 1973. - V. 5 , no. 2 . - doi : 10.1016/0012-365X(73)90108-8 .
Jaroslav Nešetřil, Patrice Ossona de Mendez. Sparity: kaaviot, rakenteet ja algoritmit. - Heidelberg: Springer, 2012. - T. 28. - S. 42. - (Algoritmit ja kombinatoriikka). — ISBN 978-3-642-27874-7 . - doi : 10.1007/978-3-642-27875-4 .
Dominic Welsh. Surveys in kombinatorials, 1997 (Lontoo). Cambridge: Cambridge Univ. Press, 1997. - T. 241. - S. 287-323. - (London Math. Soc. Lecture Note Ser.). - doi : 10.1017/CBO9780511662119.010 .
Michel Las Vergnas. Konveksiteetti orientoiduissa matroideissa // Journal of Combinatorial Theory . - 1980. - T. 29 , no. 2 . — S. 231–243 . - doi : 10.1016/0095-8956(80)90082-9 .
Komei Fukuda, Alain Prodon, Tadashi Sakuma. Huomautuksia asyklisistä orientaatioista ja kuoritusta lemmasta // Teoreettinen tietojenkäsittelytiede. - 2001. - T. 263 , numero. 1-2 . — s. 9–16 . - doi : 10.1016/S0304-3975(00)00226-7 . (linkki ei saatavilla)
Sanjoy Dasgupta. julkaisussa Proc. 15th Conference on Uncertainty in Artificial Intelligence (UAI 1999), Tukholma, Ruotsi, heinä-elokuu 1999. - 1999. - P. 134-141.
Hubert de Fraysseix, Patrice Ossona de Mendez, Pierre Rosentiehl. Kaksisuuntaiset suuntaukset uudelleen // Discrete Applied Mathematics. - 1995. - T. 56 , no. 2-3 . — S. 157–179 . - doi : 10.1016/0166-218X(94)00085-R .
Alain Ghouila-Houri. Caractérisation des graphes non orientés dont on peut orienter les arrêtes de manière à obtenir le graphe d'une relation d'ordre // Les Comptes rendus de l'Académie des sciences . - 1962. - T. 254 . - S. 1370-1371 .