Which of the following is false?

M

Mr. Dubey

🎓 Coach ⭐ 104.60K Points

📊 Design and Analysis of Algorithms

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

💬 Discuss

✅ Correct 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.

Explanation by: Mr. Dubey

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.

💬 Discussion

📊 Question Analytics

👁️

607

Total Visits

📽️

3 y ago

Published

🎖️

Mr. Dubey

Publisher

📈

90%

Success Rate