PARIXO GATE · ME Open the app

GATE 2014 ME Set 3 · Question 31

1 markMultiple choiceIndustrial EngineeringTransportation, Assignment and Network Flow

A minimal spanning tree in network flow models involves

  1. A

    all the nodes with cycle/loop allowed

  2. B

    all the nodes with cycle/loop not allowed

  3. C

    shortest path between start and end nodes

  4. D

    all the nodes with directed arcs

GATE 2014 · Mechanical Engineering · Set 3 · IIT Kharagpur · printed as Q.21 in the ME section

Answer
(B)

From the official answer key published by IIT Kharagpur.

Worked solution

A tree is defined as an undirected, connected graph with no cycles or loops. A spanning tree of a connected graph is a subgraph that includes all the vertices (nodes) of the original graph while maintaining the tree property (i.e., no cycles/loops and connected with edges for nodes).

A minimal spanning tree (MST) is a spanning tree whose sum of edge weights is minimized. Therefore, an MST must span all the nodes with cycles/loops strictly not allowed, which corresponds to option (B).

  • Option (A) is incorrect because loops or cycles violate the definition of a tree.
  • Option (C) refers to the shortest path problem, not a spanning tree.
  • Option (D) describes directed network models, whereas a standard spanning tree connects nodes without cycles regardless of direction.

Answer: (B)

Practise Transportation, Assignment and Network Flow

8 GATE questions from this chapter, in short untimed sets, with the formula sheet beside them. Free.

More from Transportation, Assignment and Network Flow

Question from the official GATE 2014 ME paper (Set 3), IIT Kharagpur. Solutions by PARIXO AI. All 65 questions of this paper.