Jump to content
  • Advertisement
Sign in to follow this  
Nicholas Kong

Finding strongly connected components in a graph

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

stronglyConnected_zps8c6a6999.png

 

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 this post


Link to post
Share on other sites
Advertisement

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.

Edited by Paradigm Shifter

Share this post


Link to post
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 this post


Link to post
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).

Edited by Paradigm Shifter

Share this post


Link to post
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 this post


Link to post
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 this post


Link to post
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.

 

They are basically talking about dead ends and one way streets.

 

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!

Edited by Paradigm Shifter

Share this post


Link to post
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.

 

They are basically talking about dead ends and one way streets.

 

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 this post


Link to post
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 ;)

Edited by Paradigm Shifter

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!