Fuerte orientación

En la teoría de grafos , una fuerte orientación 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 conectado .

Se han aplicado fuertes orientaciones al diseño de redes de carreteras de un solo sentido. Según el teorema de Robbins , los gráficos con orientaciones fuertes son exactamente los gráficos sin puentes . Las orientaciones eulerianas y las orientaciones equilibradas proporcionan casos especiales importantes de orientaciones fuertes; a su vez, las orientaciones fuertes pueden generalizarse a orientaciones totalmente cíclicas de gráficos desconectados. El conjunto de orientaciones fuertes de un gráfico 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 gráfico dado.

Aplicación al control de tráfico

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 G dado . Según la historia de Robbins, la gente de la ciudad quiere poder reparar cualquier segmento de la carretera durante los días de semana, y al mismo tiempo permitir que se llegue 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, nuevamente, permitir que se llegue a cualquier parte de la ciudad desde cualquier otra parte. Teorema de robbinsestablece que un sistema de carreteras es adecuado para reparaciones entre semana si y solo si es adecuado para la conversión a un sistema de sentido único 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 más cuidadosamente el problema de convertir una cuadrícula de calles urbanas de dos sentidos 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 mostraron, 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 por pares lo más pequeñas posible. 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.

Tipos relacionados de orientación

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 igual a su grado exterior) al orientar los bordes consistentemente alrededor del recorrido. ^[2] Estas orientaciones son automáticamente orientaciones fuertes.

Un teorema de Nash-Williams ( 1960 , 1969 ) establece que cada grafo no dirigido G tiene una orientación bien equilibrada . Ésta 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 por pares de bordes disjuntos de u a v en el gráfico dirigido resultante es al menos , donde k es el número máximo de caminos en un conjunto de trayectorias no direccionadas de borde disjunto de u a v${\displaystyle \lfloor {\frac {k}{2}}\rfloor }$. Las orientaciones de Nash-Williams también tienen la propiedad de que están lo más cerca posible de las orientaciones eulerianas: en cada vértice, el grado inferior y el grado externo están uno dentro del otro. La existencia de orientaciones bien equilibradas, junto con el teorema de Menger , implica inmediatamente el teorema de Robbins: según el teorema de Menger, un grafo conectado por 2 aristas tiene al menos dos trayectorias disjuntas por aristas entre cada par de vértices, de lo cual se deduce que cualquier La orientación bien equilibrada debe estar fuertemente conectada. De manera más general, este resultado implica que cada grafo no dirigido con conexión de 2 k bordes se puede orientar para formar un grafo dirigido con conexión de k k .

Una orientación totalmente cíclica de un gráfico G es una orientación en la que cada borde pertenece a un ciclo dirigido. Para gráficos conectados, esto es lo mismo que una orientación fuerte, pero también se pueden definir orientaciones totalmente cíclicas para gráficos desconectados, y son las orientaciones en las que cada componente conectado de G se conecta fuertemente. El teorema de Robbins puede reformularse diciendo que un gráfico 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 gráfico acíclico dirigido ) en el sentido de que, si G es un gráfico plano , y las orientaciones deG se transfieren a las orientaciones del gráfico dual plano de G girando cada borde 90 grados en el sentido de las agujas del reloj, luego una orientación totalmente cíclica de G corresponde de esta manera a una orientación acíclica del gráfico dual y viceversa. ^{[3] [4]} El número de diferentes orientaciones totalmente cíclicas de cualquier gráfico G es T _G (0,2) donde T _G es el polinomio de Tutte del gráfico, y doblemente 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 la gráfica G tiene un puente.

Si una orientación fuerte tiene la propiedad de que todos los ciclos dirigidos pasan a través de un solo borde st (de manera equivalente, si voltear la orientación de un borde produce una orientación acíclica ), entonces la orientación acíclica formada invirtiendo st es una orientación bipolar . Toda orientación bipolar está relacionada con una fuerte orientación de esta manera. ^[6]

Voltear gráficos

Si G es un gráfico conectado 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 un solo borde a la vez, en cada paso conservando la propiedad que la orientacion es fuerte. ^[7] Por lo tanto, el flip graph cuyos vértices corresponden a las orientaciones fuertes de G , y cuyos bordes corresponden a pares de orientaciones fuertes que difieren en la dirección de un solo borde, forma un cubo parcial .

Algoritmos y complejidad

Se puede encontrar una fuerte orientación de un gráfico no dirigido sin puente dado en tiempo lineal realizando una primera búsqueda en profundidad del gráfico, orientando todos los bordes en el primer árbol de búsqueda en profundidad lejos de la raíz del árbol y orientando todos los bordes restantes (que necesariamente deben conectar un antepasado y un descendiente en el primer árbol de búsqueda en profundidad) del descendiente al antepasado. ^[8] Si se da 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 el tiempo polinomial encontrar una orientación de G que conecte todos los pares dados, si tal orientación existe. Sin embargo, el mismo problema esNP-completo cuando la entrada puede ser un gráfico mixto. ^[9]

Es # P-completo contar el número de orientaciones fuertes de un gráfico G dado , incluso cuando G es plano y bipartito . ^{[3] [10]} Sin embargo, para gráficos densos (más específicamente, gráficos 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 aleatorizado en tiempo polinomial completo . ^{[3] [11]} El problema de contar orientaciones fuertes también puede resolverse exactamente, en tiempo polinomial , para gráficos de ancho de árbol acotado . ^[3]

Notas

1. Koh y Tay (2002) .
2. Schrijver (1983) .
3. Galés (1997) .
4. Noy (2001) .
5. Las Vergnas (1980) .
6. de Fraysseix, Ossona de Mendez y Rosenstiehl (1995) .
7. Fukuda, Prodon y Sakuma (2001) .
8. Véase, por ejemplo, Atallah (1984) y Roberts (1978) .
9. Arkin y Hassin (2002) .
10. Vertigan y Gales (1992) .
11. Alon, Frieze y Welsh (1995) .

