Talk:Biconnected component

Lowpoint

"The key fact is that a nonroot vertex v is a cut vertex (or articulation point) separating two biconnected components if and only if v's lowpoint is at least as large as v's depth". This is not correct.

For instance if the depth-first-search tree is like:

    T
    |
    x
   / \
  A   B

i.e, T is a tree, x is a node (not the root), A and B are subtrees.

If there is a backward edge from a node of A to a node of T, then lowpoint(x) < depth(x) so according to the previous characterization, x can not be a cut vertex. But if there is no backward edge from B to T then x is actually a cut vertex (removing x separate B from T) so the characterization is not correct.

I think it should be : "a non-root vertex x is a cut vertex iff there is no son y of x such that lowpoint(y) >= depth(x)".

In your example, depth(x) = 2 and lowpoint(A) = lowpoint(B) = 3. The terminology is a bit confusing. Bobmath (talk) 14:00, 18 May 2015 (UTC)

Cut Vertex

IMO, it would be more appropriate for cut vertex, et al., to redirect to Connected component (graph theory). Justin W Smith ^talk/_stalk 23:55, 11 July 2010 (UTC)

C++ example

The C++ example seems misleading and complex to me, although it directly translates the . What about a shorter recursive pseudocode like this:

neither your example nor the pseudo code on the wiki page seemed to work for me. 130.149.232.36 (talk) 12:29, 30 July 2015 (UTC)

mark_lowpoint(node, parent, depth)
    if not visited[node]:
        if parent = root:
            ++root_children
        visited[node] := true
        min_depth_lowpoints := depth
        for n in neighbours[node]
            l := mark_lowpoint(node, depth+1)
            if l >= depth and node != root:
                articulation_point[node] := true
            min_depth_lowpoints := min(l, min_depth_lowpoints)
        lowpoint[node] := min_depth_lowpoints;
    return lowpoint[node]

root_children := 0
articulation_point := [false, ...]
visited            := [false, ...]

mark_lowpoint(root, ..., 0)

if root_children >= 2:
    articulation_point[root] := true

The provided algorithm seems to be wrong

"The root vertex must be handled separately: it is a cut vertex if and only if it has at least two children. Thus, it suffices to simply build one component out of each child subtree of the root (including the root)." seems to be wrong.

If you consider graph:

   a
 /   \
b     c
 \   /
   d

You can start algorithm execution from vertex a, making it a root of DFS tree. It meets the requirement of "it is a cut vertex if and only if it has at least two children." but it's not an articulation point. Yet it would meet the condition

(parent[i] <> null and isArticulation) or (parent[i] == null and childCount > 1)

In my opinion it should be The root vertex must be handled separately: it may be a cut vertex if and only if it has at least two children.

The final condition should be

(parent[i] <> null and isArticulation) or (parent[i] == null and isArticulation and childCount > 1)

But I might be wrong.

EDIT: Nevermind, I was wrong, in this case the child count of a will be 1. Making the pseudo code correct.

Jaroslaw.mroz (talk) 09:18, 23 February 2018 (UTC)

Edge case missing

If the whole graph consists of a single edge (A,B), then there is no articulation point (correct), but (A,B) should be a biconnected component. Not sure how/where to add this. 46.5.2.53 (talk) 08:46, 14 November 2018 (UTC)

In the Diestel Book, a block is defined as a maximal connected vertex without cutvertex. So it includes biconnected components, bridges, and isolated vertices. With this definition it seems to work. Calin-info (talk) 17:42, 14 August 2019 (UTC)

References

In what sense is this a missing case? It seems to be adequately covered by the definitions in the article. —David Eppstein (talk) 18:20, 14 August 2019 (UTC)

You are right, I got biconnected and 2-connected mixed up Calin-info (talk) 16:16, 1 September 2019 (UTC)

The pseudocode still does not work

I tried to implement the pseudocode in C++ being as closely as possible but the results are wrong. I suggest to take inspiration from the C++ code at [1]https://codeforces.com/blog/entry/71146 for working algorithm. In particular, the pseudocode in the original article is more similar to the one I suggested than the one currently on wikipedia. 2001:B07:AA7:FB42:FC19:720B:F26C:BD9B (talk) 08:52, 6 November 2024 (UTC)