Acyklisk orientering

Den acykliska orienteringen av en oriktad graf är tilldelningen av riktningar till varje kant ( orientering ) där ingen riktad cykel bildas , och därför förvandlar en sådan orientering grafen till en riktad acyklisk graf . Varje graf har en acyklisk orientering.

Det kromatiska talet för en graf är lika med den minsta längden på den maximala banan bland alla acykliska orienteringar. Acykliska orienteringar är relaterade till färgning med hjälp av ett kromatiskt polynom , som räknar både acykliska orienteringar och färger. För plana grafer är acykliska orienteringar de dubbla graferna för helt cykliska orienteringar , och vice versa. Uppsättningen av acykliska orienteringar av en given graf kan ges strukturen av en partiell kub , där två cykliska orienteringar är intill varandra om de skiljer sig åt i riktningen av endast en kant.

Trädorienteringarna är alltid acykliska och är polyträd [ . Acykliska orienteringar av kompletta grafer kallas transitiva turneringar . Bipolära orienteringar är specialfall av acykliska orienteringar där det finns exakt en källa och en sänka. Alla transitiva turneringar är bipolära.

Byggnad

Varje graf har en acyklisk orientering. Ett sätt att skapa acykliska orienteringar är att ordna hörnen och sedan orientera varje kant från den tidigaste hörn i listan till den senaste. Sekvensen av hörn blir sedan en topologisk ordning av den resulterande riktade acykliska grafen (DAG), och varje topologisk sortering av denna DAG bildar samma orientering.

Eftersom vilken OAG som helst har en topologisk sort, kan vilken som helst acyklisk orientering erhållas på detta sätt. Emellertid kan olika vertexsekvenser leda till samma acykliska orienteringar om den resulterande OAG har flera topologiska sorter. Till exempel har en cykel med fyra hörn (visas i figuren) 24 olika sekvenser, men bara 14 möjliga acykliska orienteringar.

Länk till färgläggning

Gallai-Hasse-Roy-Vitaver-satsen säger att en graf har en acyklisk orientering där den maximala banan har högst k hörn om och bara om grafen kan färgas med högst k färger [1] .

Antalet acykliska orienteringar kan räknas med hjälp av ett kromatiskt polynom vars värde för ett positivt heltal k är lika med antalet k -färgningar i grafen. Vilken graf G som helst har exakt olika acykliska orienteringar [2] , så i denna mening kan acykliska orienteringar förstås som en färgning med -1 färg. $\chi _{G}$ $|\chi _{G}(-1)|$

Dualitet

För plana grafer är acykliska orienteringar dubbla till helt cykliska orienteringar , orienteringar där varje kant tillhör en riktad cykel - if är en plan graf , och orienteringarna översätts till orienteringarna för den dubbla grafen genom att vrida varje kant 90 grader medurs, sedan helt cykliskt motsvarar grafens orientering den acykliska orienteringen av den sålunda erhållna dubbla grafen och vice versa [3] . $G$ $G$ $G$ $G$

Liksom det kromatiska polynomet kan Tatta -grafpolynomet användas för att räkna antalet acykliska orienteringar som . Dualiteten mellan acykliska och totalt cykliska orienteringar av plana grafer kan utökas på samma sätt till icke-planära grafer - Tutt-polynomet för den dubbla grafen för en plan graf erhålls genom utbyte av argument för polynomet , och antalet helt cykliska orienteringar av grafen är , som erhålls genom utbyte av argument i formeln för antalet acykliska orienteringar [4] . $T_{G}$ $G$ $G$ $T_{G}(2,0)$ $T_{G}$ $G$ $T_{G}(0,2)$

Ribbvändning

Uppsättningen av acykliska orienteringar för en given graf kan ges en partiell kubstruktur där två cykliska orienteringar är intilliggande om de skiljer sig åt i riktningen av endast en kant [5] . Det följer att om två olika acykliska orienteringar av samma graf skiljer sig åt i riktningen av k kanter, är det möjligt att omvandla en av orienteringarna till den andra genom en sekvens av k förändringar i orienteringen av en kant, så att varje mellantillstånd är en acyklisk orientering.

Specialfall

Varje orientering av ett träd är acyklisk. En riktad acyklisk graf som erhålls genom en sådan orientering kallas ett polyträd [6] .

En acyklisk orientering av en komplett graf kallas en transitiv turnering och motsvarar en fullständig ordning av grafens hörn. I en sådan orientering finns det i synnerhet exakt en källa och en sänka.

En acyklisk orientering av en godtycklig graf som har en unik källa och en unik sänka kallas bipolär orientering [7] .

Den transitiva orienteringen av en graf är en acyklisk orientering, vilket är dess transitiva stängning . Inte varje graf har en transitiv orientering. Grafer med transitiv orientering är jämförbarhetsdiagram [8] . Kompletta grafer är ett specialfall av jämförbarhetsgrafer, och transitiva turneringar är ett specialfall av transitiva orienteringar.

Anteckningar

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

Litteratur

Richard P Stanley. Acykliska orienteringar av grafer // Diskret matematik. - 1973. - V. 5 , nr. 2 . - doi : 10.1016/0012-365X(73)90108-8 .
Jaroslav Nešetřil, Patrice Ossona de Mendez. Sparity: Grafer, strukturer och algoritmer. - Heidelberg: Springer, 2012. - T. 28. - P. 42. - (Algorithms and Combinatorics). — ISBN 978-3-642-27874-7 . - doi : 10.1007/978-3-642-27875-4 .
Dominic Welsh. Surveys in combinatorials, 1997 (London). Cambridge: Cambridge Univ. Press, 1997. - T. 241. - S. 287-323. — (London Math. Soc. Lecture Note Ser.). - doi : 10.1017/CBO9780511662119.010 .
Michel Las Vergnas. Konvexitet i orienterade matroider // Journal of Combinatorial Theory . - 1980. - T. 29 , nr. 2 . — S. 231–243 . - doi : 10.1016/0095-8956(80)90082-9 .
Komei Fukuda, Alain Prodon, Tadashi Sakuma. Anteckningar om acykliska orienteringar och beskjutningslemmat // Teoretisk datavetenskap. - 2001. - T. 263 , nummer. 1-2 . — S. 9–16 . - doi : 10.1016/S0304-3975(00)00226-7 . (inte tillgänglig länk)
Sanjoy Dasgupta. i Proc. 15th Conference on Uncertainty in Artificial Intelligence (UAI 1999), Stockholm, Sverige, juli-augusti 1999. - 1999. - S. 134-141.
Hubert de Fraysseix, Patrice Ossona de Mendez, Pierre Rosentiehl. Bipolära orienteringar återbesökt // Diskret tillämpad matematik. - 1995. - T. 56 , nr. 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 .