En teoría de grafos , una orientación de un gráfico no dirigido es una asignación de una dirección a cada arista, convirtiendo el gráfico inicial en un gráfico dirigido .
Un grafo dirigido se llama grafo orientado si ninguno de sus pares de vértices está unido por dos aristas simétricas. Entre los gráficos dirigidos, los gráficos orientados son los que no tienen 2 ciclos (es decir, como máximo uno de ( x , y ) y ( y , x ) pueden ser flechas del gráfico). [1]
Un torneo es una orientación de un gráfico completo . Un poliárbol es una orientación de un árbol no dirigido . [2] La conjetura de Sumner establece que cada torneo con 2 n – 2 vértices contiene cada poliárbol con n vértices. [3]
El número de gráficos orientados no isomorfos con n vértices (para n = 1, 2, 3,… ) es
Los torneos están en correspondencia uno a uno con gráficos dirigidos completos (gráficos en los que hay un borde dirigido en una o ambas direcciones entre cada par de vértices distintos). Un gráfico dirigido completo se puede convertir en un gráfico orientado eliminando cada 2 ciclos y, a la inversa, un gráfico orientado se puede convertir en un gráfico dirigido completo agregando 2 ciclos entre cada par de vértices que no son puntos finales de un borde; estas correspondencias son biyectivas . Por lo tanto, la misma secuencia de números también resuelve el problema de enumeración de gráficos para dígrafos completos. Existe una fórmula explícita pero complicada para los números de esta secuencia. [4]
Una orientación fuerte es una orientación que da como resultado un gráfico fuertemente conectado . Las orientaciones totalmente cíclicas, estrechamente relacionadas, son orientaciones en las que cada arista pertenece al menos a un ciclo simple. Una orientación de un gráfico no dirigido G es totalmente cíclica si y sólo si es una orientación fuerte de cada componente conectado de G. El teorema de Robbins establece que un gráfico tiene una orientación fuerte si y sólo si está conectado por 2 aristas ; Los grafos desconectados pueden tener orientaciones totalmente cíclicas, pero sólo si no tienen puentes . [5]
Una orientación acíclica es una orientación que da como resultado un gráfico acíclico dirigido . Todo gráfico tiene una orientación acíclica; Todas las orientaciones acíclicas se pueden obtener colocando los vértices en una secuencia y luego dirigiendo cada arista desde el primer punto final de la secuencia hasta el último punto final. El teorema de Gallai-Hasse-Roy-Vitaver establece que un gráfico tiene una orientación acíclica en la que el camino más largo tiene como máximo k vértices si y sólo si se puede colorear con como máximo k colores. [6] Las orientaciones acíclicas y las orientaciones totalmente cíclicas están relacionadas entre sí por dualidad plana . Una orientación acíclica con una única fuente y un único sumidero se denomina orientación bipolar . [7]
Una orientación transitiva es una orientación tal que el gráfico dirigido resultante es su propio cierre transitivo . Las gráficas con orientaciones transitivas se llaman gráficas de comparabilidad ; se pueden definir a partir de un conjunto parcialmente ordenado haciendo dos elementos adyacentes siempre que sean comparables en el orden parcial. [8] Una orientación transitiva, si existe, se puede encontrar en el tiempo lineal. [9] Sin embargo, probar si la orientación resultante (o cualquier orientación dada) es realmente transitiva requiere más tiempo, ya que es equivalente en complejidad a la multiplicación de matrices .
Una orientación euleriana de un gráfico no dirigido es una orientación en la que cada vértice tiene el mismo grado de entrada y de salida. Las orientaciones eulerianas de los gráficos de cuadrícula surgen en la mecánica estadística en la teoría de los modelos de tipo hielo . [10]
Una orientación pfaffiana tiene la propiedad de que ciertos ciclos de longitud par en el gráfico tienen un número impar de aristas orientadas en cada una de las dos direcciones alrededor del ciclo. Siempre existen para gráficos planos , pero no para otros gráficos determinados. Se utilizan en el algoritmo FKT para contar coincidencias perfectas. [11]