COMPUTER SCIENCE AND ENGINEERING
ALGORITHMS
|
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
|
|
By the sum of costs of the edges of the tree
|
|
|
By the sum of the costs of the edges and vertices of the tree
|
|
|
By the sum of the costs of the vertices of the tree
|
|
|
By the sum of costs of the edges of the graph
|
Detailed explanation-1: -Sum of all of the edges in the spanning tree is the cost of the spanning tree. There can be many minimum spanning trees for a given graph. 3. Consider a complete graph G with 4 vertices.
Detailed explanation-2: -The cost of the spanning tree is the sum of the weights of all the edges in the tree.
Detailed explanation-3: -This can be generalized as weight = V2 – V + 1 where V is the total nodes in the graph.
Detailed explanation-4: -Step 1: Determine the arbitrary starting vertex. Step 2: Keep repeating steps 3 and 4 until the fringe vertices (vertices not included in MST)remain. Step 3: Select an edge connecting the tree vertex and fringe vertex having the minimum weight. Step 4: Add the chosen edge to MST if it doesn’t form any closed cycle.
Detailed explanation-5: -Theorem on characterization of an all-MST edge: An edge appears in every minimum spanning tree if and only if for any cycle that contains that edge, that cycle also contains an edge heavier than that edge.