Componente biconectado
En la teoría de grafos , un componente biconectado (a veces conocido como componente de 2 conexiones ) es un subgrafo biconectado máximo . Cualquier gráfico conectado se descompone en un árbol de componentes biconectados llamado árbol cortado en bloques del gráfico. Los bloques están unidos entre sí en vértices compartidos llamados vértices de corte o vértices de separación o puntos de articulación . Específicamente, un vértice de corte es cualquier vértice cuya eliminación aumenta el número de componentes conectados .
El algoritmo secuencial clásico para calcular componentes biconectados en un gráfico conectado no dirigido se debe a John Hopcroft y Robert Tarjan (1973). [1] Se ejecuta en tiempo lineal y se basa en una búsqueda en profundidad . Este algoritmo también se describe como el problema 22-2 de Introducción a los algoritmos (tanto la segunda como la tercera edición).
La profundidad es estándar para mantener durante una búsqueda en profundidad. El punto bajo de v se puede calcular después de visitar todos los descendientes de v (es decir, justo antes de que v se elimine de la pila de búsqueda en profundidad ) como el mínimo de la profundidad de v , la profundidad de todos los vecinos de v (excepto el padre de v en el árbol de búsqueda en profundidad primero) y el punto bajo de todos los hijos de v en el árbol de búsqueda en profundidad primero.
El hecho clave es que un vértice sin raíz v es un vértice cortado (o punto de articulación) que separa dos componentes biconectados si y solo si hay un hijo y de v tal que el punto bajo ( y ) ≥ profundidad ( v ). Esta propiedad se puede probar una vez que la búsqueda en profundidad primero devuelve cada hijo de v (es decir, justo antes de que v se elimine de la pila de búsqueda en profundidad), y si es verdadera , v separa el gráfico en diferentes componentes biconectados. Esto se puede representar calculando un componente biconectado de cada y (un componente que contiene y contendrá el subárbol dey , más v ), y luego borrando el subárbol de y del árbol.
El vértice raíz debe manejarse por separado: es un vértice cortado si y solo si tiene al menos dos hijos en el árbol DFS. Por lo tanto, basta con crear un componente de cada subárbol secundario de la raíz (incluida la raíz).
Una alternativa simple al algoritmo anterior usa descomposiciones en cadena , que son descomposiciones especiales del oído que dependen de los árboles DFS . [2] Las descomposiciones en cadena se pueden calcular en tiempo lineal mediante esta regla de desplazamiento . Deje C ser una descomposición de la cadena de G . Entonces G está conectado-2-vértice si y sólo si G tiene mínimo grado 2 y C 1 es el único ciclo en C . Esto proporciona inmediatamente una prueba de 2 conectividad de tiempo lineal y se puede ampliar para enumerar todos los vértices cortados de Gen tiempo lineal utilizando la siguiente instrucción: Un vértice v en un gráfico conectado G (con grado mínimo 2) es un vértice de corte si y sólo si v es incidente a un puente o v es el primer vértice de un ciclo en C - C 1 . La lista de vértices cortados se puede utilizar para crear el árbol cortado en bloque de G en tiempo lineal.
