Finding strongly connected components in a graph

Nick · 2013-10-30T14:16:38

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.

Math and Physics Programming

Started by Nicholas Kong October 30, 2013 01:09 AM

19 comments, last by Paradigm Shifter 11 years, 3 months ago

Paradigm Shifter

5,832

October 30, 2013 02:16 PM

I dunno, it was a conjecture, I'd never heard of strongly connected components either! Sounds right to me though. I'm fairly certain the OPs book will go on to prove that in due course.

I think strongly connected is an equivalence relation and those partition a set into disjoint subsets anyway.

EDIT: Proof here http://www.ics.uci.edu/~eppstein/161/960220.html

"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley