En teoría de grafos , un componente o bloque biconexo (a veces conocido como componente 2-conexo ) es un subgrafo biconexo maximal . Cualquier grafo conexo se descompone en un árbol de componentes biconexos llamado árbol de corte de bloques del grafo. 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 conexos . [1] Un bloque que contiene como máximo un vértice de corte se llama bloque hoja , corresponde a un vértice hoja en el árbol de corte de bloques.
El algoritmo secuencial clásico para calcular componentes biconectados en un grafo no dirigido conectado 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 2.ª como la 3.ª edición).
La idea es ejecutar una búsqueda en profundidad manteniendo la siguiente información:
La profundidad es un parámetro estándar que se debe mantener durante una búsqueda en profundidad. El punto más bajo de v se puede calcular después de visitar todos los descendientes de v (es decir, justo antes de que v se extraiga 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) y el punto más bajo de todos los hijos de v en el árbol de búsqueda en profundidad.
El hecho clave es que un vértice no raíz v es un vértice de corte (o punto de articulación) que separa dos componentes biconectados si y solo si hay un hijo y de v tal que lowpoint( y ) ≥ depth( v ) . Esta propiedad se puede probar una vez que la búsqueda en profundidad devuelve el resultado de cada hijo de v (es decir, justo antes de que v se extraiga de la pila de búsqueda en profundidad), y si es true , 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 de corte si y solo 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 número de hijos := 0 esArticulacion := falso para cada ni en adj[i] hacer si no visitado[ni] entonces padre[ni] := i ObtenerPuntosDeArticulación(ni, d + 1) número de hijos := número de hijos + 1 si low[ni] ≥ depth[i] entonces isArticulation := true bajo[i] := Mín (bajo[i], bajo[ni]) de lo contrario si ni ≠ padre[i] entonces bajo[i] := Min (bajo[i], profundidad[ni]) si (parent[i] ≠ null y isArticulation) o (parent[i] = null 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 en el gráfico original.
Una alternativa simple al algoritmo anterior utiliza descomposiciones en cadena , que son descomposiciones especiales de orejas que dependen de árboles DFS . [3] Las descomposiciones en cadena se pueden calcular en tiempo lineal mediante esta regla de recorrido . Sea C una descomposición en cadena de G. Entonces G es 2-vértices-conexos si y solo si G tiene un grado mínimo de 2 y C 1 es el único ciclo en C. Esto da inmediatamente una prueba de 2-conectividad en tiempo lineal y se puede extender para enumerar todos los vértices de corte de G en tiempo lineal utilizando la siguiente declaración: Un vértice v en un grafo conexo G (con un grado mínimo de 2) es un vértice de corte si y solo 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 de corte se puede utilizar para crear el árbol de corte de bloques 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) [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 inversa de Ackermann . 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 las aristas de un grafo arbitrario no dirigido, según la cual dos aristas e y f están relacionadas si y solo si e = f o el grafo contiene un ciclo simple que pasa por e y f . Cada arista está relacionada consigo misma, y una arista e está relacionada con otra arista f si y solo 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 que pasa por 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 biconexos del grafo dado. Por lo tanto, los componentes biconexos dividen las aristas del grafo; sin embargo, pueden compartir vértices entre sí. [6]
El grafo de bloques de un grafo G dado es el grafo de intersección de sus bloques. Por lo tanto, tiene un vértice por cada bloque de G y una arista entre dos vértices siempre que los dos bloques correspondientes compartan un vértice. Un grafo H es el grafo de bloques de otro grafo G exactamente cuando todos los bloques de H son subgrafos completos. Los grafos H con esta propiedad se conocen como grafos de bloques . [7]
Un punto de corte , vértice de corte o punto de articulación de un grafo G es un vértice que comparten dos o más bloques. La estructura de los bloques y puntos de corte de un grafo conexo 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 grafo dado. Hay una arista en el árbol de corte de bloques para cada par de un bloque 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 el número de componentes de la red.
{{cite book}}: CS1 maint: varios nombres: lista de autores ( enlace )