52 846
Assignments Done
97,9%
Successfully Done
In October 2017
Your physics homework can be a real challenge, and the due date can be really close — feel free to use our assistance and get the desired result.
Be sure that math assignments completed by our experts will be error-free and done according to your instructions specified in the submitted order form.
Our experts will gladly share their knowledge and help you with programming homework. Keep up with the world’s newest programming trends.

Answer on Discrete Mathematics Question for Sujata Roy

Question #15602
Formula to determine the number of connected components of a graph G.
Expert's answer
There isn't common formula to determine the number of connected components of an arbitrary graph. You can find the number of connected components algorithmically.

Need a fast expert's response?

Submit order

and get a quick answer at the best price

for any assignment or question with DETAILED EXPLANATIONS!

Comments

Assignment Expert
10.10.2012 09:18

It is straightforward to compute the connected components of a graph in linear time (in terms of the numbers of the vertices and edges of the graph) using either breadth-first search or depth-first search. In either case, a search that begins at some particular vertex v will find the entire connected component containing v (and no more) before returning. To find all the connected components of a graph, loop through its vertices, starting a new breadth first or depth first search whenever the loop reaches a vertex that has not already been included in a previously found connected component.

There are also efficient algorithms to dynamically track the connected components of a graph as vertices and edges are added, as a straightforward application of disjoint-set data structures. These algorithms require amortized O(α(n)) time per operation, where adding vertices and edges and determining the connected component in which a vertex falls are both operations, and α(n) is a very slow-growing inverse of the very quickly growing Ackermann function. A related problem is tracking connected components as all edges are deleted from a graph, one by one; an algorithm exists to solve this with constant time per query, and O(|V||E|) time to maintain the data structure; this is an amortized cost of O(|V|) per edge deletion. For forests, the cost can be reduced to O(q + |V|log|V|), or O(log|V|) amortized cost per edge deletion.




Sujata Roy
07.10.2012 03:37

Then sir please tell me about the algorithm.

Leave a comment

Ask Your question