точка сочленения игнорирует обратный край, ведущий к прямому родителю

Question

Из алгоритма Принстона Точка сочленения алгоритм сочленения dfs () игнорирует обратный край, ведущий к v. Но почему мы не можем использовать обратный край, когда он указывает на прямого родителя? Пожалуйста, обратитесь к этой части кода

    // **low number - ignore reverse of edge leading to v. Why is this???**
    else if (w != u)
        low[v] = Math.min(low[v], pre[w]);

Полный код ниже.

private void dfs(Graph G, int u, int v) {
    int children = 0;
    pre[v] = cnt++;
    low[v] = pre[v];
    for (int w : G.adj(v)) {
        if (pre[w] == -1) {
            children++;
            dfs(G, v, w);

            // update low number
            low[v] = Math.min(low[v], low[w]);

            // non-root of DFS is an articulation point if low[w] >= pre[v]
            if (low[w] >= pre[v] && u != v) 
                articulation[v] = true;
        }

        // **low number - ignore reverse of edge leading to v. Why is this???**
        else if (w != u)
            low[v] = Math.min(low[v], pre[w]);
    }

    // root of DFS is an articulation point if it has more than 1 child
    if (u == v && children > 1)
        articulation[v] = true;
}

Answer 1

По определению этого алгоритма ( link-1 ):

• pre [v] - это индекс DFS-preorder для v, другими словами,глубина этой вершины в дереве DFS;
• low [v] - самая низкая глубина соседей всех потомков v (включая самого v) в дереве DFS

Таким образом, во время вызова DFS(G, u, v) мы не должны проверять обратный край (v->u), потому что вершина u является предком из v, поэтому ее не следует учитывать при вычислении low[v].

Дополнительное объяснение можно найти здесь: ссылка-2