Orientare aciclică

Orientarea aciclică a unui graf nedirecționat este alocarea de direcții fiecărei muchii ( orientare ) în care nu se formează niciun ciclu direcționat și, prin urmare, o astfel de orientare transformă graficul într-un graf aciclic direcționat . Orice grafic are o orientare aciclică.

Numărul cromatic al oricărui grafic este egal cu lungimea minimă a căii maxime dintre toate orientările aciclice. Orientările aciclice sunt legate de colorare prin intermediul unui polinom cromatic , care numără atât orientările aciclice, cât și colorațiile. Pentru graficele plane, orientările aciclice sunt graficele duale ale orientărilor complet ciclice , și invers. Mulțimii orientărilor aciclice ale unui grafic dat i se poate da structura unui cub parțial , în care două orientări ciclice sunt adiacente dacă diferă în direcția unei singure muchii.

Orientările arborilor sunt întotdeauna aciclice și sunt poliarbori . Orientările aciclice ale graficelor complete se numesc turnee tranzitive . Orientările bipolare sunt cazuri speciale de orientări aciclice în care există exact o sursă și un singur absorbant. Orice turneu tranzitiv este bipolar.

Clădire

Orice grafic are o orientare aciclică. O modalitate de a crea orientări aciclice este de a ordona vârfurile și apoi de a orienta fiecare muchie de la cel mai vechi vârf din listă la cel mai recent. Secvența de vârfuri devine apoi o ordonare topologică a graficului aciclic direcționat (DAG) rezultat, iar orice sortare topologică a acestui DAG formează aceeași orientare.

Deoarece orice OAG are un sort topologic, orice orientare aciclică poate fi obținută în acest fel. Cu toate acestea, secvențe de vârf diferite pot duce la aceleași orientări aciclice dacă OAG rezultat are mai multe sorturi topologice. De exemplu, un ciclu cu patru vârfuri (prezentat în figură) are 24 de secvențe diferite, dar numai 14 orientări aciclice posibile.

Link către colorare

Teorema Gallai-Hasse-Roy-Vitaver afirmă că un grafic are o orientare aciclică în care drumul maxim are cel mult k vârfuri dacă și numai dacă graficul poate fi colorat cu cel mult k culori [1] .

Numărul de orientări aciclice poate fi numărat folosind un polinom cromatic a cărui valoare pentru un întreg pozitiv k este egală cu numărul de k -colorări ale graficului. Orice grafic G are orientări aciclice exact diferite [2] , deci în acest sens, orientările aciclice pot fi înțelese ca o colorare cu −1 culoare. $\chi _{G}$ $|\chi _{G}(-1)|$

Dualitate

Pentru graficele plane, orientările aciclice sunt orientări duale până la complet ciclice , orientări în care fiecare muchie aparține unui ciclu direcționat - dacă este un grafic plan , iar orientările sunt translate în orientările graficului dual prin rotirea fiecărei muchii 90 grade în sensul acelor de ceasornic, apoi complet ciclic orientarea graficului corespunde orientării aciclice a graficului dual astfel obținut și invers [3] . $G$ $G$ $G$ $G$

La fel ca polinomul cromatic, polinomul grafic Tatta poate fi folosit pentru a număra numărul de orientări aciclice ca . Dualitatea dintre orientările aciclice și total ciclice ale graficelor plane poate fi extinsă în același mod și la graficele neplanare — polinomul Tutt al graficului dual al unui grafic plan se obține prin schimbul de argumente ale polinomului și numărul de orientările complet ciclice ale graficului este , care se obține prin schimbul de argumente în formula pentru numărul de orientări aciclice [4] . $T_{G}$ $G$ $G$ $T_{G}(2,0)$ $T_{G}$ $G$ $T_{G}(0,2)$

Rib Flipping

Mulțimii orientărilor aciclice ale unui grafic dat i se poate da o structură de cub parțial în care două orientări ciclice sunt adiacente dacă diferă în direcția unei singure muchii [5] . Rezultă că dacă două orientări aciclice diferite ale aceluiași grafic diferă în direcția k muchii, este posibil să se transforme una dintre orientări în cealaltă printr-o succesiune de k modificări în orientarea unei muchii, astfel încât fiecare stare intermediară este o orientare aciclică.

Cazuri speciale

Orice orientare a unui arbore este aciclică. Un graf aciclic direcționat obținut printr-o astfel de orientare se numește polytree [6] .

O orientare aciclică a unui graf complet se numește turneu tranzitiv și este echivalentă cu o ordonare completă a vârfurilor grafului. Într-o astfel de orientare, există, în special, exact o sursă și o chiuvetă.

O orientare aciclică a unui graf arbitrar care are o sursă unică și un absorbant unic se numește orientare bipolară [7] .

Orientarea tranzitivă a unui grafic este o orientare aciclică, care este închiderea sa tranzitivă . Nu orice grafic are o orientare tranzitivă. Graficele cu orientare tranzitivă sunt grafice de comparabilitate [8] . Graficele complete sunt un caz special de grafice de comparabilitate, iar turneele tranzitive sunt un caz special de orientări tranzitive.

Note

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

Literatură

Richard P Stanley. Orientări aciclice ale graficelor // Matematică discretă. - 1973. - V. 5 , nr. 2 . - doi : 10.1016/0012-365X(73)90108-8 .
Jaroslav Nešetřil, Patrice Ossona de Mendez. Sparitate: grafice, structuri și algoritmi. - Heidelberg: Springer, 2012. - T. 28. - P. 42. - (Algoritmi și combinatorică). — ISBN 978-3-642-27874-7 . - doi : 10.1007/978-3-642-27875-4 .
Dominic Welsh. Surveys in combinatorials, 1997 (Londra). Cambridge: Cambridge University. Press, 1997. - T. 241. - S. 287-323. — (London Math. Soc. Lecture Note Ser.). - doi : 10.1017/CBO9780511662119.010 .
Michel Las Vergnas. Convexitatea în matroizi orientați // 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. Note despre orientările aciclice și lema de decojire // Informatică teoretică. - 2001. - T. 263 , nr. 1-2 . — P. 9–16 . - doi : 10.1016/S0304-3975(00)00226-7 . (link indisponibil)
Sanjoy Dasgupta. în Proc. 15th Conference on Uncertainty in Artificial Intelligence (UAI 1999), Stockholm, Suedia, iulie-august 1999. - 1999. - P. 134-141.
Hubert de Fraysseix, Patrice Ossona de Mendez, Pierre Rosentiehl. Orientări bipolare revăzute // Matematică aplicată discretă. - 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 à obține le graphe d'une relation d'ordre // Les Comptes rendus de l'Académie des sciences . - 1962. - T. 254 . - S. 1370-1371 .