Orientación (teoría de grafos)

En teoría de grafos , la orientación de un grafo no dirigido consiste en asignar una dirección a cada arista, convirtiendo así el grafo inicial en un grafo dirigido .

Un grafo dirigido se denomina grafo orientado si ninguno de sus pares de vértices está unido por dos aristas mutuamente simétricas. Entre los grafos dirigidos, los grafos orientados son aquellos que no tienen 2-ciclos (es decir, como máximo uno de ( x , y ) y ( y , x ) puede ser una flecha del grafo). ^{[ 1 ]}

Un torneo es una orientación de un grafo completo . Un poliárbol es una orientación de un árbol no dirigido . ^{[ 2 ]} La conjetura de Sumner afirma que todo torneo con 2 n − 2 vértices contiene todo poliárbol con n vértices. ^{[ 3 ]}

El número de grafos orientados no isomorfos con n vértices (para n = 1, 2, 3, … ) es

1, 2, 7, 42, 582, 21480, 2142288, 575016219, 415939243032, … (secuencia A001174 en el OEIS ) .

Los torneos guardan una correspondencia biunívoca con los grafos dirigidos completos (grafos en los que existe una arista dirigida en una o ambas direcciones entre cada par de vértices distintos). Un grafo dirigido completo puede convertirse en un grafo orientado eliminando cada ciclo de orden 2, y viceversa, un grafo orientado puede convertirse en un grafo dirigido completo añadiendo un ciclo de orden 2 entre cada par de vértices que no sean extremos de una arista; estas correspondencias son biyectivas . Por lo tanto, la misma secuencia de números también resuelve el problema de enumeración de grafos para digrafos completos. Existe una fórmula explícita, aunque compleja, para los números de esta secuencia. ^{[ 4 ]}

Una orientación fuerte es aquella que da como resultado un grafo fuertemente conectado . Las orientaciones totalmente cíclicas, estrechamente relacionadas, son aquellas en las que cada arista pertenece al menos a un ciclo simple. Una orientación de un grafo no dirigido G es totalmente cíclica si y solo si es una orientación fuerte de cada componente conexa de G. El teorema de Robbins establece que un grafo tiene una orientación fuerte si y solo si es 2-arista-conexo ; los grafos desconectados pueden tener orientaciones totalmente cíclicas, pero solo si no tienen puentes . ^{[ 5 ]}

Una orientación acíclica es aquella que da como resultado un grafo dirigido acíclico . Todo grafo posee una orientación acíclica; todas las orientaciones acíclicas se obtienen colocando los vértices en una secuencia y dirigiendo cada arista desde el primero de sus extremos en la secuencia hasta el último. 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 puede colorearse con como máximo k colores. ^{[ 6 ]} Las orientaciones acíclicas y las totalmente cíclicas están relacionadas entre sí por la dualidad planar . Una orientación acíclica con un único origen y un único destino se denomina orientación bipolar . ^{[ 7 ]}

Una orientación transitiva es una orientación tal que el grafo dirigido resultante es su propia clausura transitiva . Los grafos con orientaciones transitivas se denominan grafos de comparabilidad ; pueden definirse a partir de un conjunto parcialmente ordenado haciendo que dos elementos sean adyacentes siempre que sean comparables en el orden parcial. ^{[ 8 ]} Una orientación transitiva, si existe, puede hallarse en tiempo lineal. ^{[ 9 ]} Sin embargo, comprobar si la orientación resultante (o cualquier orientación dada) es realmente transitiva requiere más tiempo, ya que su complejidad es equivalente a la de una multiplicación de matrices .

Una orientación euleriana de un grafo no dirigido es aquella en la que cada vértice tiene el mismo grado de entrada y de salida. Las orientaciones eulerianas de los grafos 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 grafo tienen un número impar de aristas orientadas en cada una de las dos direcciones alrededor del ciclo. Siempre existen para grafos planares , pero no para otros grafos. Se utilizan en el algoritmo FKT para contar emparejamientos perfectos. ^{[ 11 ]}

• Relación Connex

• Weisstein, Eric W. , "Orientación de grafos" , MathWorld
• Weisstein, Eric W. , "Grafo orientado" , MathWorld