Acyklická orientace

Acyklická orientace neorientovaného grafu je přiřazení směrů každé hraně ( orientaci ), ve které nevzniká žádný směrovaný cyklus , a proto taková orientace mění graf v orientovaný acyklický graf . Každý graf má acyklickou orientaci.

Barevné číslo libovolného grafu se rovná minimální délce maximální dráhy mezi všemi acyklickými orientacemi. Acyklické orientace souvisí s barvením pomocí chromatického polynomu , který počítá jak acyklické orientace, tak zbarvení. Pro rovinné grafy jsou acyklické orientace duálními grafy zcela cyklických orientací a naopak. Množina acyklických orientací daného grafu může mít strukturu parciální krychle , ve které sousedí dvě cyklické orientace, pokud se liší pouze ve směru jedné hrany.

Orientace stromů jsou vždy acyklické a jsou to polystromy . Acyklické orientace úplných grafů se nazývají tranzitivní turnaje . Bipolární orientace jsou speciální případy acyklických orientací, ve kterých je právě jeden zdroj a jedna jímka. Každý tranzitivní turnaj je bipolární.

Konstrukce

Každý graf má acyklickou orientaci. Jedním ze způsobů, jak vytvořit acyklické orientace, je seřadit vrcholy a poté orientovat každou hranu od nejstaršího vrcholu v seznamu po nejnovější. Posloupnost vrcholů se pak stává topologickým uspořádáním výsledného orientovaného acyklického grafu (DAG) a jakékoli topologické řazení tohoto DAG tvoří stejnou orientaci.

Protože každý OAG má topologické řazení, lze tímto způsobem získat jakoukoli acyklickou orientaci. Různé vrcholové sekvence však mohou vést ke stejným acyklickým orientacím, pokud má výsledný OAG více topologických druhů. Například cyklus se čtyřmi vrcholy (zobrazený na obrázku) má 24 různých sekvencí, ale pouze 14 možných acyklických orientací.

Odkaz na barvení

Gallai-Hasse-Roy-Vitaverova věta říká, že graf má acyklickou orientaci, ve které má maximální dráha nejvýše k vrcholů právě tehdy, když lze graf obarvit nejvýše k barvami [1] .

Počet acyklických orientací lze spočítat pomocí chromatického polynomu , jehož hodnota pro kladné celé číslo k je rovna počtu k -zabarvení grafu. Každý graf G má přesně odlišné acyklické orientace [2] , takže v tomto smyslu lze acyklické orientace chápat jako zbarvení −1 barvou. $\chi _{G}$ $|\chi _{G}(-1)|$

Dualita

Pro rovinné grafy jsou acyklické orientace duální až zcela cyklické orientace , orientace, ve kterých každá hrana patří do orientovaného cyklu - if je rovinný graf a orientace jsou převedeny do orientací duálního grafu otočením každé hrany o 90°. stupně ve směru hodinových ručiček, pak zcela cyklicky orientace grafu odpovídá takto získané acyklické orientaci duálního grafu a naopak [3] . $G$ $G$ $G$ $G$

Podobně jako chromatický polynom lze i polynom Tatta grafu použít k počítání počtu acyklických orientací jako . Dualitu mezi acyklickou a zcela cyklickou orientací rovinných grafů lze stejným způsobem rozšířit i na nerovinné grafy — Tuttův polynom duálního grafu rovinného grafu se získá výměnou argumentů polynomu a počtem zcela cyklické orientace grafu je , což se získá výměnou argumentů ve vzorci pro počet acyklických orientací [4] . $T_{G}$ $G$ $G$ $T_{G}(2,0)$ $T_{G}$ $G$ $T_{G}(0,2)$

Překlápění žebra

Množině acyklických orientací daného grafu může být dána částečná krychlová struktura , ve které sousedí dvě cyklické orientace, pokud se liší pouze ve směru jedné hrany [5] . Z toho vyplývá, že pokud se dvě různé acyklické orientace téhož grafu liší ve směru k hran, je možné transformovat jednu z orientací na druhou sekvencí k změn orientace jedné hrany, takže každý mezistav je acyklická orientace.

Speciální případy

Jakákoli orientace stromu je acyklická. Orientovaný acyklický graf získaný takovou orientací se nazývá polytree [6] .

Acyklická orientace úplného grafu se nazývá tranzitivní turnaj a je ekvivalentní úplnému uspořádání vrcholů grafu. V takové orientaci je zejména přesně jeden zdroj a jedna jímka.

Acyklická orientace libovolného grafu, který má jedinečný zdroj a jedinečný pokles, se nazývá bipolární orientace [7] .

Tranzitivní orientace grafu je acyklická orientace, což je jeho tranzitivní uzávěr . Ne každý graf má tranzitivní orientaci. Grafy s tranzitivní orientací jsou grafy srovnatelnosti [8] . Kompletní grafy jsou speciálním případem grafů srovnatelnosti a tranzitivní turnaje jsou zvláštním případem tranzitivních orientací.

Poznámky

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

Literatura

Richard P. Stanley. Acyklické orientace grafů // Diskrétní matematika. - 1973. - V. 5 , čís. 2 . - doi : 10.1016/0012-365X(73)90108-8 .
Jaroslav Nešetřil, Patrice Ossona de Mendez. Sparita: Grafy, struktury a algoritmy. - Heidelberg: Springer, 2012. - T. 28. - S. 42. - (Algoritmy a kombinatorika). — ISBN 978-3-642-27874-7 . - doi : 10.1007/978-3-642-27875-4 .
Dominic Welsh. Průzkumy v kombinatoriích, 1997 (Londýn). Cambridge: Cambridge Univ. Press, 1997. - T. 241. - S. 287-323. — (Londýnská matematika. Soc. Poznámka k přednášce Ser.). - doi : 10.1017/CBO9780511662119.010 .
Michel Las Vergnas. Konvexita v orientovaných matroidech // 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. Poznámky k acyklickým orientacím a lemmatu ostřelování // Teoretická informatika. - 2001. - T. 263 , vydání. 1-2 . — S. 9–16 . - doi : 10.1016/S0304-3975(00)00226-7 . (nedostupný odkaz)
Sanjoy Dasgupta. v Proc. 15th Conference on Uncertainty in Artificial Intelligence (UAI 1999), Stockholm, Švédsko, červenec-srpen 1999. - 1999. - S. 134-141.
Hubert de Fraysseix, Patrice Ossona de Mendez, Pierre Rosentiehl. Revidované bipolární orientace // Diskrétní aplikovaná matematika. - 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 relationship d'ordre // Les Comptes rendus de l'Académie des sciences . - 1962. - T. 254 . - S. 1370-1371 .