En teoría de grafos , un puente , istmo , borde de corte o arco de corte es un borde de un gráfico cuya eliminación aumenta el número de componentes conectados del gráfico . [1] De manera equivalente, un borde es un puente si y solo si no está contenido en ningún ciclo . Para un gráfico conectado, un puente puede determinar de forma única un corte . Se dice que un gráfico 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 Glosario de términos de teoría de grafos § puente .
Árboles y bosques
Un gráfico con los nodos pueden contener como máximo puentes, ya que agregar bordes adicionales debe crear un ciclo. Los gráficos con exactamentelos puentes son exactamente los árboles , y los gráficos en los que cada borde es un puente son exactamente los bosques .
En cada grafo no dirigido, hay 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 borde disjuntos que los conectan. (Cada vértice está relacionado consigo mismo a través de dos trayectorias de longitud cero, que son idénticas pero sin embargo disjuntas en los bordes.) Las clases de equivalencia de esta relación se denominan componentes conectados por 2 bordes , y los puentes del gráfico son exactamente los bordes cuyas 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 un borde 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 puentes conectados por 2 bordes, 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 de corte 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 tiene una descomposición de oído abierto , [3] que cada componente conectado está conectado por 2 bordes o (según el teorema de Robbins ) que cada componente conectado tiene una orientación fuerte . [3]
Un problema abierto importante que involucra puentes es la conjetura de la doble cobertura del ciclo , debido a Seymour y Szekeres (1978 y 1979, independientemente), que establece que cada grafo sin puente admite un conjunto múltiple de ciclos simples que contiene cada borde 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:
- Encuentra un bosque extenso de
- Crea un bosque enraizado desde el bosque que se extiende
- Atravesar el bosque en preordenar y numerar los nodos. Los nodos principales del bosque ahora tienen números más bajos que los nodos secundarios.
- Para cada nodo en preorder (que denota cada nodo usando su número de preorden), haga:
- Calcular el número de descendientes del bosque para este nodo, agregando uno a la suma de los descendientes de sus hijos.
- Calcular , la etiqueta de reserva más baja accesible desde por un camino para el cual todos menos el último borde permanece dentro del subárbol enraizado en . Este es el mínimo del conjunto que consta de la etiqueta de pedido anticipado de, de los valores de en los nodos secundarios de y de las etiquetas de preorden de nodos accesibles desde por aristas que no pertenecen a .
- Del mismo modo, calcule , la etiqueta de preorden más alta a la que se puede acceder mediante una ruta para la que todos, excepto el último borde, permanecen dentro del subárbol 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 nodos accesibles desde por aristas que no pertenecen a .
- Para cada nodo con nodo padre , Si y luego el borde de a es un puente.
Búsqueda de puentes con descomposiciones en cadena
Un algoritmo de búsqueda de puentes muy simple [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 de corte de G (y el árbol de corte de bloque de G ), lo que proporciona un marco general para probar 2 aristas y 2 vértices. -conectividad (que se extiende a las pruebas de conectividad de 3 aristas y 3 vértices en tiempo lineal).
Las descomposiciones en cadena son descomposiciones de oído especiales 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 , atraviese cada retroceso (es decir, cada borde que no esté en el árbol DFS) que sea incidente av y siga el camino de los bordes del árbol de regreso a la raíz de T , deteniéndose en el primer vértice marcado como visitado. Durante dicho recorrido, cada vértice atravesado se marca como visitado. Por tanto, un recorrido se detiene a más tardar en v y forma una trayectoria dirigida o un 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 1 , C 2 , ... es entonces una degradación de las cadenas de G .
Los siguientes caracterizaciones luego permitir a leer de varias propiedades de G de C de manera eficiente, incluyendo todos los puentes de G . [6] Sea C una descomposición en cadena de un gráfico simple conectado G = (V, E) .
- G está conectado-2-borde si y sólo si las cadenas en C partición E .
- Un borde e en G es un puente si y sólo si e no está contenida en cualquier cadena en C .
- Si G está conectado por 2 bordes, C es una descomposición del oído .
- G está conectada a 2-vértice si y sólo si G tiene grado mínimo 2 y C 1 es el único ciclo en C .
- Un vértice v en un gráfico G conectado por 2 aristas es un vértice cortado si y solo si v es el primer vértice de un ciclo en C - C 1 .
- Si G está conectado a 2 vértices, C es una descomposición de oído abierto .
Cabeza de puente
Para un gráfico conectado , un puente puede separar en la región y región , es decir, el corte . Los vértices y son las dos cabezas de puente de y . es la cabeza de puente cercana de y cabeza de puente lejana de y viceversa para .
Ver también
Notas
- ^ Bollobás, Béla (1998), Teoría de grafos modernos , Textos de posgrado en matemáticas, 184 , Nueva York: Springer-Verlag, p. 6, doi : 10.1007 / 978-1-4612-0619-4 , ISBN 0-387-98488-7, MR 1633290.
- ^ Westbrook, Jeffery ; Tarjan, Robert E. (1992), "Maintaining bridge-connected and biconnected components on-line", Algorithmica , 7 (5–6): 433–464, doi : 10.1007 / BF01758773 , MR 1154584.
- ^ a b Robbins, HE (1939), "Un teorema sobre gráficos, 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.
- ^ Jaeger, F. (1985), "Una revisión de la conjetura de la cubierta doble del ciclo", Annals of Discrete Mathematics 27 - Cycles in Graphs , North-Holland Mathematics Studies, 27 , pp. 1-12, doi : 10.1016 / S0304-0208 (08) 72993-1.
- ^ Tarjan, R. Endre (1974), "A note on find the bridges of a graph", Information Processing Letters , 2 (6): 160–161, doi : 10.1016 / 0020-0190 (74) 90003-9 , MR 0349483.
- ^ a b Schmidt, Jens M. (2013), "A Simple Test on 2-Vertex- and 2-Edge-Connectivity", Information Processing Letters , 113 (7): 241–244, arXiv : 1209.0700 , doi : 10.1016 / j.ipl .2013.01.016.