2
$\begingroup$

I'm reading CLRS and it mentions that any graph and its transpose graph both have the same strongly connected components. However, I don't seem to understand how to formally prove this claim. How would you recommend to approach this problem?

$\endgroup$

2 Answers 2

2
$\begingroup$

We can look at strongly connected component as a group of vertexes. We are gonna look at one scc and prove that it's the same in the transpose. Let's name vertexes that are in this scc as vertexes $A$, and those that aren't there as vertexes $B$.

From definition of scc:

1) From every vertex $A$ you can get to every other vertex $A$

2a) For every vertex $B$ there either exists vertex $A$ from which you can't get to this vertex $B$

Or

2b) There exists a vertex $A$ to which you can't get from this vertex $B$ (if both 2a and 2b were not true vertex B would be a part of this scc)

Let's look closer at 2a

If there exists vertex $A$ from which we can't get to this vertex $B$, we can't get from ANY vertex $A$ to this vertex $B$. This is a simple conclusion from 1).

The same goes for 2b

If there exists a vertex $A$ to which you can't get from this vertex $B$, we can't get to ANY vertex $A$ from this vertex $B$. That's a conclusion from 1) as well.

To prove that scc is the same in the transpose we need to show that in the transpose

a) every vertex $A$ will still be in this scc which means that WE WILL BE ABLE TO GET FROM EVERY VERTEX $A$ TO ANY OTHER VERTEX $A$.

b) every vertex $B$ will still NOT be a part of this scc

Proof of a)

Let's take a pair of vertexes - $A_1$ and $A_2$. From 1) we are able to get from $A_1$ to $A_2$ using some way (let's name it way 1) and from $A_2$ to $A_1$ (let's name it way 2) In the transpose when we change every direction way 1 becomes way 2 and way 2 becomes way 1, so we're still able to get from $A_1$ to $A_2$ and from $A_2$ to $A_1$. That's truth for every pair of vertexes $A$, so a) is proved.

Proof of b)

  • if a vertex $B$ isn't connected with any vertex $A$ (in any direction) than it's simple because in the transpose it still won't be connected with any vertex $A$, so it won't be part of this scc.

  • if a vertex $B$ is connected with a vertex $A$ in a direction $B\to A$ than it can't be connected with any vertex $A$ in direction $ A\to B$, because then vertex $B$ would be a part of this scc. So in the transpose when we change directions vertex $B$ will be connected with a vertex $A$ in direction $A \to B$, but it won't be connected with any vertex $A$ in a direction $ B \to A$, so from 2b it won't be a part of this scc

  • (here the situation is similar to a previous one) if a vertex $B$ is connected with a vertex $A$ in a direction $A\to B$ than it can't be connected with any vertex $A$ in direction $B \to A$, because then vertex $B$ would be a part of this scc. So in the transpose when we change directions vertex $B$ will be connected with a vertex $A$ in direction $B \to A$, but it won't be connected with any vertex $A$ in a direction $A \to B$, so from 2a it won't be a part of this scc.

So in every case $B$ still won't be a part of scc in the transpose, so b) is proved.

We proved a) and b) so this scc is the same in the transpose. That is truth for every scc, so the whole proof is completed.

// if this helped you please vote up, I'm new in math stack exchange

$\endgroup$
0
$\begingroup$

Let $D$ be the digraph and $D'$ its transpose digraph.

If $D$ is strongly connected, by definition, we have that for each ordered pair of vertices $(x,y)$ there is a path from $x$ to $y$. Now, $D'$ has an edge $(y,x)$ iff $(x,y)$ is an edge in $D$. So, our path from $x$ to $y$ corresponds to a path from $y$ to $x$ in $D'$ since we just reverse the edges. Vertices $x$ and $y$ were arbitrary thus $D'$ is strongly connected.

Now for the converse, note that the transpose of the transpose equals the digraph itself: $(D')' = D$.

$\endgroup$
2
  • $\begingroup$ Thank you. This part of the proof is straightforward, however I'm having trouble proofing that the any other vertex initially not in the strongly connected component stays so in the transposed graph. $\endgroup$
    – Oringa
    Nov 18, 2017 at 13:22
  • $\begingroup$ you are not adding any more edges to the transpose, just reversing them! $\endgroup$
    – mandella
    Nov 18, 2017 at 13:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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