Difference between connected vs strongly connected vs complete graphs - MathOverflow [closed] most recent 30 from http://mathoverflow.net 2013-05-21T15:34:50Z http://mathoverflow.net/feeds/question/6833 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/6833/difference-between-connected-vs-strongly-connected-vs-complete-graphs Difference between connected vs strongly connected vs complete graphs Goody Two Shoes 2009-11-25T19:45:12Z 2013-04-17T00:45:40Z <p>What is the difference between</p> <p>connected</p> <p>strongly-connected and</p> <p>complete?</p> <p>My understanding is:</p> <p><strong>connected</strong>: you can get to every vertex from every other vertex.</p> <p><strong>strongly connected</strong>: every vertex has an edge connecting it to every other vertex.</p> <p><strong>complete</strong>: same as strongly connected.</p> <p>Is this correct?</p> http://mathoverflow.net/questions/6833/difference-between-connected-vs-strongly-connected-vs-complete-graphs/6837#6837 Answer by Alexandru Moșoi for Difference between connected vs strongly connected vs complete graphs Alexandru Moșoi 2009-11-25T20:11:12Z 2009-11-25T20:11:12Z <ul> <li><em>Connected</em> is usually associated with undirected graphs (two way edges): there is a <strong>path</strong> between every two nodes.</li> <li><em>Strongly connected</em> is usually associated with directed graphs (one way edges): there is a <strong>route</strong> between every two nodes.</li> <li><em>Complete graphs</em> are undirected graphs where there is an <strong>edge</strong> between every pair of nodes.</li> </ul> http://mathoverflow.net/questions/6833/difference-between-connected-vs-strongly-connected-vs-complete-graphs/6839#6839 Answer by Eric Xu for Difference between connected vs strongly connected vs complete graphs Eric Xu 2009-11-25T20:24:19Z 2009-11-25T20:24:19Z <p>I agree with Alex. Note that Strongly connected means "there is a route/path" instead of "there is an edge" between every two nodes. </p> http://mathoverflow.net/questions/6833/difference-between-connected-vs-strongly-connected-vs-complete-graphs/8470#8470 Answer by Hank Turowski for Difference between connected vs strongly connected vs complete graphs Hank Turowski 2009-12-10T18:39:42Z 2009-12-10T18:39:42Z <p>It is also important to remember the distinction between strongly connected and unilaterally connected. A directed graph is unilaterally connected if for any two vertices a and b, there is a directed path from a to b or from b to a but not necessarily both (although there could be). Strongly connected implies that both directed paths exist. This means that strongly connected graphs are a subset of unilaterally connected graphs.</p> <p>And a directed graph is weakly connected if it's underlying graph is connected.</p> http://mathoverflow.net/questions/6833/difference-between-connected-vs-strongly-connected-vs-complete-graphs/79905#79905 Answer by Ricky for Difference between connected vs strongly connected vs complete graphs Ricky 2011-11-03T08:21:24Z 2011-11-03T08:21:24Z <p>Alex, can you explain a bit more on the difference between a Connected Graph and a Complete Graph?</p> <p>It seems the only difference is that one uses path and the other uses edge. Aren't they the same? When you said for a Complete Graph, it's when: </p> <p>"are undirected graphs where there is an edge between every pair of nodes". </p> <p>Well, since it's an undirected graph then you can traverse both ways, hence why it's an "edge". But doesn't that mean the same as 'path'? I.e, there's a path between every two nodes that you can traverse between? So isn't that just the same as the definition of a Connected Graph then?</p>