Puente (teoría de grafos)

Borde en el gráfico de enlace de nodo 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 bordes de puente

En teoría de grafos , un puente , istmo , borde de corte o arco cortado es un borde de un gráfico cuya eliminación aumenta el número de componentes conectados del gráfico . ^[1] De manera equivalente, una arista es un puente si y solo si no está contenida en ningún ciclo . Para un gráfico conectado, un puente puede determinar de forma única un corte . Se dice que un grafo no tiene puentes o está libre de istmos 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; ver puente .

Arboles y bosques

Un gráfico con nodos puede contener como máximo puentes, ya que agregar aristas adicionales debe crear un ciclo. Los gráficos con exactamente puentes son exactamente los árboles , y los gráficos en los que cada arista es un puente son exactamente los bosques . ${\displaystyle n}$ ${\displaystyle n-1}$ ${\displaystyle n-1}$

En todo gráfico 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 hay dos caminos de aristas disjuntas que los conectan. (Cada vértice está relacionado consigo mismo a través de dos caminos de longitud cero, que son idénticos pero, sin embargo, separados por aristas). Las clases de equivalencia de esta relación se denominan componentes conectadas por 2 aristas , y los puentes del gráfico son exactamente las aristas cuyos Los puntos finales pertenecen a diferentes componentes. El árbol de bloques de puentes del gráfico 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 todo 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 es posible que un borde que no sea un puente tenga dos vértices de articulación como puntos finales. De manera análoga a los gráficos sin puente que están conectados por 2 aristas, los gráficos sin vértices de articulación están conectados 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 puente

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

Un problema abierto importante que involucra puentes es la conjetura de la doble cobertura del ciclo , debida a Seymour y Szekeres (1978 y 1979, independientemente), que establece que todo grafo sin puentes admite un conjunto múltiple 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 para encontrar los puentes en un gráfico fue descrito por Robert Tarjan en 1974. ^[5] Realiza los siguientes pasos:

• Encuentre un bosque extenso de ${\displaystyle G}$
• Crear un bosque enraizado a partir del bosque expansivo ${\displaystyle F}$
• Atraviesa el bosque en orden anticipado y numera los nodos. Los nodos principales en el bosque ahora tienen números más bajos que los nodos secundarios. ${\displaystyle F}$
• Para cada nodo en preorden (indicando cada nodo usando 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 pedido anticipado más baja a la que se puede acceder mediante una ruta en la que todos, excepto el último borde, permanecen dentro del subárbol con raíz en . Este es el mínimo del conjunto que consta de la etiqueta de preorden de , de los valores de en los nodos secundarios de y de las etiquetas de preorden de los nodos accesibles desde 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 a la que se puede acceder mediante una ruta para la cual todos menos el último borde permanecen dentro del subárbol con raíz en . Este es el máximo del conjunto que consta de la etiqueta de preorden de , de los valores de en los nodos secundarios de y de las etiquetas de preorden de los nodos accesibles desde 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 desde hasta 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 gráfico, sino que también permiten leer cada vértice cortado de G (y el árbol de corte en bloque de G ), brindando un marco general para probar 2 aristas y 2 vértices. -conectividad (que se extiende a pruebas de conectividad de 3 aristas y 3 vértices en tiempo lineal).

Las descomposiciones en cadena son descomposiciones especiales del oído que dependen de un árbol DFS T de G y se pueden calcular de manera muy simple: marque cada vértice como no visitado. Para cada vértice v en números DFS ascendentes 1... n , recorra cada borde posterior (es decir, cada borde que no esté en el árbol DFS) que incide en v y siga el camino de los bordes 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 a más tardar en v y forma una ruta dirigida o un ciclo, que comienza con v; A este camino o ciclo lo llamamos cadena . La i- ésima cadena _encontrada mediante este procedimiento se denomina Ci . C=C ₁ ,C ₂ ,... es entonces una descomposición en cadena de G .

Las siguientes caracterizaciones permiten leer varias propiedades de G de C de manera eficiente, incluidos 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á conectado por 2 aristas si y solo si las cadenas en la partición C E.
2. Una arista e en G es un puente si y sólo si e no está contenida en ninguna cadena en C.
3. Si G está conectado por 2 aristas, C es una descomposición del oído .
4. G está conectado por 2 vértices si y solo si G tiene un grado mínimo 2 y C ₁ es el único ciclo en C .
5. Un vértice v en un gráfico G conectado con 2 aristas es un vértice de corte si y sólo si v es el primer vértice de un ciclo en C - C ₁ .
6. Si G está conectado por 2 vértices, C es una descomposición en oído abierto .

Ver también

• Componente biconectado
• Cortar (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ág. 6, doi :10.1007/978-1-4612-0619-4, ISBN 0-387-98488-7, señor  1633290.
2. Westbrook, Jeffery ; Tarjan, Robert E. (1992), "Mantenimiento en línea de componentes biconectados y conectados por puente", Algorithmica , 7 (5–6): 433–464, doi :10.1007/BF01758773, MR  1154584.
3. Robbins, HE (1939), "Un teorema sobre gráficas, con una aplicación a un problema de control de tráfico", The American Mathematical Monthly , 46 : 281–283, doi :10.2307/2303897, hdl : 10338.dmlcz/101517.
4. Jaeger, F. (1985), "Un estudio de la conjetura de la doble cobertura del ciclo", Annals of Discrete Mathematics 27 - Cycles in Graphs , Estudios de matemáticas de Holanda Septentrional, vol. 27, págs. 1–12, doi :10.1016/S0304-0208(08)72993-1.
5. Tarjan, R. Endre (1974), "Una nota sobre cómo encontrar los puentes de un gráfico", Cartas de procesamiento de información , 2 (6): 160–161, doi :10.1016/0020-0190(74)90003-9, SEÑOR  0349483.
6. Schmidt, Jens M. (2013), "Una prueba simple sobre conectividad de 2 vértices y 2 bordes", Cartas de procesamiento de información , 113 (7): 241–244, arXiv : 1209.0700 , doi : 10.1016/j .ipl.2013.01.016.