Fuerte orientación

En teoría de grafos , una orientación fuerte de un grafo no dirigido es la asignación de una dirección a cada arista (una orientación ) que lo convierte en un grafo fuertemente conectado .

Las orientaciones fuertes se han aplicado al diseño de redes de carreteras de un solo sentido. Según el teorema de Robbins , los grafos con orientaciones fuertes son precisamente los grafos sin puentes , o equivalentemente, grafos en los que cada componente conexa está conectada por 2 aristas . Las orientaciones eulerianas y las orientaciones bien equilibradas proporcionan casos especiales importantes de orientaciones fuertes; a su vez, las orientaciones fuertes pueden generalizarse a orientaciones totalmente cíclicas de grafos desconectados. El conjunto de orientaciones fuertes de un grafo forma un cubo parcial , con orientaciones adyacentes en esta estructura que difieren en la orientación de una sola arista. Es posible encontrar una sola orientación en tiempo lineal, pero es #P-completo contar el número de orientaciones fuertes de un grafo dado.

Robbins (1939) introduce el problema de la fuerte orientación con una historia sobre un pueblo, cuyas calles e intersecciones están representadas por el grafo G dado . Según la historia de Robbins, los habitantes del pueblo desean poder reparar cualquier segmento de carretera durante los días laborables, permitiendo al mismo tiempo el acceso a cualquier parte del pueblo desde cualquier otra parte utilizando las carreteras restantes como calles de doble sentido. Los fines de semana, todas las carreteras están abiertas, pero debido al gran volumen de tráfico, desean convertirlas todas en calles de un solo sentido y permitir nuevamente el acceso a cualquier parte del pueblo desde cualquier otra parte. El teorema de Robbins establece que un sistema de carreteras es adecuado para reparaciones entre semana si y solo si es adecuado para su conversión a un sistema de un solo sentido los fines de semana. Por esta razón, su resultado se conoce a veces como el teorema de la calle de un solo sentido . ^{[ 1 ]}

Posteriormente al trabajo de Robbins, una serie de artículos de Roberts y Xu modelaron con mayor precisión el problema de convertir una cuadrícula de calles urbanas de doble sentido en calles de un solo sentido, y examinaron el efecto de esta conversión en las distancias entre pares de puntos dentro de la cuadrícula. Como demostraron, el trazado tradicional de un solo sentido, en el que las calles paralelas alternan su dirección, no es óptimo para minimizar las distancias entre pares de puntos. Sin embargo, las orientaciones mejoradas que encontraron incluyen puntos donde el tráfico de dos manzanas de un solo sentido se encuentra de frente, lo que podría considerarse una deficiencia en sus soluciones.

Si un grafo no dirigido tiene un recorrido euleriano , se puede encontrar una orientación euleriana del grafo (una orientación para la cual cada vértice tiene un grado de entrada igual a su grado de salida) orientando las aristas de manera consistente alrededor del recorrido. ^{[ 2 ]} Estas orientaciones son automáticamente orientaciones fuertes.

Un teorema de Nash-Williams ( 1960 , 1969 ) establece que todo grafo no dirigido G tiene una orientación bien equilibrada . Esta es una orientación con la propiedad de que, para cada par de vértices u y v en G , el número de caminos dirigidos disjuntos por aristas de u a v en el grafo dirigido resultante es al menos ${\displaystyle \left\lfloor k/2\right\rfloor }$donde k es el número máximo de caminos en un conjunto de caminos no dirigidos disjuntos por aristas desde u hasta v . Las orientaciones de Nash-Williams también tienen la propiedad de que son lo más cercanas posible a ser orientaciones eulerianas: en cada vértice, el grado de entrada y el grado de salida están dentro de uno entre sí. La existencia de orientaciones bien balanceadas, junto con el teorema de Menger , implica inmediatamente el teorema de Robbins: por el teorema de Menger, un grafo 2-arista-conexo tiene al menos dos caminos disjuntos por aristas entre cada par de vértices, de lo cual se sigue que cualquier orientación bien balanceada debe ser fuertemente conexa. Más generalmente, este resultado implica que todo grafo no dirigido 2 k -arista-conexo puede orientarse para formar un grafo dirigido k -arista-conexo.

