1
$\begingroup$

We know that if in a graph $G$, $e$ < $(n -1)$, then the graph is disconnected, where $e$ and $n$ are number of edges and number of vertices resp. Is there any other criteria to find out the disconnected graphs. Thanks for your help.

$\endgroup$
  • 2
    $\begingroup$ There's a nice formula that is often useful: $V-E=b_0-b_1$ where $V,E$ are the number of vertices and edges, $b_0$ is the number of connected components and $b_1$ is the "number of loops," which can be defined as the number of edges in the complement of a spanning forest. $\endgroup$ – Cheerful Parsnip May 6 '13 at 12:58
  • $\begingroup$ Sir, Is there any specific name of this formula? It means if we are taking simple graphs, then $b_1$ is zero. And if $V$ - $E$ = $b_0$ is greater than 1, we will get disconnected graphs. Am i right sir? $\endgroup$ – monalisa May 6 '13 at 13:25
  • $\begingroup$ One quick and dirty algorithm, for a graph with n vertices, sum the first n powers of the adjacency matrix. If there are no zeros in the sum, it's connected. This is slower that the standard algorithms, but it's a one-liner program. $\endgroup$ – Ed Pegg May 6 '13 at 15:08
  • $\begingroup$ @monalisa: this is called the Euler characteristic. The loops I am referring to are not the same as what you are thinking, though. For me a loop is a "hole" in the graph, and as I mentioned in my comment, this can be rigorously defined as the number of edges in the complement of a spanning forest. $\endgroup$ – Cheerful Parsnip May 6 '13 at 18:13
1
$\begingroup$

You can do BFS or DFS search on the given graph, say G. If the output is a tree with less than n vertices, then G is not connected. Actually, G is connected if and only if the output tree has n vertices.

$\endgroup$

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.