algorithm - superponer - Explicación del algoritmo para encontrar puntos de articulación o cortar vértices de un gráfico

superponer graficas en r ggplot

Question

He buscado en la red y no he podido encontrar ninguna explicación de un algoritmo DFS para encontrar todos los vértices de articulación de un gráfico. Ni siquiera hay una página wiki.

Después de leer todo, llegué a conocer los hechos básicos desde aquí. PDF

Hay una variable en cada nodo que está mirando los bordes traseros y buscando el nodo más cercano y más alto hacia el nodo raíz. Después de procesar todos los bordes se encontraría.

Pero no entiendo cómo encontrar esta variable hacia abajo y hacia arriba en cada nodo durante la ejecución de DFS. ¿Qué está haciendo esta variable exactamente?

Por favor explica el algoritmo.

Gracias.

Answer 1

Encontrar vértices de articulación es una aplicación de DFS.

En una palabra,

1. Aplicar DFS en un gráfico. Obtener el árbol DFS.
2. Un nodo que se visita anteriormente es un "padre" de esos nodos a los que llega y se visita posteriormente.
3. Si un elemento secundario de un nodo no tiene una ruta a ninguno de los antecesores de su elemento primario, significa que al eliminar este nodo, este elemento secundario se separaría del gráfico.
4. Hay una excepción: la raíz del árbol. Si tiene más de un niño, 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 borde posterior de él o de cualquiera de sus hijos.

Todo esto se explica bellamente en este PDF .

Answer 2

Si el valor low del descendiente de u es mayor que el dfsnum de u , entonces u se dice que es el punto de articulación.

int adjMatrix[256][256];
int low[256], num=0, dfsnum[256];

void cutvertex(int u){
    low[u]=dfsnum[u]=num++;
    for (int v = 0; v < 256; ++v)
    {
        if(adjMatrix[u][v] && dfsnum[v]==-1)
        {
            cutvertex(v);
            if(low[v]>dfsnum[u])    
                cout<<"Cut Vertex: "<<u<<"/n";
            low[u]=min(low[u], low[v]);
        }
        else{
            low[u]=min(low[u], dfsnum[v]);
        }
    }
}

Answer 3

Trataré de desarrollar una comprensión intuitiva sobre cómo funciona este algoritmo y también dar un pseudocódigo comentado que da salida tanto a Bi-Components como a bridges.

De hecho, es fácil desarrollar un algoritmo de fuerza bruta para los puntos de articulación. Solo saca un vértice y ejecuta 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. Entonces imagina que estás dentro de uno de estos subgrafos y visitando su nodo. Cuando visita el nodo, lo marca y luego pasa al siguiente nodo sin marcar con algún borde disponible. Mientras haces esto, ¿cómo sabes que estás dentro del mismo subgráfico? 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 no marcado. Esto se llama borde posterior e indica que tienes un ciclo. Tan pronto como encuentre un borde posterior, puede estar seguro de que todos los nodos a través de ese nodo marcado al que está visitando en este momento son todos 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 todos puntos de articulación.

Por lo tanto, necesitamos un algoritmo que visite los vértices y marque todos los puntos entre el objetivo de los bordes posteriores y los nodos que se están visitando actualmente dentro del mismo subgráfico. Obviamente, puede haber subgrafos dentro de subgrafos, entonces tenemos que seleccionar el subgrafo mas grande que tenemos hasta ahora. Estos subgrafos se llaman Bi-Componentes. Podemos implementar este algoritmo asignando a cada bi componente una ID que se inicializa como solo un recuento de la cantidad de vértices que hemos visitado hasta ahora. Más tarde, cuando encontremos bordes traseros, podemos restablecer la identificación de bi-compinent al mínimo 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 hay alguno. En el segundo pase, queremos visitar vértices en la dirección opuesta y recoger la identificación mínima de dos componentes (es decir, el ancestro más antiguo accesible desde cualquier descendiente). DFS naturalmente cabe aquí. En DFS bajamos primero y luego volvemos a subir para que ambos pases anteriores se puedan realizar en un solo cruce 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