Home » MCQs » Discrete Mathematics MCQs

Discrete Mathematics | Minimum Spanning Tree MCQs

Discrete Mathematics | Minimum Spanning Tree MCQs: This section contains multiple-choice questions and answers on Minimum Spanning Tree in Discrete Mathematics.
Submitted by Anushree Goswami, on October 23, 2022

1. If T is a tree and includes all the vertices of G, then T is a ____ tree of G?

1. Spanning
2. Minimum Spanning
3. Maximum Spanning
4. Average Spanning

Answer: A) Spanning

Explanation:

If T is a tree and includes all the vertices of G, then T is a spanning tree of G.

---

2. In a weighted graph G, each edge is assigned a nonnegative number called the ____ and all spanning trees T of G are assigned a total weight by adding the ____?

1. Edge Height
2. Edge Weight
3. Edge Length
4. Edge Width

Answer: B) Edge Weight

Explanation:

In a weighted graph G, each edge is assigned a nonnegative number called the edge weight, and all spanning trees T of G are assigned a total weight by adding the edge weights.

---

3. In G, the minimum spanning tree is the tree with the ____ total weight?

1. Largest
2. Medium
3. Smallest
4. Average

Answer: C) Smallest

Explanation:

In G, the minimum spanning tree is the tree with the smallest total weight.

---

4. A connected weighted graph G is analyzed using ____ algorithm to find the minimum spanning tree T?

1. Kuskal
2. Kruskal
3. Krush
4. Kaiskhal

Answer: B) Kruskal

Explanation:

A connected weighted graph G is analyzed using Kruskal's algorithm to find the minimum spanning tree T.

---

5. Here are the steps performed in Kruskal's algorithm to find the minimum spanning tree?

1. We want to find the minimum spanning tree T of a connected weighted graph G with n vertices.
2. In T, add the edges of each graph G that does not form a cycle until n-1 edges are added.
3. The edges of the graph G should be ordered in increasing weight order.
4. Include an edge in T when it is initialized with all vertices.

What is the correct order -

1. i > ii > iii > iv
2. i > iii > ii > iv
3. i > iv > iii > ii
4. i > iii > iv > ii

Answer: D) i > iii > iv > ii

Explanation:

The correct order of steps performed in Kruskal's algorithm to find the minimum spanning tree is -

1. We want to find the minimum spanning tree T of a connected weighted graph G with n vertices.
2. The edges of the graph G should be ordered in increasing weight order.
3. Include an edge in T when it is initialized with all vertices.
4. In T, add the edges of each graph G that does not form a cycle until n-1 edges are added.

---

---