# Finding strongly connected components in a graph

This topic is 2092 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

The answers listed strongly connected components in this graph. But the textbook said a strongly connected component is a strongly connected subgraph of the directed graph but not contained in larger strongly connected subgraphs.

I do not see how the subgraph of this graph is strongly connected because the textbook said strongly connected means there is a path from vertices a to b. But there is no such thing because the directed edges clearly shows that.

Edited by warnexus

##### Share on other sites

Strongly connected means if you can go from A->B you can also go from B->A? (EDIT: That doesn't mean you can go from A to B and vice versa in one hop. one way systems would suck then ;) )

The graphs don't have to be connected in that case. You can have 2 or more subgraphs which aren't connected. Disjointed graphs are fine.

EDIT2: I think it means you get rid of dead ends.

##### Share on other sites

Strongly connected means if you can go from A->B you can also go from B->A? (EDIT: That doesn't mean you can go from A to B and vice versa in one hop. one way systems would suck then ;) )

The graphs don't have to be connected in that case. You can have 2 or more subgraphs which aren't connected. Disjointed graphs are fine.

I'm a bit confused when the textbook says A to B are they saying A is the initial vertex and B is the terminal vertex? Or is A, a vertex labeled A and B, a vertex labeled B?

Edited by warnexus

##### Share on other sites

It means any 2 vertices (could even be the same vertex, unless implicitly stated this is disallowed). Don't be confused by "if you can get from A to B" thinking the meaning is "you can get from vertex "a" to vertex "b"".

Maths books hardly ever have numbers in them, they generalise.

In that graph you can go from a to b and vice versa though ;) - just follow the arrows between them.

EDIT: In the graph you posted, vertex "e" is a dead end so isn't strongly connected to the others, if I am correct in my guess at what strongly connected means. I'm not sure whether the strongly connected components are

{e} and G\{e}

or

{e} and G

(where G is the entire graph).

##### Share on other sites

It means any 2 vertices (could even be the same vertex, unless implicitly stated this is disallowed). Don't be confused by "if you can get from A to B" thinking the meaning is "you can get from vertex "a" to vertex "b"".

Maths books hardly ever have numbers in them, they generalise.

In that graph you can go from a to b and vice versa though ;) - just follow the arrows between them.

Yeah, it does go from vertex "a" to vertex "b" and vice-versa. which means it is strongly connected which would mean it is a strongly connected component. But the textbook did not list that as an answer.

##### Share on other sites

Ok well see my edit, the answer is either

{e} and G\{e}

or

{e} and G,

depending on the definition, which I'm too lazy too google (6th beer).

##### Share on other sites

Ok well see my edit, the answer is either

{e} and G\{e}

or

{e} and G,

depending on the definition, which I'm too lazy too google (6th beer).

the strongly connected components are {a, b, f }, {c, d, e}.

I am using Rosens' textbook.

##### Share on other sites

Mhmm ok, I can see now that once you go to vertex "c" you can never get back to {a, b, f}.

That's what it means then, in effect. Strongly connected means you can get from place to place but if you leave your neighbourhood and can never get back that is a new subgraph.

EDIT: I'm interested why {e} doesn't count on its own though? Once you get to {e} you are stuck...

EDIT2: I see you can get back to {c} from {e}. Ignore this drunkard ;) I guess we've both learned something today!

##### Share on other sites

Mhmm ok, I can see now that once you go to vertex "c" you can never get back to {a, b, f}.

That's what it means then, in effect. Strongly connected means you can get from place to place but if you leave your neighbourhood and can never get back that is a new subgraph.

EDIT: I'm interested why {e} doesn't count on its own though? Once you get to {e} you are stuck...

EDIT2: I see you can get back to {c} from {e}. Ignore this drunkard ;)

I am not sure what they mean by {a,b,f}

because once you go from vertex labeled a to vertex labeled b, after vertex b you cannot go to vertex f based off the graph.

##### Share on other sites

Sure you can, you go b->a->f. Like I said, you don't have to do it in one hop.

EDIT: Mind blowing time! You don't even need to do it in a finite number of hops, probably ;)

• 13
• 18
• 29
• 11