En teoría de grafos , una orientación fuerte de un grafo no dirigido es una asignación de una dirección a cada borde (una orientación ) que lo convierte en un grafo fuertemente conexo .
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 exactamente los grafos sin puentes . 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 un solo borde. 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 orientación fuerte con una historia sobre una ciudad, cuyas calles e intersecciones están representadas por el gráfico dado G . Según la historia de Robbins, la gente de la ciudad quiere poder reparar cualquier segmento de carretera durante los días laborables, permitiendo al mismo tiempo que se pueda llegar a cualquier parte de la ciudad 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 convertir todas las carreteras en calles de un solo sentido y permitir de nuevo que se pueda llegar a cualquier parte de la ciudad desde cualquier otra parte. El teorema de Robbins establece que un sistema de carreteras es adecuado para reparaciones durante los días laborables si y solo si es adecuado para la conversión a un sistema de un solo sentido los fines de semana. Por esta razón, su resultado a veces se conoce 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 más cuidado el problema de convertir una cuadrícula de calles de una ciudad 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 diseño tradicional de un solo sentido en el que las calles paralelas se alternan en dirección no es óptimo para mantener las distancias entre pares lo más pequeñas posibles. Sin embargo, las orientaciones mejoradas que encontraron incluyen puntos donde el tráfico de dos bloques de un solo sentido se encuentra de frente, lo que puede verse como un defecto en sus soluciones.
Si un gráfico no dirigido tiene un recorrido de Euler , se puede encontrar una orientación euleriana del gráfico (una orientación para la cual cada vértice tiene un grado de entrada igual a su grado de salida) orientando los bordes 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 . Se trata de 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 en las aristas de u a v en el grafo dirigido resultante es al menos , donde k es el número máximo de caminos en un conjunto de caminos no dirigidos disjuntos en las aristas de u a v . Las orientaciones de Nash-Williams también tienen la propiedad de que son lo más cercanas posible a las orientaciones eulerianas: en cada vértice, el grado de entrada y el grado de salida están dentro de un intervalo entre sí. La existencia de orientaciones bien equilibradas, junto con el teorema de Menger , implica inmediatamente el teorema de Robbins: por el teorema de Menger, un grafo con 2 aristas conexas tiene al menos dos caminos disjuntos entre cada par de vértices, de lo que se sigue que cualquier orientación bien equilibrada debe estar fuertemente conexa. De manera más general, este resultado implica que cada grafo no dirigido con 2 k aristas conexas puede orientarse para formar un grafo dirigido con k aristas conexas.
Una orientación totalmente cíclica de un grafo G es una orientación en la que cada arista pertenece a un ciclo dirigido. Para grafos conexos, esto es lo mismo que una orientación fuerte, pero las orientaciones totalmente cíclicas también pueden definirse para grafos desconectados, y son las orientaciones en las que cada componente conexo de G se vuelve fuertemente conexo. El teorema de Robbins puede reformularse diciendo 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 convierten a G en un grafo acíclico dirigido ) en el sentido de que, si G es un grafo plano , y las orientaciones de G se transfieren a orientaciones del grafo dual plano 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 un único borde st (equivalentemente, si invertir la orientación de un borde 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 conexo por 3 aristas, y X e Y son dos orientaciones fuertes diferentes 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 invertido 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 .
Se puede encontrar una orientación fuerte de un grafo no dirigido sin puentes en tiempo lineal realizando una búsqueda en profundidad del grafo, orientando todos los bordes del árbol de búsqueda en profundidad lejos de la raíz del árbol y orientando todos los bordes restantes (que necesariamente deben conectar un ancestro y un descendiente en el árbol de búsqueda en profundidad) desde el descendiente hasta el ancestro. [8] Si se proporciona un grafo no dirigido G con puentes, junto con una lista de pares ordenados de vértices que deben estar conectados por 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 dado G , 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 se puede estimar mediante un esquema de aproximación completamente aleatorio en tiempo polinomial . [3] [11] El problema de contar orientaciones fuertes también se puede resolver de manera exacta, en tiempo polinomial , para grafos de ancho de árbol acotado . [3]
