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 .
Algoritmos
Búsqueda en profundidad de tiempo lineal
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 idea es realizar una búsqueda en profundidad mientras se mantiene la siguiente información:
- la profundidad de cada vértice en el árbol de búsqueda de profundidad primero (una vez que se visita), y
- para cada vértice v , la profundidad más baja de los vecinos de todos los descendientes de v (incluido el propio v ) en el árbol de búsqueda de profundidad primero, llamado punto bajo .
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 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 el punto bajo ( y ) ≥ profundidad ( v ). Esta propiedad se puede probar una vez que la búsqueda en profundidad primero devuelva de cada hijo de v (es decir, justo antes de que v salga 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).
Pseudocódigo
GetArticulationPoints (i, d) visitado [i]: = verdadero profundidad [i]: = d bajo [i]: = d childCount: = 0 isArticulation: = falso para cada ni en adj [i] hacer si no se visita [ni] entonces padre [ni]: = i GetArticulationPoints (ni, d + 1) childCount: = childCount + 1 si baja [ni] ≥ profundidad [i] entonces es Articulación: = verdadero bajo [i]: = Mín (bajo [i], bajo [ni]) de lo contrario, si ni ≠ padre [i] entonces bajo [i]: = Mín (bajo [i], profundidad [ni]) si (padre [i] ≠ nulo e isArticulation) 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.
Otros algoritmos
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.
En la versión en línea del problema, los vértices y los bordes se agregan (pero no se eliminan) dinámicamente, y una estructura de datos debe mantener los componentes biconectados. Jeffery Westbrook y Robert Tarjan (1992) [3] 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 aristas 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) [4] diseñaron un algoritmo paralelo en CRCW PRAM que se ejecuta en tiempo O (log n ) con n + m procesadores.
Estructuras relacionadas
Relación de equivalencia
Uno puede definir una relación binaria en los bordes de un grafo no dirigido arbitraria, según la cual dos bordes e y f están relacionados si y sólo si, ya sea e = f o el gráfico contiene un ciclo simple a través tanto de e y f . Cada borde está relacionado consigo mismo, y un borde e está relacionado con otro borde f si y solo si f está relacionado de la misma manera con e . Menos obvio, esta es una relación transitiva : si existe un ciclo simple que contiene aristas e y f, y otro ciclo simple que contenga las 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 puede usarse 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 los bordes en cada clase de equivalencia son los componentes biconectados del grafo dado. Por tanto, los componentes biconectados dividen los bordes del gráfico; sin embargo, pueden compartir vértices entre sí. [5]
Gráfico de bloque
El gráfico de bloques de un gráfico G dado es el gráfico de intersección de sus bloques. Por lo tanto, tiene un vértice para cada bloque de G y un borde entre dos vértices siempre que los dos bloques correspondientes comparten 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 subgráficos completos. Las gráficas H con esta propiedad se conocen como gráficas de bloque . [6]
Árbol cortado en bloque
Un punto de corte , el vértice de corte , o punto de articulación de un gráfico G es un vértice que es compartida por dos o más bloques. La estructura de los bloques y los puntos de corte de un gráfico conectado se puede describir mediante un árbol llamado árbol cortado en 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 cortado en bloque para cada par de un bloque y un punto de articulación que pertenece a ese bloque. [7]
Los bloques son: b 1 = [1,2], b 2 = [2,3,4], b 3 = [2,5,6,7], b 4 = [7,8,9,10,11 ], b 5 = [8,12,13,14,15], b 6 = [10,16] yb 7 = [10,17,18];
los puntos de corte son: c 1 = 2, c 2 = 7, c 3 = 8 y c 4 = 10.
Ver también
- Componente triconectado
- Puente (teoría de grafos)
Notas
- ^ Hopcroft, J .; Tarjan, R. (1973). "Algoritmo 447: algoritmos eficientes para la manipulación de gráficos". Comunicaciones de la ACM . 16 (6): 372–378. doi : 10.1145 / 362248.362272 .
- ^ Schmidt, Jens M. (2013), "Una prueba simple sobre conectividad de 2 vértices y 2 bordes", Cartas de procesamiento de información , 113 (7): 241–244, arXiv : 1209.0700 , doi : 10.1016 / j. ipl.2013.01.016.
- ^ Westbrook, J .; Tarjan, RE (1992). "Mantenimiento en línea de componentes conectados en puente y biconectados". Algoritmica . 7 (1–6): 433–464. doi : 10.1007 / BF01758773 .
- ^ Tarjan, R .; Vishkin, U. (1985). "Un algoritmo de biconnectividad paralela eficiente". SIAM J. Comput. 14 (4): 862–874. CiteSeerX 10.1.1.465.8898 . doi : 10.1137 / 0214061 .
- ↑ Tarjan y Vishkin (1985) dan crédito a la definición de esta relación de equivalencia con Harary (1969) ; sin embargo, Harary no parece describirlo en términos explícitos.
- ^ Harary, Frank (1969), Teoría de grafos , Addison-Wesley, p. 29.
- ^ Harary (1969) , p. 36.
Referencias
- Eugene C. Freuder (1985). "Una condición suficiente para la búsqueda delimitada por el retroceso". Revista de la Asociación de Maquinaria Informática . 32 (4): 755–761. doi : 10.1145 / 4221.4225 .
enlaces externos
- Implementación C ++ de componentes biconectados
- Conectividad gráfica
