Puente (teoría de grafos)

Arista en el gráfico de enlace de nodos cuya eliminación desconectaría el gráfico

Un gráfico con 16 vértices y seis puentes (resaltados en rojo)

Un gráfico conectado no dirigido sin aristas de puente

En teoría de grafos , un puente , istmo , arista de corte o arco de corte es una arista de un grafo cuya eliminación aumenta el número de componentes conexos del grafo . ^[1] De manera equivalente, una arista es un puente si y solo si no está contenida en ningún ciclo . Para un grafo conexo, un puente puede determinar de manera única un corte . Se dice que un grafo no tiene puentes o no tiene istmo si no contiene puentes.

Este tipo de puente debe distinguirse de un significado no relacionado de "puente" en la teoría de grafos, un subgrafo separado del resto del grafo por un subconjunto específico de vértices; véase puente en el Glosario de teoría de grafos .

Árboles y bosques

Un grafo con nodos puede contener como máximo puentes, ya que al añadir aristas adicionales se debe crear un ciclo. Los grafos con exactamente puentes son exactamente los árboles y los grafos en los que cada arista es un puente son exactamente los bosques . ${\displaystyle n}$ ${\displaystyle n-1}$ ${\displaystyle n-1}$

En todo grafo no dirigido, existe una relación de equivalencia en los vértices según la cual dos vértices están relacionados entre sí siempre que existan dos caminos disjuntos en sus aristas que los conecten. (Cada vértice está relacionado consigo mismo a través de dos caminos de longitud cero, que son idénticos pero, sin embargo, disjuntos en sus aristas). Las clases de equivalencia de esta relación se denominan componentes conexos por 2 aristas , y los puentes del grafo son exactamente las aristas cuyos puntos finales pertenecen a componentes diferentes. El árbol de bloques-puente del grafo tiene un vértice para cada componente no trivial y una arista para cada puente. ^[2]

Relación con la conectividad de vértices

Los puentes están estrechamente relacionados con el concepto de vértices de articulación , vértices que pertenecen a cada camino entre algún par de otros vértices. Los dos puntos finales de un puente son vértices de articulación a menos que tengan un grado de 1, aunque también puede ser posible que una arista que no sea un puente tenga dos vértices de articulación como puntos finales. De manera análoga a los grafos sin puentes que son conexos por 2 aristas, los grafos sin vértices de articulación son conexos por 2 vértices .

En un gráfico cúbico , cada vértice cortado es un punto final de al menos un puente.

Gráficos sin puentes

Un grafo sin puentes es un grafo que no tiene ningún puente. Las condiciones equivalentes son que cada componente conexo del grafo tenga una descomposición de oreja abierta , ^[3] que cada componente conexo esté conexo por dos aristas o (según el teorema de Robbins ) que cada componente conexo tenga una orientación fuerte . ^[3]

Un importante problema abierto que involucra puentes es la conjetura de doble cobertura de ciclos , debida a Seymour y Szekeres (1978 y 1979, independientemente), que establece que cada grafo sin puentes admite un multiconjunto de ciclos simples que contiene cada arista exactamente dos veces. ^[4]

El algoritmo de búsqueda de puentes de Tarjan

El primer algoritmo de tiempo lineal (lineal en el número de aristas) para encontrar los puentes en un grafo fue descrito por Robert Tarjan en 1974. ^[5] Realiza los siguientes pasos:

• Encuentra un bosque que se extiende de ${\displaystyle G}$
• Crear un bosque enraizado a partir del bosque de expansión ${\displaystyle F}$
• Recorrer el bosque en orden previo y numerar los nodos. Los nodos primarios del bosque ahora tienen números más bajos que los nodos secundarios. ${\displaystyle F}$
• Para cada nodo en preorden (indicando cada nodo mediante su número de preorden), haga lo siguiente: ${\displaystyle v}$
  • Calcule el número de descendientes del bosque para este nodo, sumando uno a la suma de los descendientes de sus hijos. ${\displaystyle ND(v)}$
  • Calcular , la etiqueta de preorden más baja alcanzable desde por una ruta para la cual todos los bordes, excepto el último, permanecen dentro del subárbol con raíz en . Este es el mínimo del conjunto que consiste en la etiqueta de preorden de , de los valores de en los nodos secundarios de y de las etiquetas de preorden de los nodos alcanzables desde por los bordes que no pertenecen a . ${\displaystyle L(v)}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle L(w)}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle F}$
  • De manera similar, calcule , la etiqueta de preorden más alta alcanzable por una ruta para la cual todos los bordes excepto el último permanecen dentro del subárbol con raíz en . Este es el máximo del conjunto que consiste en la etiqueta de preorden de , de los valores de en los nodos secundarios de y de las etiquetas de preorden de los nodos alcanzables desde por los bordes que no pertenecen a . ${\displaystyle H(v)}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle H(w)}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle F}$
  • Para cada nodo con nodo padre , si y entonces el borde de a es un puente. ${\displaystyle w}$ ${\displaystyle v}$ ${\displaystyle L(w)=w}$ ${\displaystyle H(w)<w+ND(w)}$ ${\displaystyle v}$ ${\displaystyle w}$

Búsqueda de puentes con descomposiciones en cadena

Un algoritmo muy simple de búsqueda de puentes ^[6] utiliza descomposiciones en cadena . Las descomposiciones en cadena no solo permiten calcular todos los puentes de un grafo, sino que también permiten leer cada vértice de corte de G (y el árbol de corte en bloque de G ), lo que proporciona un marco general para probar la conectividad de 2 aristas y 2 vértices (que se extiende a pruebas de conectividad de 3 aristas y 3 vértices en tiempo lineal).

Las descomposiciones en cadena son descomposiciones especiales de orejas que dependen de un árbol DFS T de G y se pueden calcular de forma muy sencilla: marquemos cada vértice como no visitado. Para cada vértice v en los números DFS ascendentes 1... n , recorra cada arista posterior (es decir, cada arista que no esté en el árbol DFS) que sea incidente a v y siga la ruta de las aristas del árbol hasta la raíz de T , deteniéndose en el primer vértice que esté marcado como visitado. Durante dicho recorrido, cada vértice atravesado se marca como visitado. Por lo tanto, un recorrido se detiene como muy tarde en v y forma un camino o ciclo dirigido, que comienza con v; llamamos a este camino o ciclo una cadena . La i ésima cadena encontrada por este procedimiento se denomina C _i . C=C ₁ ,C ₂ ,... es entonces una descomposición en cadena de G .

Las siguientes caracterizaciones permiten entonces leer varias propiedades de G a partir de C de manera eficiente , incluyendo todos los puentes de G. ^[6] Sea C una descomposición en cadena de un gráfico conexo simple G=(V,E) .

1. G está conexo por dos aristas si y solo si las cadenas en C se dividen en E.
2. Una arista e en G es un puente si y sólo si e no está contenido en ninguna cadena en C.
3. Si G está conexo por dos aristas, C es una descomposición en orejas .
4. G es conexo por 2 vértices si y solo si G tiene grado mínimo 2 y C ₁ es el único ciclo en C .
5. Un vértice v en un grafo G con dos aristas conexas es un vértice de corte si y solo si v es el primer vértice de un ciclo en C - C ₁ .
6. Si G está conexo por 2 vértices, C es una descomposición de oreja abierta .

Véase también

• Componente biconectado
• Corte (teoría de grafos)

Notas

1. Bollobás, Béla (1998), Teoría de grafos moderna, Textos de posgrado en matemáticas, vol. 184, Nueva York: Springer-Verlag, p. 6, doi :10.1007/978-1-4612-0619-4, ISBN 0-387-98488-7, Sr.  1633290.
2. Westbrook, Jeffery ; Tarjan, Robert E. (1992), "Mantenimiento de componentes conectados y biconectados en puente en línea", Algorithmica , 7 (5–6): 433–464, doi :10.1007/BF01758773, MR  1154584.
3. Robbins, HE (1939), "Un teorema sobre grafos, con una aplicación a un problema de control de tráfico", The American Mathematical Monthly , 46 (5): 281–283, doi :10.2307/2303897, hdl : 10338.dmlcz/101517 , JSTOR  2303897.
4. Jaeger, F. (1985), "Un estudio de la conjetura de doble cobertura del ciclo", Anales de Matemáticas Discretas 27 – Ciclos en Gráficos , Estudios de Matemáticas de Holanda Septentrional, vol. 27, págs. 1–12, doi :10.1016/S0304-0208(08)72993-1, ISBN 978-0-444-87803-8.
5. Tarjan, R. Endre (1974), "Una nota sobre la búsqueda de los puentes de un gráfico", Information Processing Letters , 2 (6): 160–161, doi :10.1016/0020-0190(74)90003-9, MR  0349483.
6. Schmidt, Jens M. (2013), "Una prueba simple sobre conectividad de 2 vértices y 2 aristas", Information Processing Letters , 113 (7): 241–244, arXiv : 1209.0700 , doi :10.1016/j.ipl.2013.01.016.