[Solved] Consider the graph shown below. Which of the following are the edges in the MST of the given graph?

Computer Science Engineering (CSE)
Design and Analysis of Algorithms
Consider the graph shown below. Which of...

Q.	Consider the graph shown below. Which of the following are the edges in the MST of the given graph?
A.	(a-c)(c-d)(d-b)(d-b)
B.	(c-a)(a-d)(d-b)(d-e)
C.	(a-d)(d-c)(d-b)(d-e)
D.	(c-a)(a-d)(d-c)(d-b)(d-e)
Answer» C. (a-d)(d-c)(d-b)(d-e)
Explanation: the minimum spanning tree of the given graph is shown below. it has cost 56.

View all MCQs in: Design and Analysis of Algorithms

Discussion

Related Questions

Consider the graph M with 3 vertices. Its adjacency matrix is shown below. Which of the following is true?
A k-regular bipartite graph is the one in which degree of each vertices is k for all the vertices in the graph. Given that the bipartitions of this graph are U and V respectively. What is the relation between them?
Consider a undirected graph G with vertices { A, B, C, D, E}. In graph G, every edge has distinct weight. Edge CD is edge with minimum weight and edge AB is edge with maximum weight. Then, which of the following is false?
A graph has 20 vertices. The maximum number of edges it can have is? (Given it is bipartite)
Consider a complete graph G with 4 vertices. The graph G has spanning trees.
Which of the following edges form minimum spanning tree on the graph using kruskals algorithm?
A complete bipartite graph is a one in which each vertex in set X has an edge with set Y. Let n be the total number of vertices. For maximum number of edges, the total number of vertices hat should be present on set X is?
How many edges does a n vertex triangle free graph contains?
From the given graph, how many vertices can be matched using maximum matching in bipartite graph algorithm?
Consider the following graph. Using Kruskal’s algorithm, which edge will be selected first?