Q. Consider the graph M with 3 vertices. Its adjacency matrix is shown below. Which of the following is true?

  • (A) graph m has no minimum spanning tree
  • (B) graph m has a unique minimum spanning trees of cost 2
  • (C) graph m has 3 distinct minimum spanning trees, each of cost 2
  • (D) graph m has 3 spanning trees of different costs
💬 Discuss
✅ Correct Answer: (C) graph m has 3 distinct minimum spanning trees, each of cost 2
Explanation: here all non-diagonal elements in the adjacency matrix are 1. so, every vertex is connected every other vertex of the graph. and, so graph m has 3 distinct minimum spanning trees.

Published by Mr. Dubey ⭐ 111.42K Points at 16-Sep-2023 03:43 pm in Design and Analysis of Algorithms

Explanation by: Mr. Dubey
here all non-diagonal elements in the adjacency matrix are 1. so, every vertex is connected every other vertex of the graph. and, so graph m has 3 distinct minimum spanning trees.

💬 Discussion

Related MCQs

Q. DD path graph is called as

Q. Which model is equally suitable to shared-address- space or message- passing paradigms, since the interaction is naturally two ways.

Q. Which requires bit transitions?

Q. An Alphabet Consist Of The Letters A, B, C And D. The probability of occurrence is p(a) = 0.4, p(b) = 0.1, p(c) = 0.2 and p(d) = 0.3. The huffman code

Q. What is the output of the expression : 3*1**3

Q. Which of these benefits can be achieved when software is restructured?

Q. Bellmann Ford algorithm was first proposed by

Q. The main purpose of having memory hierarchy is to

Q. Earliest deadline first algorithm assigns priorities according to ____________

Q. The best mode of connection between devices which need to send or receive large amounts of data over a short distance is

📊 Question Analytics

👁️
746
Total Visits
📽️
3 y ago
Published
🎖️
Mr. Dubey
Publisher
📈
93%
Success Rate