En teoría de grafos , el teorema de Robbins , que lleva el nombre de Herbert Robbins ( 1939 ), establece que las gráficas que tienen orientaciones fuertes son exactamente las gráficas conectadas por dos aristas . Es decir, es posible elegir una dirección para cada borde de un grafo no dirigido G , convirtiéndolo en un grafo dirigido que tiene un camino desde cada vértice a cada otro vértice, si y solo si G está conectado y no tiene puente .
Gráficos orientables
La caracterización de Robbins de los gráficos con orientaciones fuertes puede probarse utilizando la descomposición del oído , una herramienta introducida por Robbins para esta tarea.
Si un gráfico tiene un puente, entonces no puede ser fuertemente orientable, ya que no importa qué orientación se elija para el puente, no habrá camino desde uno de los dos puntos finales del puente al otro.
En la otra dirección, es necesario mostrar que cada gráfico sin puente conectado puede estar fuertemente orientado. Como demostró Robbins, cada gráfico de este tipo tiene una partición en una secuencia de subgrafos llamados "orejas", en la que el primer subgrafo de la secuencia es un ciclo y cada subgrafo subsiguiente es una ruta, con los dos puntos finales de ruta pertenecientes a oídos anteriores en la secuencia. (Los dos puntos finales de la ruta pueden ser iguales, en cuyo caso el subgrafo es un ciclo). La orientación de los bordes dentro de cada oído para que forme un ciclo dirigido o una ruta dirigida conduce a una orientación fuertemente conectada del gráfico general. [1]
Resultados relacionados
Una extensión del teorema de Robbins a los gráficos mixtos de Boesch y Tindell (1980) muestra que, si G es un gráfico en el que algunos bordes pueden estar dirigidos y otros no dirigidos, y G contiene un camino que respeta las orientaciones de los bordes de cada vértice a cada otro. vértice, entonces cualquier borde no dirigido de G que no es un puente puede hacerse dirigida, sin cambiar la conectividad de G . En particular, un grafo no dirigido sin puente puede convertirse en un grafo dirigido fuertemente conectado mediante un algoritmo codicioso que dirige los bordes uno a la vez mientras preserva la existencia de caminos entre cada par de vértices; Es imposible que un algoritmo de este tipo se atasque en una situación en la que no se puedan tomar decisiones de orientación adicionales.
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. [2] Aunque este algoritmo no es adecuado para computadoras en paralelo , debido a la dificultad de realizar una búsqueda en profundidad en ellas, existen algoritmos alternativos que resuelven el problema de manera eficiente en el modelo paralelo. [3] Los algoritmos paralelos también son conocidos por encontrar orientaciones fuertemente conectadas de gráficos mixtos. [4]
Aplicaciones
Robbins originalmente motivó su trabajo mediante una aplicación al diseño de calles de un solo sentido en ciudades. Otra aplicación surge en la rigidez estructural , en la teoría del arriostramiento de rejilla . Esta teoría se refiere al problema de hacer una rejilla cuadrada, construida a partir de varillas rígidas unidas a uniones flexibles, rígida al agregar más varillas o alambres como refuerzos transversales en las diagonales de la cuadrícula. Un conjunto de varillas agregadas hace que la cuadrícula sea rígida si se conecta un gráfico no dirigido asociado, y está doblemente arriostrado (permaneciendo rígido si se quita algún borde) si además no tiene puentes. De manera análoga, un conjunto de cables agregados (que pueden doblarse para reducir la distancia entre los puntos que conectan, pero no pueden expandirse) hace que la cuadrícula sea rígida si un gráfico dirigido asociado está fuertemente conectado. [5] Por lo tanto, reinterpretando el teorema de Robbins para esta aplicación, las estructuras doblemente arriostradas son exactamente las estructuras cuyas varillas pueden ser reemplazadas por alambres sin dejar de ser rígidas.
Notas
- ^ Gross y Yellen (2006) .
- ↑ Vishkin (1985) atribuye esta observación a Atallah (1984) y Balakrishnan (1996) la atribuye a Roberts (1978) . Pero, comoseñalan Clark y Holton (1991) , el mismo algoritmo ya está incluido (con el supuesto de conectividad de 2 vértices en lugar de conectividad de 2 bordes) en el trabajo previo seminal de Hopcroft y Tarjan (1973) sobre la profundidad primero. buscar.
- ^ Vishkin (1985) .
- ^ Soroker (1988) .
- ^ Baglivo y Graver (1983) .
Referencias
- 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.
- Baglivo, Jenny A .; Graver, Jack E. (1983), "3.10 Estructuras de arriostramiento", Incidencia y simetría en el diseño y la arquitectura , Cambridge Urban and Architectural Studies, Cambridge, Reino Unido: Cambridge University Press, págs. 76–87, ISBN 9780521297844
- Balakrishnan, VK (1996), "4.6 Orientación fuerte de gráficos", Introducción a las matemáticas discretas , Mineola, NY: Dover Publications Inc., p. 135, ISBN 978-0-486-69115-2, MR 1402469.
- Boesch, Frank; Tindell, Ralph (1980), "Teorema de Robbins para multigrafos mixtos", The American Mathematical Monthly , 87 (9): 716–719, doi : 10.2307 / 2321858 , JSTOR 2321858 , MR 0602828.
- Clark, John; Holton, Derek Allan (1991), "7.4 Traffic Flow", Un primer vistazo a la teoría de grafos , Teaneck, Nueva Jersey: World Scientific Publishing Co. Inc., págs. 254-260, ISBN 978-981-02-0489-1, Señor 1119781.
- Gross, Jonathan L .; Yellen, Jay (2006), "Caracterización de grafos fuertemente orientables", Teoría de grafos y sus aplicaciones , Matemáticas discretas y sus aplicaciones (2ª ed.), Boca Raton, FL: Chapman & Hall / CRC, págs. 498–499, ISBN 978-1-58488-505-4, MR 2181153.
- Hopcroft, John ; Tarjan, Robert (1973), "Algoritmo 447: algoritmos eficientes para la manipulación de gráficos", Comunicaciones del ACM , 16 (6): 372–378, doi : 10.1145 / 362248.362272 , S2CID 14772567.
- 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.
- Soroker, Danny (1988), "Orientación fuerte paralela rápida de gráficos mixtos y problemas de aumento relacionados", Journal of Algorithms , 9 (2): 205-223, doi : 10.1016 / 0196-6774 (88) 90038-7 , MR 0936106.
- Vishkin, Uzi (1985), "Sobre una orientación fuerte paralela eficiente", Information Processing Letters , 20 (5): 235-240, doi : 10.1016 / 0020-0190 (85) 90025-0 , MR 0801988.