Puente (teoría de grafos)

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 conexas del grafo . ^{[ 1 ]} De forma 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 forma única un corte . Se dice que un grafo no tiene puentes o istmos si no contiene ninguno.

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 .

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

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

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 extremos 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 extremos. De forma análoga a como los grafos sin puentes son 2-aristas-conexos, los grafos sin vértices de articulación son 2-vértices-conexos .

En un grafo cúbico , cada vértice de corte es un extremo de al menos un puente.

Un grafo sin puentes es un grafo que no tiene ningún puente. Las condiciones equivalentes son que cada componente conexa del grafo tenga una descomposición de oreja abierta , ^{[ 3 ]} que cada componente conexa sea 2-arista-conexa , o (por el teorema de Robbins ) que cada componente conexa tenga una fuerte orientación . ^{[ 3 ]}

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

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 extenso bosque de${\displaystyle G}$
• Crea un bosque enraizado${\displaystyle F}$desde el bosque que se extiende
• Atraviesa el bosque${\displaystyle F}$en preorden y numerar los nodos. Los nodos padre en el bosque ahora tienen números más bajos que los nodos hijo.
• Para cada nodo${\displaystyle v}$en preorden (indicando cada nodo mediante su número de preorden), haga lo siguiente:
  • Calcula el número de descendientes del bosque.${\displaystyle ND(v)}$para este nodo, sumando uno a la suma de los descendientes de sus hijos.
  • Calcular${\displaystyle L(v)}$, la etiqueta de preorden más baja alcanzable desde${\displaystyle v}$por un camino para el cual todos los bordes, excepto el último, permanecen dentro del subárbol enraizado en${\displaystyle v}$. Este es el mínimo del conjunto que consiste en la etiqueta de preorden de${\displaystyle v}$, de los valores de${\displaystyle L(w)}$en los nodos hijos de${\displaystyle v}$y de las etiquetas de preorden de los nodos alcanzables desde${\displaystyle v}$por bordes que no pertenecen a${\displaystyle F}$.
  • De manera similar, calcular${\displaystyle H(v)}$, la etiqueta de preorden más alta alcanzable por una ruta para la cual todas las aristas excepto la última permanecen dentro del subárbol enraizado en${\displaystyle v}$. Este es el máximo del conjunto que consta de la etiqueta de preorden de${\displaystyle v}$, de los valores de${\displaystyle H(w)}$en los nodos hijos de${\displaystyle v}$y de las etiquetas de preorden de los nodos alcanzables desde${\displaystyle v}$por bordes que no pertenecen a${\displaystyle F}$.
  • Para cada nodo${\displaystyle w}$con nodo padre${\displaystyle v}$, si${\displaystyle L(w)=w}$y${\displaystyle H(w)<w+ND(w)}$entonces el borde de${\displaystyle v}$a${\displaystyle w}$es un puente.

Un algoritmo muy simple para encontrar 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 de bloques 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 de aristas especiales que dependen de un árbol DFS T de G y se pueden calcular de forma muy sencilla: Sea cada vértice marcado como no visitado. Para cada vértice v en los números DFS ascendentes 1... n , recorra cada arista de retroceso (es decir, cada arista que no está en el árbol DFS) que sea incidente a v y siga el camino de aristas del árbol de vuelta a la raíz de T , deteniéndose en el primer vértice que está marcado como visitado. Durante dicho recorrido, cada vértice recorrido está marcado como visitado. Por lo tanto, un recorrido se detiene como máximo en v y forma un camino dirigido o ciclo, comenzando 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 grafo conexo simple G=(V,E) .

1. G es 2 - arista-conexo si y solo si las cadenas en C particionan E.
2. Una arista e en G es un puente si y solo si e no está contenida en ninguna cadena en C.
3. Si G es 2-arista-conexo, C es una descomposición de oreja .
4. G es 2-conexo por 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 2 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 es 2-conexo por vértices, C es una descomposición de oreja abierta .

Un grafo euleriano se define como un grafo con un ciclo euleriano. Todo grafo euleriano carece de puentes. Esto se debe a que, en un grafo euleriano, cada arista forma parte de un ciclo euleriano. Por lo tanto, si se elimina una arista, sus extremos permanecen conectados a través del resto del ciclo. Sin embargo, lo contrario no es cierto.

Define an almost Eulerian graph as a graph that can be made Eulerian by adding a single edge (equivalently, a graph that contains an Eulerian trail). Every almost-Eulerian graph is almost-bridgeless, but the opposite is not true.

The classes of bridgeless graphs and almost-Eulerian graphs have a non-empty intersection (the Eulerian graphs are both bridgeless and almost-Eulerian), but they do not contain each other.^{[7]:Appendix.B}

• Biconnected component
• Cut (graph theory)