Nuestros desarrolladores estrellas agotaron sus depósitos de café, investigando todo el tiempo por la respuesta, hasta que Sebastián encontró el resultado en Gitea y hoy la comparte aquí.
Solución:
Encontrar vértices de articulación es una aplicación de DFS.
En una palabra,
- Aplicar DFS en un gráfico. Obtén el árbol DFS.
- Un nodo que se visita antes es un “padre” de los nodos a los que llega y se visita más tarde.
- Si algún hijo de un nodo no tiene una ruta a ninguno de los antepasados de su padre, significa que eliminar este nodo haría que este hijo se separe del gráfico.
- Hay una excepción: la raíz del árbol. Si tiene más de un hijo, entonces es un punto de articulación, de lo contrario no.
El punto 3 esencialmente significa que este nodo es un punto de articulación.
Ahora, para un niño, este camino a los antepasados del nodo sería a través de un back-edge de él o de cualquiera de sus hijos.
Todo esto se explica maravillosamente en este PDF.
Intentaré desarrollar una comprensión intuitiva de cómo funciona este algoritmo y también daré un pseudocódigo comentado que genere Bi-Componentes y puentes.
De hecho, es fácil desarrollar un algoritmo de fuerza bruta para los puntos de articulación. Simplemente saque un vértice y ejecute BFS o DFS en un gráfico. Si permanece conectado, entonces el vértice no es un punto de articulación, de lo contrario lo es. Esto se ejecutará en O(V(E+V)) = O(EV) tiempo. El desafío es cómo hacer esto en tiempo lineal (es decir, O(E+V)).
Los puntos de articulación conectan dos (o más) subgrafos. Esto significa que no hay bordes de un subgrafo a otro. Así que imagina que estás dentro de uno de estos subgrafos y visitas su nodo. A medida que visita el nodo, lo marca y luego pasa al siguiente nodo sin marcar utilizando algún borde disponible. Mientras hace esto, ¿cómo sabe que sigue dentro del mismo subgrafo? La idea aquí es que si está dentro del mismo subgrafo, eventualmente verá un nodo marcado a través de un borde mientras visita un nodo sin marcar. Esto se llama borde posterior e indica que tiene un ciclo. Tan pronto como encuentre un borde posterior, puede estar seguro de que todos los nodos a través de ese nodo marcado hasta el que está visitando en este momento son parte del mismo subgráfico y no hay puntos de articulación en el medio. Si no vio ningún borde posterior, todos los nodos que visitó hasta ahora son puntos de articulación.
Entonces, necesitamos un algoritmo que visite los vértices y marque todos los puntos entre el objetivo de los bordes posteriores como actualmente siendo visitado nodos como dentro del mismo subgrafo. Obviamente, puede haber subgrafos dentro de subgrafos, por lo que debemos seleccionar el subgrafo mas grande que tenemos hasta ahora. Estos subgrafos se denominan Bi-Componentes. Podemos implementar este algoritmo asignando a cada bicomponente un ID que se inicializa como un recuento del número de vértices que hemos visitado hasta ahora. Más tarde, cuando encontremos bordes posteriores, podemos restablecer el ID de dos componentes al más bajo que hemos encontrado hasta ahora.
Obviamente necesitamos dos pases. En la primera pasada, queremos averiguar qué vértice podemos ver desde cada vértice a través de los bordes posteriores, si los hay. En la segunda pasada, queremos visitar los vértices en la dirección opuesta y recopilar el ID mínimo de dos componentes (es decir, el antepasado más antiguo accesible desde cualquier descendiente). DFS naturalmente encaja aquí. En DFS bajamos primero y luego volvemos a subir para que las dos pasadas anteriores se puedan realizar en un solo recorrido DFS.
Ahora, sin más preámbulos, aquí está el pseudocódigo:
time = 0
visited[i] = false for all i
GetArticulationPoints(u)
visited[u] = true
u.st = time++
u.low = v.st //keeps track of highest ancestor reachable from any descendants
dfsChild = 0 //needed because if no child then removing this node doesn't decompose graph
for each ni in adj[i]
if not visited[ni]
GetArticulationPoints(ni)
++dfsChild
parents[ni] = u
u.low = Min(u.low, ni.low) //while coming back up, get the lowest reachable ancestor from descendants
else if ni <> parent[u] //while going down, note down the back edges
u.low = Min(u.low, ni.st)
//For dfs root node, we can't mark it as articulation point because
//disconnecting it may not decompose graph. So we have extra check just for root node.
if (u.low = u.st and dfsChild > 0 and parent[u] != null) or (parent[u] = null and dfsChild > 1)
Output u as articulation point
Output edges of u with v.low >= u.low as bridges
output u.low as bicomponent ID
Un hecho que parece quedar fuera de todas las explicaciones:
Hecho # 1: En un árbol de expansión de primera búsqueda en profundidad (DFSST), cada backge conecta un vértice con uno de sus ancestros.
Esto es esencial para que el algoritmo funcione, es por eso que un árbol de expansión arbitrario no funcionará para el algoritmo. También es la razón por la que la raíz es un punto de articulación si tiene más de 1 hijo: no puede haber un respaldo entre los subárboles enraizados en los hijos de la raíz del árbol de expansión.
Una prueba de la declaración es, sea (u, v) un respaldo donde u no es un antepasado de v, y (WLOG) u se visita antes que v en el DFS. Sea p el antepasado más profundo tanto de u como de v. Entonces el DFS tendría que visitar p, luego u, luego de alguna manera volver a visitar p antes de visitar v. Pero no es posible volver a visitar p antes de visitar v porque hay una ventaja entre u y v.
Llame a V (c) el conjunto de vértices en el subárbol enraizado en c en el DFSST
Llame a N (c) el conjunto de vértices para los que tiene un vecino en V (c)
Hecho # 2:
Para un nodo no raíz u,
Si u tiene un hijo c tal que N (c) ⊆ V (c) ∪ u entonces u es un punto de articulación.
Razón: para cada vértice w en V (c), cada camino desde la raíz hasta w debe contener u. De lo contrario, dicha ruta tendría que contener un borde posterior que conecte un antepasado de u con un descendiente de u debido al Hecho # 1, haciendo que N (c) sea más grande que V (c).
Hecho # 3:
El inverso del hecho # 2 también es true.
Razón: cada descendiente de u tiene una ruta a la raíz que no pasa por u. Un descendiente en V (c) puede desviar a u con una ruta a través de un respaldo que conecta V (c) con N (c) / V (c).
Entonces, para el algoritmo, solo necesita saber 2 cosas sobre cada vértice no raíz u:
- La profundidad del vértice, digamos D (u)
- La profundidad mínima de N (u), también llamada punto bajo, digamos L (u)
Entonces, si un vértice u tiene un hijo c, y L (c) es menor que D (u), entonces eso significa que el subárbol enraizado en c tiene un respaldo que llega a un ancestro de u, lo que lo convierte en un punto de articulación por Hecho # 3. A la inversa, también por el Hecho # 2.
Te mostramos las comentarios y valoraciones de los lectores
Recuerda dar visibilidad a este ensayo si si solucionó tu problema.