Talk:Biconnected component

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Computer science (Rated Start-class)
WikiProject icon This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Start-Class article Start  This article has been rated as Start-Class on the project's quality scale.
 ???  This article has not yet received a rating on the project's importance scale.
 
WikiProject Mathematics (Rated Start-class, Mid-priority)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
Start Class
Mid Priority
 Field: Discrete mathematics

"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)".

Cut Vertex[edit]

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[edit]

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

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