Orientación acíclica

La orientación acíclica de un grafo no dirigido es la asignación de direcciones a cada arista ( orientación ) en la que no se forma un ciclo dirigido , y por lo tanto tal orientación convierte al grafo en un grafo acíclico dirigido . Cualquier gráfico tiene una orientación acíclica.

El número cromático de cualquier gráfico es igual a la longitud mínima del camino máximo entre todas las orientaciones acíclicas. Las orientaciones acíclicas están relacionadas con la coloración por medio de un polinomio cromático , que cuenta tanto las orientaciones acíclicas como las coloraciones. Para los gráficos planos, las orientaciones acíclicas son los gráficos duales de las orientaciones completamente cíclicas y viceversa. Al conjunto de orientaciones acíclicas de un gráfico dado se le puede dar la estructura de un cubo parcial , en el que dos orientaciones cíclicas son adyacentes si difieren en la dirección de una sola arista.

Las orientaciones de los árboles son siempre acíclicas y son poliárboles . Las orientaciones acíclicas de grafos completos se denominan torneos transitivos . Las orientaciones bipolares son casos especiales de orientaciones acíclicas en las que hay exactamente una fuente y un sumidero. Cualquier torneo transitivo es bipolar.

Edificio

Cualquier gráfico tiene una orientación acíclica. Una forma de crear orientaciones acíclicas es ordenar los vértices y luego orientar cada borde desde el vértice más antiguo de la lista hasta el último. La secuencia de vértices se convierte entonces en una ordenación topológica del gráfico acíclico dirigido (DAG) resultante, y cualquier ordenación topológica de este DAG forma la misma orientación.

Dado que cualquier OAG tiene una clasificación topológica, cualquier orientación acíclica se puede obtener de esta manera. Sin embargo, diferentes secuencias de vértices pueden conducir a las mismas orientaciones acíclicas si el OAG resultante tiene varios tipos topológicos. Por ejemplo, un ciclo con cuatro vértices (que se muestra en la figura) tiene 24 secuencias diferentes, pero solo 14 orientaciones acíclicas posibles.

Enlace para colorear

El teorema de Gallai-Hasse-Roy-Vitaver establece que un gráfico tiene una orientación acíclica en la que el camino máximo tiene como máximo k vértices si y solo si el gráfico puede colorearse con como máximo k colores [1] .

El número de orientaciones acíclicas se puede contar usando un polinomio cromático cuyo valor para un entero positivo k es igual al número de k -coloraciones del gráfico. Cualquier gráfico G tiene orientaciones acíclicas exactamente diferentes [2] , por lo que, en este sentido, las orientaciones acíclicas pueden entenderse como una coloración con −1 color. ${\ estilo de visualización \ chi _ {G}}$ ${\ estilo de visualización | \ chi _ {G} (-1) |}$

Dualidad

Para gráficos planos, las orientaciones acíclicas son orientaciones duales a completamente cíclicas , orientaciones en las que cada borde pertenece a un ciclo dirigido - si es un gráfico plano , y las orientaciones se traducen en las orientaciones del gráfico dual girando cada borde 90 grados en el sentido de las agujas del reloj, luego completamente cíclico la orientación del gráfico corresponde a la orientación acíclica del gráfico dual así obtenido, y viceversa [3] . $GRAMO$ $GRAMO$ $GRAMO$ $GRAMO$

Al igual que el polinomio cromático, el polinomio gráfico de Tatta se puede usar para contar el número de orientaciones acíclicas como . La dualidad entre las orientaciones acíclica y totalmente cíclica de los gráficos planos se puede extender de la misma manera a los gráficos no planos: el polinomio de Tutt del gráfico dual de un gráfico plano se obtiene mediante el intercambio de argumentos del polinomio , y el número de orientaciones completamente cíclicas del gráfico es , que se obtiene mediante el intercambio de argumentos en la fórmula para el número de orientaciones acíclicas [4] . $T_{G}$ $GRAMO$ $GRAMO$ $T_{G}(2,0)$ $T_{G}$ $GRAMO$ $T_{G}(0,2)$

Volteo de costillas

Al conjunto de orientaciones acíclicas de un gráfico dado se le puede dar una estructura de cubo parcial en la que dos orientaciones cíclicas son adyacentes si difieren en la dirección de un solo borde [5] . De ello se deduce que si dos orientaciones acíclicas diferentes del mismo gráfico difieren en la dirección de k aristas, es posible transformar una de las orientaciones en la otra mediante una secuencia de k cambios en la orientación de una arista, de modo que cada estado intermedio es una orientación acíclica.

Casos especiales

Cualquier orientación de un árbol es acíclica. Un gráfico acíclico dirigido obtenido por tal orientación se llama poliárbol [6] .

Una orientación acíclica de un grafo completo se denomina torneo transitivo y equivale a una ordenación completa de los vértices del grafo. En tal orientación, hay, en particular, exactamente una fuente y un sumidero.

Una orientación acíclica de un gráfico arbitrario que tiene una fuente única y un sumidero único se denomina orientación bipolar [7] .

La orientación transitiva de un gráfico es una orientación acíclica, que es su cierre transitivo . No todos los gráficos tienen una orientación transitiva. Los gráficos con orientación transitiva son gráficos de comparabilidad [8] . Los gráficos completos son un caso especial de gráficos de comparabilidad y los torneos transitivos son un caso especial de orientaciones transitivas.

Notas

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

Literatura

Richard P. Stanley. Orientaciones acíclicas de grafos // Matemáticas discretas. - 1973. - V. 5 , núm. 2 . - doi : 10.1016/0012-365X(73)90108-8 .
Jaroslav Nešetřil, Patrice Ossona de Méndez. Sparity: gráficos, estructuras y algoritmos. - Heidelberg: Springer, 2012. - T. 28. - P. 42. - (Algoritmos y Combinatoria). — ISBN 978-3-642-27874-7 . -doi : 10.1007 / 978-3-642-27875-4 .
Dominic Welsh. Surveys in combinatorials, 1997 (Londres). Cambridge: Universidad de Cambridge. Prensa, 1997. - T. 241. - S. 287-323. - (London Math. Soc. Lecture Note Ser.). -doi : 10.1017 / CBO9780511662119.010 .
Michel Las Vergnas. Convexidad en matroides orientados // Revista de Teoría Combinatoria . - 1980. - T. 29 , núm. 2 . — S. 231–243 . - doi : 10.1016/0095-8956(80)90082-9 .
Komei Fukuda, Alain Prodon, Tadashi Sakuma. Apuntes sobre orientaciones acíclicas y el lema de descascarillado // Informática Teórica. - 2001. - T. 263 , núm. 1-2 . — pág. 9–16 . - doi : 10.1016/S0304-3975(00)00226-7 . (enlace no disponible)
Sanjoy Dasgupta. en Proc. 15th Conference on Uncertainty in Artificial Intelligence (UAI 1999), Estocolmo, Suecia, julio-agosto 1999. - 1999. - P. 134-141.
Hubert de Fraysseix, Patrice Ossona de Méndez, Pierre Rosentiehl. Orientaciones bipolares revisadas // Matemática aplicada discreta. - 1995. - T. 56 , núm. 2-3 . — S. 157–179 . - doi : 10.1016/0166-218X(94)00085-R .
Alain Ghouila-Houri. Caracterización de gráficos no orientados no puede orientarse sobre los obstáculos de la humanidad para obtener el gráfico de una relación de orden // Les Comptes rendus de l'Académie des sciences . - 1962. - T. 254 . - S. 1370-1371 .