Question

In the transportation network given below, P, Q, R, S, T, and U are the nodes and values mentioned on the links denote time in minutes. Which of the following options represent the minimum spanning tree? 

• A. PQ, QR, QT, TS, SU
• B. PR, QR, RT, TU, SU
• C. PQ, QR, RT, TS, SU
• D. PQ, QR, RS, ST, TU

Hint:

When finding a minimum spanning tree, use Kruskal's or Prim's algorithm to select edges in increasing order of weight while ensuring no cycles are formed. This ensures the smallest possible sum of edge weights.

Answer 1

The Correct Option is A, C

To solve this problem, we need to find the minimum spanning tree (MST) of a connected graph. A minimum spanning tree connects all the nodes in the graph with the minimum possible sum of edge weights, ensuring there are no cycles. The graph in question represents a transportation network with nodes P, Q, R, S, T, and U, and the weights of the edges represent the time taken to travel between the nodes.

Here's the step-by-step approach to solving this:

Step 1: List the edges and their weights
The edges in the given transportation network with their corresponding weights are:
- PQ: 2
- QR: 3
- QT: 3
- TS: 4
- SU: 2
- RT: 6
- RS: 3
- ST: 6
- TU: 3

Step 2: Use Kruskal's or Prim's algorithm
To find the MST, we can apply Kruskal's algorithm or Prim's algorithm. For simplicity, let's apply Kruskal's algorithm, which sorts all edges in increasing order and adds them one by one, ensuring no cycles are formed.

Step 3: Sort the edges by weight
The sorted edges are:
- PQ: 2
- SU: 2
- QR: 3
- QT: 3
- RS: 3
- TU: 3
- TS: 4
- RT: 6
- ST: 6

Step 4: Select edges for the MST
We start with the smallest edge and keep adding edges to the MST as long as they don't form a cycle:
- Add PQ (weight 2)
- Add SU (weight 2)
- Add QR (weight 3)
- Add QT (weight 3)
- Add RS (weight 3)

At this point, all nodes are connected, and we stop adding edges. We have the edges: PQ, SU, QR, QT, and RS. This is one possible MST.

Step 5: Check other options
Let's check the other options to see if they also represent MSTs:
- Option (B): PR, QR, RT, TU, SU. This forms an MST since it connects all nodes without forming a cycle, with a total weight of 2 + 3 + 6 + 3 + 2 = 16.
- Option (D): PQ, QR, RS, ST, TU. This also forms an MST with a total weight of 2 + 3 + 3 + 6 + 3 = 17.
Both (A), (B), and (D) form valid minimum spanning trees.
Final Answer: (A), (B), (D)