4
$\begingroup$

My question relates to Problem 22.-2 in Introduction to Algorithms 3rd edition.

There biconnected components are defined as maximal sets of edges such that any two edges in the set lie on a common simple cycle. The problems that I am having are the last two tasks of this problem, namely

  1. proving that biconnected components of a graph partition the nonbridge edges of the grap (where a nonbridge is an edge which can be omitted without disconnecting the graph)
  2. computing the biconnected components.

The first task seems rather easy since one could argue that "any nonbridge has to lie on some simple cylce and is therefore in a biconnected component" and that "if two biconnected components were to share an edge they would be the same biconnected component since one can then construct a path through any pair of edges". However, here I find the second argument too unspecific: How would this path look like? How can I really argue about that since any edge on the constructed path might be in both components.

To make it clearer, a picture: enter image description here

Clearly, I can construct such a simple cycle here always, but what if some red edges were also blue? Wouldn't that blow up the whole proof?

The problem I am having with (2) is of a similar nature. Before the problem definition in the book, the concept of articulation points is introduced. These are defined a vertices whose removal disconnect a previously connected graph.

Solutions I found on the internet of the "computing biconncted components"-task (such as the linear-time algorithm in https://en.wikipedia.org/wiki/Biconnected_component or 22.-2 h in https://sites.math.rutgers.edu/~ajl213/CLRS/Ch22.pdf) argue that "removing all articulation points respectively bridges yields the biconnected components of the graph". However, if I have the following graphenter image description here

a removal of x would disconnect the graph whereas a removal of y would not. However, of the remaining graph (i.e. without x), y is an articulation point and there is no simple cycle on which e and f both lie (since y has to be visited twice in every cycle meaning it is not simple anymore). So removing articulation points alone does not suffice. The same applies to removing bridges alone with the upper graph.

How would I fix these problems?

PS:

enter image description here

PPS:

enter image description here

$\endgroup$
4
  • $\begingroup$ As you probably suspected, sites.math.rutgers.edu/~ajl213/CLRS/Ch22.pdf is wrong when it says at Problem 22-2 g "... This means $a, b,$ $p_1,\ldots, p_k,$ $u,$ $q_m,\ldots, q_1,$ $d, c,$ $q_l,\ldots, q_{m+1}$, $v,$ $p_{k+1}, \ldots, p_{n}$, $a$ is a simple cycle containing $(a, b)$ and $(c, d)$", since that cycle might not be simple. $\endgroup$
    – John L.
    Jul 20, 2022 at 18:56
  • $\begingroup$ Problem 22-2 f at sites.math.rutgers.edu/~ajl213/CLRS/Ch22.pdf is wrong when it starts with "A edge $(u, v)$ lies on a simple cycle in an undirected graph if and only if either both of its endpoints are articulation points, ...". It is still wrong even if we replace "lies on a simple cycle " by "is a bridge", as illustrated by the second last graph in the question $\endgroup$
    – John L.
    Jul 21, 2022 at 19:00
  • $\begingroup$ Problem 22-2 h at sites.math.rutgers.edu/~ajl213/CLRS/Ch22.pdf says "Remove each bridge from $E$. The biconnected components are now simply the edges in the connected components". That is wrong as illustrated by the last graph in the question $\endgroup$
    – John L.
    Jul 21, 2022 at 19:06
  • $\begingroup$ Thanks for the questions. It turns out both questions, although look simple and clear intuitively, are somewhat tricky. $\endgroup$
    – John L.
    Jul 21, 2022 at 19:36

1 Answer 1

2
$\begingroup$

Two different biconnected components does not share an edge

Claim: Let edge $u$ lie on simple cycle $\mathcal C_u$. Let edge $v$ lie on simple cycle $\mathcal C_v$. $\mathcal C_u$ and $\mathcal C_v$ share an edge. Then $u$ and $v$ must lie on a common simple cycle.

Proof: If $v$ is on $\mathcal C_u$, we are done. So, assume $v$ is not on $\mathcal C_u$.

Let us visit the edges of $\mathcal C_v$ starting at $v$ on one direction, until we reach an edge on $\mathcal C_u$ the first time. We must be able to reach such an edge, since $\mathcal C_u$ and $\mathcal C_v$ share an edge.
Do the same on the other direction.
The edges we have visited, slightly reordered, can be seen as a path on $\mathcal C_v$: $f_{i+1}, f_i, \cdots, f_2, f_1, v, e_1, e_2, \cdots, e_j, e_{j+1}$, where

  • $i\ge0$, $j\ge0$, $f_*$ and $e_*$ are edges, and
  • the sequence $P_v$: $f_i, \cdots, f_2, f_1, v, e_1, e_2, \cdots, e_j$ is a a simple path on $C_v$ that is disjoint with $\mathcal C_u$ and,
  • Both $f_{i+1}$ and $e_{j+1}$ are on $\mathcal C_v$ and on $\mathcal C_v$.

There are two cases.

  • If $f_{i+1}$ and $e_{j+1}$ are the same edge, this is the simple case illustrated by the first graph in the question.
  • Otherwise, $f_{i+1}$ and $e_{j+1}$ are different. Since both edges are on $\mathcal C_u$, there is a simple path $P_u$ on $\mathcal C_u$ from one endpoint of $f_{i+1}$, say $x$, to one endpoint of $e_{j+1}$, say $y$, that includes edge $u$.
    Let us start at edge $v$, travelling along the $f_*$ edges until we reach $x$, then travelling along the $P_u$ until we reach point $y$, then travelling along the $e_*$ edges back to edge $v$. We can verify that the edges we have thus visited is a simple cycle that contains both $u$ and $v$. (This cycle may or may not contain $f_{i+1}$. It may or may not contain $e_{j+1}$. It does contain $P_v$ and $P_u$.) $\checkmark$

The claim and its constructive proof above explains that "if two biconnected components were to share an edge they would be the same biconnected component since one can then construct a path through any pair of edges".

Two or more different biconnected components may share an articulation point

It looks like you misunderstand what you have read about "computing biconncted components".

Suppose we are given a graph $G$.

While $G$ is a disjoint union of its connected components, it is NOT necessarily a disjoint union of its biconnected components.

An articulation point of $G$ is a point that joins two or more different biconnected components ("joins" instead of "separates" is used so as to be consistent with the next statement. Either "joins" or "separates" is fine. By the way, the ordinary meaning of "articulation" means "the action or manner of jointing or interrelating"). An articulation point of $G$ belongs to each biconnected components that is directly connected to it. (Also note that a vertex of a biconnected component that is an articulation point of $G$ is not an articulation point of that biconnected component as a graph.) It does not make sense to remove any articulation point of $G$ if we want to list the vertices of each biconnected component of $G$.

We can see that "removing articulation points" is never involved when we try to find biconnected components. Articulation points serve as the shared boundary between different biconnected components, as illustrated in the following diagram from Wikipedia, where "cut vertices" are the same as "articulations points".

enter image description here


For the graph at the bottom of the question, vertex $x$ is the only articulation point. There are two biconnected components, which share vertex $x$.

  • the biconnected component at the top that contains the top 2 vertices.
  • the biconnected component at the bottom that contains all vertices except the topmost vertex.
$\endgroup$
8
  • $\begingroup$ Hi! Thank you for your answer! It has enlightened me on the first problem and is quite elegant! However, I am still having trouble with the second problem. If I were to remove all articulation points of the second graph of my question at once, I would just have to remove x. Of the remaining graph (i.e. the one without x) y would be an articulation point and so I still don't know how to construct a simple cycle through e and f then. So to me, removing all articulation points of the original graph at once does not seem to suffice. Could you maybe explain this a little bit more in depth? $\endgroup$
    – sorry
    Jul 17, 2022 at 9:18
  • $\begingroup$ Please check the analysis of the second problem I just added. $\endgroup$
    – John L.
    Jul 20, 2022 at 18:54
  • $\begingroup$ Hi, thanks for the additional explanation. This was very helpful and enriched my understanding. Unfortunately, there are still some issues which rather confuse me and are potentially not correct. 1. At the bottom of your answer you claim that y is an articulation point. However, the removal of y would not disconnect the graph as I see it. Furthermore, as I see it, there are only two biconneted components, namely the one "x and the top vertex" and "x and all other vertices except for the top vertex". $\endgroup$
    – sorry
    Jul 21, 2022 at 15:56
  • $\begingroup$ Additional issues are: The claim "an edge is a bridge iff either both of its endpoints are articulation points or one of its endpoints is an articulation point and the other is of degree one" does not hold. Consider for example the following graph in which the red vertices are articulation points but the green edge is not a bridge: (I dont know how to add the picture here, so I wrote it into a PS-section of my original question) $\endgroup$
    – sorry
    Jul 21, 2022 at 16:00
  • 1
    $\begingroup$ Here is the lesson for me, again. Textbooks (that has been published for years) are the most reliable. Wikipedia is pretty good in general. Articles on the internet that are not peer-reviewed should be treated with suspicion. $\endgroup$
    – John L.
    Jul 21, 2022 at 19:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.