[Solved] Which of the following is false?

McqMate

Q.	Which of the following is false?
A.	the spanning trees do not have any cycles
B.	mst have n – 1 edges if the graph has n edges
C.	edge e belonging to a cut of the graph if has the weight smaller than any other edge in the same cut, then the edge e is present in all the msts of the graph
D.	removing one edge from the spanning tree will not make the graph disconnected
Answer» D. removing one edge from the spanning tree will not make the graph disconnected
Explanation: every spanning tree has n – 1 edges if the graph has n edges and has no cycles. the mst follows the cut property, edge e belonging to a cut of the graph if has the weight smaller than any other edge in the same cut, then the edge e is present in all the msts of the graph.

1.1k

0

Do you find this helpful?

3

View all MCQs in

Design and Analysis of Algorithms

Discussion

No comments yet

Related MCQs

Which of the following is false in the case of a spanning tree of a graph G?
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?
Which of the following is false about the Kruskal’s algorithm?
Which of the following is false about Prim’s algorithm?
Suppose you have coins of denominations 1,3 and 4. You use a greedy algorithm, in which you choose the largest denomination coin which is not greater than the remaining sum. For which of the following sums, will the algorithm produce an optimal answer?
Which of the following strategies does the following diagram depict?
Which of the following strategies does the following diagram depict?
You are given n dice each having f faces. You have to find the number of ways in which a sum of S can be achieved. This is the dice throw problem. Which of the following methods can be used to solve the dice throw problem?
Recursion is similar to which of the following?
Which of the following problems can’t be solved using recursion?