Wikipedia
Un grafo de ejemplo con el vértice de corte marcado. Cada color corresponde a un vértice de corte. vértices multicolores se cortan vértices, y por lo tanto pertenecen a varios vértice de corte.En la teoría de grafos, un vértice de corte (también conocido como un bloque o componente 2-conectado) es un subgrafo máximo biconexas. Cualquier grafo conexo se descompone en un árbol del vértice de corte llamado el árbol de corte de bloque del grafo. Los bloques están unidos entre sí en los vértices compartidos llamados vértices de corte 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
El tiempo lineal profundidad primera búsqueda
El algoritmo secuencial clásica para el cálculo de vértice de corte en un grafo no dirigido conectada se debe a John Hopcroft y Robert Tarjan (1973). [1] Se ejecuta en tiempo lineal, y se basa en la búsqueda en profundidad. Este algoritmo también se perfila como un Problem 22-2 de su Introduction to Algorithms (tanto 2ª y 3ª ediciones).La idea es ejecutar una búsqueda en profundidad mientras se mantiene la siguiente información:
- la profundidad de cada vértice en el árbol de profundidad-primero-búsqueda (una vez que se visitó), y
- para cada vértice v, la profundidad más baja de los vecinos de todos los descendientes de v en el árbol de profundidad primera búsqueda, llamado el punto más bajo.
La profundidad es estándar para mantener durante una búsqueda en profundidad. El punto más bajo de v puede calcularse después de visitar todos los descendientes de v (es decir, justo antes de v se apareció de la pila profundidad-primero-búsqueda) como el mínimo de la profundidad de v, la profundidad de todos los vecinos de v (aparte de la padre de v en el árbol de la profundidad de primera búsqueda) y el punto más bajo de todos los hijos de v en el árbol de la profundidad de primera búsqueda.
La clave es que un vértice no raíz v es un vértice de corte (o punto de articulación) que separa dos vértice de corte si y sólo si hay un niño y de v tal que si profundidad ≥ punto más bajo (y) (v). Esta propiedad puede ser probado una vez que la búsqueda en profundidad regresó de cada hijo de v (es decir, justo antes de v se hizo estallar de la pila de profundidad primera búsqueda), y si es verdad, v separa el grafo en diferentes vértice de corte. Esto se puede representar mediante el cálculo de un vértice de corte de cada uno de estos y (un componente que contiene y contendrá el subárbol de y, además v) y, a continuación, borrar el subárbol de y del árbol.
El vértice de la raíz debe ser manejado por separado: es un vértice de corte si y sólo si tiene al menos dos hijos. Por lo tanto, basta con simplemente construir un componente de cada subárbol hijo de la raíz (incluyendo la raíz).
Pseudocódigo
GetArticulationPoints(i, d)visited[i] = true
depth[i] = d
low[i] = d
childCount = 0
isArticulation = false
for each ni in adj[i]
if not visited[ni]
parent[ni] = i
GetArticulationPoints(ni, d + 1)
childCount = childCount + 1
if low[ni] >= depth[i]
isArticulation = true
low[i] = Min(low[i], low[ni])
else if ni <> parent[i]
low[i] = Min(low[i], depth[ni])
if (parent[i] <> null and isArticulation) or (parent[i] == null and childCount > 1)
Output i as articulation point
Otros algoritmos
Una alternativa simple al algoritmo anterior utiliza descomposiciones de la cadena, que son descomposiciones especiales para los oídos en función de árboles DFS. [2] Las descomposiciones de cadena se pueden calcular en tiempo lineal por esta regla de desplazamiento. Sea C una descomposición de la cadena de G. Entonces se conecta-2-vértice G si y sólo si G tiene grado mínimo 2 y C1 es el único ciclo en C. Esto da inmediatamente una prueba de 2-conectividad en tiempo lineal y se puede ampliar listar todos los vértices de corte de G en el tiempo lineal utilizando la siguiente instrucción: un vértice v en un grafo conexo 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 - C1. La lista de los vértices de corte se puede utilizar para crear el árbol de bloque de corte de G en el tiempo lineal.En la versión en línea del problema, se añaden vértices y aristas (pero no eliminado) de forma dinámica, y una estructura de datos deben mantener las vértice de corte. Jeffery Westbrook y Robert Tarjan (1992) [3] desarrollaron una estructura de datos eficiente para este problema sobre la base de estructuras de datos disjuntos-set. En concreto, se procesa n vértices adiciones y adiciones m de borde en O (m α (m, n)) tiempo total, donde α es la función inversa Ackermann. Esta vez unida se demostró ser óptima.
Uzi Vishkin y Robert Tarjan (1985) [4] diseñaron un algoritmo paralelo en CRCW PRAM que se ejecuta en O (log n) tiempo con n + m procesadores. Guojing Cong y David A. Bader (2005) [5] desarrollaron un algoritmo que logra una aceleración de 5 con 12 procesadores en SMP. Aceleraciones superiores a 30 basado en el algoritmo original Tarjan-Vishkin fueron reportados por James A. Edwards y Uzi Vishkin (2012). [6]
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 relacionadas si y sólo si, ya sea e = f o el grafo contiene un ciclo simple tanto a través de e y f. Cada borde está relacionada a sí mismo, y un borde e está relacionado con otro borde f si y sólo si f está relacionado de la misma manera a E, menos evidente, esta es una relación transitiva: si existe un ciclo simple que contiene bordes e y f, y otro ciclo simple que contiene bordes F y g, entonces se pueden combinar estos dos ciclos de encontrar un ciclo simple a través de e y g. Por lo tanto, esta es una relación de equivalencia, y que puede ser utilizado para dividir los bordes en clases de equivalencia, los subconjuntos de los bordes con la propiedad de que dos bordes están relacionados entre sí, si y sólo si pertenecen a la misma clase de equivalencia. Los subgraphs formados por los bordes de cada clase de equivalencia son los vértice de corte de la grafo dada. Por lo tanto, los vértice de corte partición de los bordes de la grafo; sin embargo, pueden compartir vértices entre sí. [7]Grafo de bloque
El grafo de bloques de un grafo dado G es el grafo 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 las correspondientes dos bloques comparten 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 grafo H con esta propiedad son conocidos como los grafos de bloque. [8]Árbol de bloque de corte
Un punto de un grafo de G punto de corte, el vértice de corte, o la articulación 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 grafo conectado puede ser descrita por un árbol llamado el árbol de bloque de corte o árbol de BC. Este árbol tiene un vértice para cada bloque y para cada punto del grafo dada la articulación. Hay una ventaja en el árbol de bloque de corte para cada par de un bloque y un punto de articulación que pertenece a ese bloque. [9]Notas
- Hopcroft, J.; Tarjan, R. (1973). "Algorithm 447: efficient algorithms for graph manipulation". Communications of the ACM. 16 (6): 372–378. doi:10.1145/362248.362272.
- Schmidt, Jens M. (2013), "A Simple Test on 2-Vertex- and 2-Edge-Connectivity", Information Processing Letters, 113 (7): 241–244, doi:10.1016/j.ipl.2013.01.016.
- Westbrook, J.; Tarjan, R. E. (1992). "Maintaining bridge-connected and biconnected components on-line". Algorithmica. 7: 433–464. doi:10.1007/BF01758773.
- Tarjan, R.; Vishkin, U. (1985). "An Efficient Parallel Biconnectivity Algorithm". SIAM J. Comput. 14 (4): 862–874. doi:10.1137/0214061.
- Guojing Cong and David A. Bader, (2005). "An Experimental Study of Parallel Biconnected Components Algorithms on Symmetric Multiprocessors (SMPs)". Proceedings of the 19th IEEE International Conference on Parallel and Distributed Processing Symposium. pp. 45b. doi:10.1109/IPDPS.2005.100.
- Edwards, J. A.; Vishkin, U. (2012). "Better speedups using simpler parallel programming for graph connectivity and biconnectivity". Proceedings of the 2012 International Workshop on Programming Models and Applications for Multicores and Manycores - PMAM '12. p. 103. doi:10.1145/2141702.2141714. ISBN 9781450312110.
- Tarjan & Vishkin (1985) credit the definition of this equivalence relation to Harary (1969); however, Harary does not appear to describe it in explicit terms.
- Harary, Frank (1969), Graph Theory, Addison-Wesley, p. 29.
- Harary (1969), p. 36.
No hay comentarios:
Publicar un comentario