Teorema de Robbins

En teoría de grafos , el teorema de Robbins , que lleva el nombre de Herbert Robbins ( 1939 ) , establece que los grafos que tienen orientaciones fuertes son precisamente los grafos 2-aristas-conexos . Es decir, es posible elegir una dirección para cada arista de un grafo no dirigido G , convirtiéndolo en un grafo dirigido que tiene un camino desde cada vértice a todos los demás vértices, si y solo si G es conexo y no tiene puentes . 

La caracterización que hace Robbins de los grafos con fuertes orientaciones puede demostrarse utilizando la descomposición en orejas , una herramienta introducida por Robbins para esta tarea.

Si un grafo tiene un puente, entonces no puede ser fuertemente orientable, ya que, independientemente de la orientación que se elija para el puente, no habrá un camino desde uno de los dos extremos del puente al otro.

En sentido contrario, es necesario demostrar que todo grafo conexo sin puentes puede estar fuertemente orientado. Como demostró Robbins, todo grafo 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 un camino, cuyos dos extremos pertenecen a orejas anteriores de la secuencia. (Los dos extremos del camino pueden ser iguales, en cuyo caso el subgrafo es un ciclo). Orientar las aristas dentro de cada oreja de manera que forme un ciclo dirigido o un camino dirigido conduce a una orientación fuertemente conexa del grafo global. ^{[ 1 ]}

Una extensión del teorema de Robbins a grafos mixtos , realizada por Boesch y Tindell (1980), demuestra que si G es un grafo en el que algunas aristas pueden ser dirigidas y otras no, y G contiene un camino que respeta las orientaciones de las aristas desde cada vértice a todos los demás, entonces cualquier arista no dirigida de G que no sea un puente puede convertirse en dirigida sin cambiar la conectividad de G. En particular, un grafo no dirigido sin puentes puede transformarse en un grafo dirigido fuertemente conexo mediante un algoritmo voraz que dirige las aristas una a una, preservando la existencia de caminos entre cada par de vértices; es imposible que dicho algoritmo se quede atascado en una situación en la que no se puedan tomar decisiones de orientación adicionales.

Una fuerte orientación 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. ^{[ 2 ]} Aunque este algoritmo no es adecuado para computadoras paralelas , 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 ]} También se conocen algoritmos paralelos para encontrar orientaciones fuertemente conectadas de grafos mixtos. ^{[ 4 ]}

Robbins motivó originalmente su trabajo por una aplicación al diseño de calles de sentido único en ciudades. Otra aplicación surge en la rigidez estructural , en la teoría del arriostramiento de cuadrículas . Esta teoría aborda el problema de hacer rígida una cuadrícula cuadrada, construida con varillas rígidas unidas en juntas flexibles, añadiendo más varillas o alambres como arriostramiento transversal en las diagonales de la cuadrícula. Un conjunto de varillas añadidas hace que la cuadrícula sea rígida si un grafo no dirigido asociado está conectado, y es doblemente arriostrada (permaneciendo rígida si se elimina cualquier arista) si además no tiene puentes. Análogamente, un conjunto de alambres añadidos (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 grafo dirigido asociado está fuertemente conectado. ^{[ 5 ]} Por lo tanto, reinterpretando el teorema de Robbins para esta aplicación, las estructuras doblemente arriostradas son precisamente las estructuras cuyas varillas pueden ser reemplazadas por alambres sin dejar de ser rígidas.