En teoría de grafos , un componente biconectado (a veces conocido como componente biconexo ) es un subgrafo biconectado máximo . Cualquier gráfico conectado se descompone en un árbol de componentes biconectados llamado árbol de corte en bloque 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 cortado es cualquier vértice cuya eliminación aumenta el número de componentes conectados . [1]
El algoritmo secuencial clásico para calcular componentes biconectados en un grafo conexo no dirigido se debe a John Hopcroft y Robert Tarjan (1973). [2] Se ejecuta en tiempo lineal y se basa en la 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 idea es realizar una búsqueda en profundidad manteniendo la siguiente informació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 salga 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 (aparte de el padre de v en el árbol de búsqueda en profundidad) y el punto bajo de todos los hijos de v en el árbol de búsqueda en profundidad.
El hecho clave es que un vértice v no raíz 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 punto bajo ( y ) ≥ profundidad ( v ) . Esta propiedad se puede probar una vez que la búsqueda en profundidad haya regresado de cada hijo de v (es decir, justo antes de que v salga de la pila de búsqueda en profundidad), y si es verdadero , v separa el gráfico en diferentes componentes biconectados. Esto se puede representar calculando un componente biconectado de cada uno de esos y (un componente que contiene y contendrá el subárbol de y , 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 sólo si tiene al menos dos hijos en el árbol DFS. Por lo tanto, basta con construir un componente a partir de cada subárbol hijo de la raíz (incluida la raíz).
GetArticulationPoints(i, d) visitado[i] := verdadero profundidad[i] := d bajo[i] := d niñoCuenta := 0 esArticulación: = falso para cada ni en adj[i] hazlo si no lo visitaste[ni] entonces padre[ni] := yo Obtener puntos de articulación (ni, d + 1) niñoContar := niñoContar + 1 si bajo [ni] ≥ profundidad [i] entonces esArticulación: = verdadero bajo[i] := Min (bajo[i], bajo[ni]) de lo contrario, si ni ≠ padre [i] entonces bajo[i] := Min (bajo[i], profundidad[ni]) si (padre[i] ≠ nulo y isArticulación) o (padre[i] = nulo y childCount > 1) entonces Salida i como punto de articulación
Tenga en cuenta que los términos hijo y padre denotan las relaciones en el árbol DFS, no el gráfico original.
Una alternativa simple al algoritmo anterior utiliza descomposiciones en cadena , que son descomposiciones de oreja especiales que dependen de los árboles DFS . [3] Las descomposiciones en cadena se pueden calcular en tiempo lineal mediante esta regla transversal . Sea C una descomposición en cadena de G . Entonces G está conectado por 2 vértices si y solo si G tiene un grado mínimo 2 y C 1 es el único ciclo en C . Esto da inmediatamente una prueba de conectividad 2 en tiempo lineal y se puede extender para enumerar todos los vértices cortados de G en tiempo lineal usando la siguiente declaración: Un vértice v en un gráfico conectado G (con grado mínimo 2) es un vértice cortado si y sólo si v incide en 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 bloques de G en tiempo lineal.
En la versión en línea del problema, los vértices y aristas se agregan (pero no se eliminan) dinámicamente, y una estructura de datos debe mantener los componentes biconectados. Jeffery Westbrook y Robert Tarjan (1992) [4] desarrollaron una estructura de datos eficiente para este problema basada en estructuras de datos de conjuntos disjuntos . Específicamente, procesa n adiciones de vértices y m adiciones de bordes en O ( m α ( m , n )) tiempo total, donde α es la función de Ackermann inversa . Se ha demostrado que este límite de tiempo es óptimo.
Uzi Vishkin y Robert Tarjan (1985) [5] diseñaron un algoritmo paralelo en CRCW PRAM que se ejecuta en tiempo O (log n ) con n + m procesadores.
Se puede definir una relación binaria en los bordes de un gráfico arbitrario no dirigido, según la cual dos bordes e y f están relacionados si y solo si e = f o el gráfico contiene un ciclo simple a través de e y f . Cada arista está relacionada consigo misma, y una arista e está relacionada con otra arista f si y sólo si f está relacionada de la misma manera con e . De manera menos obvia, esta es una relación transitiva : si existe un ciclo simple que contiene aristas e y f , y otro ciclo simple que contiene aristas f y g , entonces se pueden combinar estos dos ciclos para encontrar un ciclo simple a través de e y g . Por lo tanto, esta es una relación de equivalencia y se puede usar para dividir las aristas en clases de equivalencia, subconjuntos de aristas con la propiedad de que dos aristas están relacionadas entre sí si y solo si pertenecen a la misma clase de equivalencia. Los subgrafos formados por las aristas en cada clase de equivalencia son los componentes biconectados del gráfico dado. Así, los componentes biconectados dividen los bordes del gráfico; sin embargo, pueden compartir vértices entre sí. [6]
El gráfico de bloques de un gráfico dado G es el gráfico de intersección de sus bloques. Por tanto, tiene un vértice para cada bloque de G y una arista entre dos vértices siempre que los dos bloques correspondientes compartan un vértice. Un gráfico H es el gráfico de bloques de otro gráfico G exactamente cuando todos los bloques de H son subgrafos completos. Los gráficos H con esta propiedad se conocen como gráficos de bloques . [7]
Un punto de corte , vértice de corte o punto de articulación de un gráfico G es un vértice compartido por dos o más bloques. La estructura de los bloques y puntos de corte de un gráfico conectado se puede describir mediante un árbol llamado árbol de corte de bloques o árbol BC . Este árbol tiene un vértice para cada bloque y para cada punto de articulación del gráfico dado. Hay un borde en el árbol de corte de bloques para cada par de bloques y un punto de articulación que pertenece a ese bloque. [8]
Un vértice de corte es un vértice que, si se elimina, aumenta la cantidad de componentes de la red.
{{cite book}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace )