Acyklisk orientering

Den acykliske orientering af en urettet graf er tildelingen af retninger til hver kant ( orientering ), hvor der ikke dannes en rettet cyklus , og derfor forvandler en sådan orientering grafen til en rettet acyklisk graf . Enhver graf har en acyklisk orientering.

Det kromatiske tal for enhver graf er lig med minimumslængden af den maksimale vej blandt alle acykliske orienteringer. Acykliske orienteringer er relateret til farvning ved hjælp af et kromatisk polynomium , som tæller både acykliske orienteringer og farvestoffer. For plane grafer er acykliske orienteringer de dobbelte grafer af fuldstændig cykliske orienteringer , og omvendt. Sættet af acykliske orienteringer af en given graf kan gives strukturen af en delvis terning , hvor to cykliske orienteringer er tilstødende, hvis de adskiller sig i retning af kun én kant.

Træorienteringer er altid acykliske og er polytræer . Acykliske orienteringer af komplette grafer kaldes transitive turneringer . Bipolære orienteringer er specielle tilfælde af acykliske orienteringer, hvor der er præcis én kilde og én vask. Enhver transitiv turnering er bipolær.

Konstruktion

Enhver graf har en acyklisk orientering. En måde at skabe acykliske orienteringer på er at ordne hjørnerne og derefter orientere hver kant fra det tidligste hjørne på listen til det seneste. Sekvensen af toppunkter bliver derefter en topologisk rækkefølge af den resulterende dirigerede acykliske graf (DAG), og enhver topologisk sortering af denne DAG danner den samme orientering.

Da enhver OAG har en topologisk sortering, kan enhver acyklisk orientering opnås på denne måde. Imidlertid kan forskellige vertexsekvenser føre til de samme acykliske orienteringer, hvis den resulterende OAG har flere topologiske sorter. For eksempel har en cyklus med fire hjørner (vist på figuren) 24 forskellige sekvenser, men kun 14 mulige acykliske orienteringer.

Link til farvelægning

Gallai-Hasse-Roy-Vitaver-sætningen siger, at en graf har en acyklisk orientering, hvor den maksimale vej højst har k toppunkter, hvis og kun hvis grafen kan farvelægges med højst k farver [1] .

Antallet af acykliske orienteringer kan tælles ved hjælp af et kromatisk polynomium , hvis værdi for et positivt heltal k er lig med antallet af k -farvninger af grafen. Enhver graf G har nøjagtig forskellige acykliske orienteringer [2] , så i denne forstand kan acykliske orienteringer forstås som en farvning med -1 farve. $\chi _{G}$ $|\chi _{G}(-1)|$

Dualitet

For plane grafer er acykliske orienteringer dobbelte til fuldstændig cykliske orienteringer , orienteringer, hvor hver kant tilhører en rettet cyklus - hvis er en plan graf , og orienteringerne oversættes til orienteringerne af den dobbelte graf ved at rotere hver kant 90 grader med uret, derefter helt cyklisk, svarer grafens orientering til den således opnåede dobbeltgrafs acykliske orientering, og omvendt [3] . $G$ $G$ $G$ $G$

Ligesom det kromatiske polynomium kan Tatta-grafpolynomiet bruges til at tælle antallet af acykliske orienteringer som . Dualiteten mellem acykliske og totalt cykliske orienteringer af plane grafer kan udvides på samme måde til ikke-plane grafer - Tutt-polynomiet for den dobbelte graf af en plan graf opnås ved udveksling af argumenter for polynomiet , og antallet af helt cykliske orienteringer af grafen er , som opnås ved udveksling af argumenter i formlen for antallet af acykliske orienteringer [4] . $T_{G}$ $G$ $G$ $T_{G}(2,0)$ $T_{G}$ $G$ $T_{G}(0,2)$

Rib Flipping

Sættet af acykliske orienteringer af en given graf kan gives en delvis terningstruktur , hvor to cykliske orienteringer støder op til hinanden, hvis de kun adskiller sig i retning af én kant [5] . Det følger heraf, at hvis to forskellige acykliske orienteringer af den samme graf adskiller sig i retningen af k kanter, er det muligt at transformere en af orienteringerne til den anden ved en sekvens af k ændringer i orienteringen af den ene kant, således at hver mellemtilstand er en acyklisk orientering.

Særlige tilfælde

Enhver orientering af et træ er acyklisk. En rettet acyklisk graf opnået ved en sådan orientering kaldes et polytræ [6] .

En acyklisk orientering af en komplet graf kaldes en transitiv turnering og svarer til en fuldstændig rækkefølge af grafens hjørner. I en sådan orientering er der især præcis én kilde og én vask.

En acyklisk orientering af en vilkårlig graf, der har en unik kilde og en unik sink, kaldes en bipolær orientering [7] .

Den transitive orientering af en graf er en acyklisk orientering, som er dens transitive lukning . Ikke alle grafer har en transitiv orientering. Grafer med transitiv orientering er sammenlignelighedsgrafer [8] . Komplette grafer er et særligt tilfælde af sammenlignelighedsgrafer, og transitive turneringer er et særligt tilfælde af transitive orienteringer.

Noter

↑ Nešetřil, Ossona de Mendez, 2012 , s. 42.
↑ Stanley, 1973 , s. 171-178.
↑ Welsh, 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.

Litteratur

Richard P Stanley. Acykliske orienteringer af grafer // Diskret matematik. - 1973. - V. 5 , no. 2 . - doi : 10.1016/0012-365X(73)90108-8 .
Jaroslav Nešetřil, Patrice Ossona de Mendez. Sparity: Grafer, strukturer og algoritmer. - Heidelberg: Springer, 2012. - T. 28. - S. 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. Presse, 1997. - T. 241. - S. 287-323. — (London Math. Soc. Lecture Note Ser.). - doi : 10.1017/CBO9780511662119.010 .
Michel Las Vergnas. Konveksitet i orienterede matroider // 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. Noter om acykliske orienteringer og beskydningslemmaet // Teoretisk datalogi. - 2001. - T. 263 , udg. 1-2 . — S. 9–16 . - doi : 10.1016/S0304-3975(00)00226-7 . (utilgængeligt link)
Sanjoy Dasgupta. i Proc. 15. konference om usikkerhed i kunstig intelligens (UAI 1999), Stockholm, Sverige, juli-august 1999. - 1999. - S. 134-141.
Hubert de Fraysseix, Patrice Ossona de Mendez, Pierre Rosentiehl. Bipolære orienteringer revisited // Diskret anvendt matematik. - 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 .