Orientación acíclica

Elemento de la teoría de grafos

Las 14 orientaciones acíclicas diferentes de un gráfico cíclico de 4 vértices , asignaciones de una dirección a cada arista del ciclo que hacen que el gráfico dirigido resultante sea acíclico . Dos orientaciones se muestran como adyacentes cuando difieren en la dirección de una sola arista.

En teoría de grafos , una orientación acíclica de un grafo no dirigido es una asignación de una dirección a cada arista (una orientación ) que no forma ningún ciclo dirigido y, por lo tanto, lo convierte en un grafo acíclico dirigido . Todo grafo tiene una orientación acíclica.

El número cromático de cualquier grafo es igual a uno más que la longitud del camino más largo en una orientación acíclica elegida para minimizar esta longitud de camino. Las orientaciones acíclicas también están relacionadas con las coloraciones a través del polinomio cromático , que cuenta tanto las orientaciones acíclicas como las coloraciones. El dual planar de una orientación acíclica es una orientación totalmente cíclica , y viceversa. A la familia de todas las orientaciones acíclicas se le puede dar la estructura de un cubo parcial haciendo que dos orientaciones sean adyacentes cuando difieren en la dirección de una sola arista.

Las orientaciones de los árboles son siempre acíclicas y dan lugar a poliárboles . Las orientaciones acíclicas de grafos completos se denominan torneos transitivos . Las orientaciones bipolares son un caso especial de las orientaciones acíclicas en las que hay exactamente una fuente y un sumidero; todo torneo transitivo es bipolar.

Construcción

Cada grafo tiene una orientación acíclica. Una forma de generar una orientación acíclica es colocar los vértices en una secuencia y luego dirigir cada arista desde el punto final anterior en la secuencia hasta el punto final posterior. La secuencia de vértices se convierte entonces en un ordenamiento topológico del grafo acíclico dirigido (DAG) resultante, y cada ordenamiento topológico de este DAG genera la misma orientación.

Como cada DAG tiene un ordenamiento topológico, cada orientación acíclica se puede construir de esta manera. Sin embargo, es posible que diferentes secuencias de vértices den lugar a la misma orientación acíclica, cuando el DAG resultante tiene múltiples ordenamientos topológicos. Por ejemplo, para un grafo de ciclo de cuatro vértices (mostrado), hay 24 secuencias de vértices diferentes, pero solo 14 orientaciones acíclicas posibles.

Relación con la coloración

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

El número de orientaciones acíclicas se puede contar utilizando el polinomio cromático , cuyo valor en un entero positivo k es el número de k coloraciones del grafo. Cada grafo G tiene exactamente diferentes orientaciones acíclicas, ^[2] por lo que en este sentido una orientación acíclica se puede interpretar como una coloración con −1 colores. ${\displaystyle \chi _{G}}$ ${\displaystyle |\chi _{G}(-1)|}$

Dualidad

Para los grafos planares , las orientaciones acíclicas son orientaciones duales a totalmente cíclicas , orientaciones en las que cada arista pertenece a un ciclo dirigido: si es un grafo planar , y las orientaciones de se transfieren a orientaciones del grafo dual planar de girando cada arista 90 grados en el sentido de las agujas del reloj, entonces una orientación totalmente cíclica de corresponde de esta manera a una orientación acíclica del grafo dual y viceversa. ^[3] ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$

Al igual que el polinomio cromático, el polinomio de Tutte de un grafo , se puede utilizar para contar el número de orientaciones acíclicas de como . La dualidad entre las orientaciones acíclicas y totalmente cíclicas de los grafos planares se extiende de esta forma también a los grafos no planares: el polinomio de Tutte del grafo dual de un grafo planar se obtiene intercambiando los argumentos de , y el número de orientaciones totalmente cíclicas de un grafo es , también obtenido intercambiando los argumentos de la fórmula para el número de orientaciones acíclicas. ^[4] ${\displaystyle T_{G}}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle T_{G}(2,0)}$ ${\displaystyle T_{G}}$ ${\displaystyle G}$ ${\displaystyle T_{G}(0,2)}$

Cambio de borde

Al conjunto de todas las orientaciones acíclicas de un grafo dado se le puede dar la estructura de un cubo parcial , en el que dos orientaciones acíclicas son adyacentes siempre que difieran en la dirección de una sola arista. ^[5] Esto implica que cuando dos orientaciones acíclicas diferentes del mismo grafo difieren en las direcciones de k aristas, es posible transformar una de las orientaciones en la otra mediante una secuencia de k cambios de orientación de una sola arista, de modo que cada uno de los estados intermedios de esta secuencia de transformaciones también sea acíclico.

Casos especiales

Un poliárbol, resultado de orientar acíclicamente un árbol

Toda orientación de un árbol es acíclica. El grafo acíclico dirigido resultante de dicha orientación se denomina poliárbol . ^[6]

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

De manera más general, 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]

Una orientación transitiva de un grafo es una orientación acíclica que es igual a su propio cierre transitivo . No todos los grafos tienen una orientación transitiva; los grafos que sí la tienen son los grafos de comparabilidad . ^[8] Los grafos completos son casos especiales de grafos de comparabilidad, y los torneos transitivos son casos especiales de orientaciones transitivas.

Referencias

1. Nešetřil, Jaroslav ; Ossona de Mendez, Patrice (2012), "Teorema 3.13", Sparsity: Graphs, Structures, and Algorithms , Algorithms and Combinatorics, vol. 28, Heidelberg: Springer, p. 42, doi :10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, Sr.  2920058.
2. Stanley, Richard P. (1973), "Orientaciones acíclicas de grafos", Discrete Mathematics , 5 (2): 171–178, doi :10.1016/0012-365X(73)90108-8.
3. Welsh, Dominic (1997), "Conteo aproximado", Surveys in combinatorics, 1997 (Londres) , London Math. Soc. Lecture Note Ser., vol. 241, Cambridge: Cambridge Univ. Press, págs. 287–323, doi :10.1017/CBO9780511662119.010, MR  1477750.
4. Las Vergnas, Michel (1980), "Convexidad en matroides orientadas", Journal of Combinatorial Theory , Serie B, 29 (2): 231–243, doi :10.1016/0095-8956(80)90082-9, MR  0586435.
5. Fukuda, Komei ; Prodon, Alain; Sakuma, Tadashi (2001), "Notas sobre orientaciones acíclicas y el lema de descascarado", Theoretical Computer Science , 263 (1–2): 9–16, doi : 10.1016/S0304-3975(00)00226-7 , MR  1846912
6. Dasgupta, Sanjoy (1999), "Aprendizaje de polytrees", en Proc. 15th Conference on Uncertainty in Artificial Intelligence (UAI 1999), Estocolmo, Suecia, julio-agosto de 1999 (PDF) , pp. 134–141 .
7. de Fraysseix, Hubert; de Mendez, Patrice Ossona; Rosenstiehl, Pierre (1995), "Orientaciones bipolares revisitadas", Discrete Applied Mathematics , 56 (2–3): 157–179, doi : 10.1016/0166-218X(94)00085-R , MR  1318743.
8. Ghouila-Houri, Alain (1962), "Caractérisation des graphes non orientés dont on peut orienter les arrêtes de manière à obtenir le graphe d'une Relations d'ordre", Les Comptes rendus de l'Académie des sciences , 254 : 1370 –1371, SEÑOR  0172275.