Una orientación totalmente cíclica de un grafo G es aquella en la que cada arista pertenece a un ciclo dirigido. Para grafos conexos, esto equivale a una orientación fuerte, pero también se pueden definir orientaciones totalmente cíclicas para grafos disconexos, en las que cada componente conexa de G se vuelve fuertemente conexa. El teorema de Robbins se puede reformular como que un grafo tiene una orientación totalmente cíclica si y solo si no tiene un puente. Las orientaciones totalmente cíclicas son duales a las orientaciones acíclicas (orientaciones que transforman G en un grafo dirigido acíclico ) en el sentido de que, si G es un grafo planar y las orientaciones de G se transfieren a las orientaciones del grafo dual planar de G girando cada arista 90 grados en el sentido de las agujas del reloj, entonces una orientación totalmente cíclica de G corresponde de esta manera a una orientación acíclica del grafo dual y viceversa. ^{[ 3 ] [ 4 ]} El número de orientaciones totalmente cíclicas diferentes de cualquier grafo G es T _G (0, 2) donde T _G es el polinomio de Tutte del grafo, y dualmente el número de orientaciones acíclicas es T _G (2, 0) . ^{[ 5 ]} Como consecuencia, el teorema de Robbins implica que el polinomio de Tutte tiene una raíz en el punto (0, 2) si y solo si el grafo G tiene un puente.

Si una orientación fuerte tiene la propiedad de que todos los ciclos dirigidos pasan por una sola arista st (o, equivalentemente, si invertir la orientación de una arista produce una orientación acíclica ), entonces la orientación acíclica formada al invertir st es una orientación bipolar . Toda orientación bipolar está relacionada con una orientación fuerte de esta manera. ^{[ 6 ]}

Si G es un grafo 3-arista-conectado, y X e Y son dos orientaciones fuertes distintas de G , entonces es posible transformar X en Y cambiando la orientación de una sola arista a la vez, preservando en cada paso la propiedad de que la orientación es fuerte. ^{[ 7 ]} Por lo tanto, el grafo flip cuyos vértices corresponden a las orientaciones fuertes de G , y cuyas aristas corresponden a pares de orientaciones fuertes que difieren en la dirección de una sola arista, forma un cubo parcial .

Una orientación fuerte de un grafo no dirigido sin puentes dado puede encontrarse en tiempo lineal realizando una búsqueda en profundidad del grafo, orientando todas las aristas en el árbol de búsqueda en profundidad alejándolas de la raíz del árbol, y orientando todas las aristas restantes (que necesariamente deben conectar un ancestro y un descendiente en el árbol de búsqueda en profundidad) desde el descendiente hacia el ancestro. ^{[ 8 ]} Si se da un grafo no dirigido G con puentes, junto con una lista de pares ordenados de vértices que deben conectarse mediante caminos dirigidos, es posible en tiempo polinomial encontrar una orientación de G que conecte todos los pares dados, si tal orientación existe. Sin embargo, el mismo problema es NP-completo cuando la entrada puede ser un grafo mixto. ^{[ 9 ]}

Es #P-completo contar el número de orientaciones fuertes de un grafo G dado , incluso cuando G es planar y bipartito . ^{[ 3 ] [ 10 ]} Sin embargo, para grafos densos (más específicamente, grafos en los que cada vértice tiene un número lineal de vecinos), el número de orientaciones fuertes puede estimarse mediante un esquema de aproximación aleatoria de tiempo totalmente polinomial . ^{[ 3 ] [ 11 ]} El problema de contar orientaciones fuertes también puede resolverse exactamente, en tiempo polinomial , para grafos de ancho de árbol acotado . ^{[ 3 ]}