Puente (teoría de grafos)
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 .
Un gráfico con nodos puede contener como máximo puentes, ya que agregar bordes adicionales debe crear un ciclo. Los gráficos con exactamente 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, disjuntos 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]
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 que están conectados por 2 bordes, los gráficos sin vértices de articulación están conectados por 2 vértices .
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]