Referencias

• Alon, Noga ; Frieze, Alan ; Welsh, Dominic (1995), "Esquemas polinomiales de aproximación aleatoria en el tiempo para invariantes de Tutte-Gröthendieck: el caso denso", Estructuras y algoritmos aleatorios , 6 (4): 459–478, doi : 10.1002 / rsa.3240060409 , MR  1368847
• Arkin, Esther M .; Hassin, Refael (2002), "Una nota sobre las orientaciones de los gráficos mixtos", Matemáticas aplicadas discretas , 116 (3): 271-278, doi : 10.1016 / S0166-218X (01) 00228-1 , MR  1878572.
• Atallah, Mikhail J. (1984), "Orientación fuerte paralela de un gráfico no dirigido" , Information Processing Letters , 18 (1): 37–39, doi : 10.1016 / 0020-0190 (84) 90072-3 , MR  0742079.
• de Fraysseix, Hubert; Ossona de Méndez, Patrice ; Rosenstiehl, Pierre (1995), "Orientaciones bipolares revisitadas", Matemáticas aplicadas discretas , 56 (2-3): 157-179, doi : 10.1016 / 0166-218X (94) 00085-R , MR  1318743.
• Fukuda, Komei ; Prodon, Alain; Sakuma, Tadashi (2001), "Notes on acíclic orientations and the shelling lema" , Theoretical Computer Science , 263 (1-2): 9-16, doi : 10.1016 / S0304-3975 (00) 00226-7 , MR  1846912^{[ enlace muerto permanente ]} .
• Koh, KM; Tay, EG (2002), "Orientaciones óptimas de gráficos y dígrafos: una encuesta", Gráficos y combinatoria , 18 (4): 745–756, doi : 10.1007 / s003730200060 , MR  1964792 , S2CID  34821155.
• 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.
• Nash-Williams, C. St. JA (1960), "Sobre orientaciones, conectividad y emparejamientos de vértices impares en gráficos finitos", Canadian Journal of Mathematics , 12 : 555–567, doi : 10.4153 / cjm-1960-049 -6 , MR  0118684.
• Nash-Williams, C. St. JA (1969), "Orientaciones bien equilibradas de gráficos finitos y emparejamientos discretos de vértices impares", Progreso reciente en combinatoria (Proc. Tercera Conf. De Waterloo sobre Combinatoria, 1968) , Nueva York: Academic Press, págs. 133-149, MR  0253933.
• Noy, Marc (2001), "Orientaciones acíclicas y totalmente cíclicas en gráficas planas", The American Mathematical Monthly , 108 (1): 66–68, doi : 10.2307 / 2695680 , JSTOR  2695680 , MR  1857074.
• Robbins, HE (1939), "Un teorema sobre gráficos, con una aplicación a un problema de control de tráfico", American Mathematical Monthly , 46 (5): 281-283, doi : 10.2307 / 2303897 , JSTOR  2303897.
• Roberts, Fred S. (1978), "Capítulo 2. El problema de la calle de un solo sentido", Teoría de grafos y sus aplicaciones a los problemas de la sociedad , Serie de conferencias regionales de CBMS-NSF sobre matemáticas aplicadas, 29 , Filadelfia, Pa .: Society for Matemáticas industriales y aplicadas (SIAM), págs. 7–14, ISBN 9780898710267, MR  0508050.
• Roberts, Fred S .; Xu, Yonghua (1988), "Sobre las orientaciones óptimas fuertemente conectadas de los gráficos de calles de la ciudad. I. Cuadrículas grandes", SIAM Journal on Discrete Mathematics , 1 (2): 199-222, doi : 10.1137 / 0401022 , MR  0941351.
• Roberts, Fred S .; Xu, Yonghua (1989), "Sobre las orientaciones óptimas fuertemente conectadas de los gráficos de calles de la ciudad. II. Dos avenidas este-oeste o calles norte-sur", Networks , 19 (2): 221-233, doi : 10.1002 / net. 3230190204 , MR  0984567.
• Roberts, Fred S .; Xu, Yonghua (1992), "Sobre las orientaciones óptimas fuertemente conectadas de los gráficos de calles de la ciudad. III. Tres avenidas este-oeste o calles norte-sur", Networks , 22 (2): 109-143, doi : 10.1002 / net. 3230220202 , MR  1148018.
• Roberts, Fred S .; Xu, Yong Hua (1994), "Sobre las orientaciones óptimas fuertemente conectadas de los gráficos de calles de la ciudad. IV. Cuatro avenidas este-oeste o calles norte-sur", Discrete Applied Mathematics , 49 (1-3): 331-356, doi : 10.1016 / 0166-218X (94) 90217-8 , Sr.  1272496.
• Schrijver, A. (1983), "Límites en el número de orientaciones eulerianas" (PDF) , Combinatorica , 3 (3–4): 375–380, doi : 10.1007 / BF02579193 , MR  0729790 , S2CID  13708977.
• Vertigan, DL; Welsh, DJA (1992), "La complejidad computacional del plano de Tutte: el caso bipartito", Combinatoria, Probabilidad y Computación , 1 (2): 181-187, doi : 10.1017 / S0963548300000195 , MR  1179248.
• Welsh, Dominic (1997), "Conteo aproximado", Encuestas en combinatoria, 1997 (Londres) , London Math. Soc. Lecture Note Ser., 241 , Cambridge: Cambridge Univ. Prensa, págs. 287–323, doi : 10.1017 / CBO9780511662119.010 , MR  1477750.