GATE 2014 ME Set 3 · Question 31
A minimal spanning tree in network flow models involves
- A
all the nodes with cycle/loop allowed
- B
all the nodes with cycle/loop not allowed
- C
shortest path between start and end nodes
- D
all the nodes with directed arcs
GATE 2014 · Mechanical Engineering · Set 3 · IIT Kharagpur · printed as Q.21 in the ME section
Answer
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
- GATE 2014 ME Set 4 · Q28The total number of decision variables in the objective function of an assignment problem of size n × n (n…
- GATE 2024 ME · Q65In a supplier-retailer supply chain, the demand of each retailer, the capacity of each supplier, and the…
- GATE 2022 ME Set 1 · Q58An assignment problem is solved to minimize the total processing time of four jobs (1, 2, 3 and 4) on four…
- GATE 2019 ME Set 1 · Q64Five jobs (J1, J2, J3, J4 and J5) need to be processed in a factory. Each job can be assigned to any of the…
- GATE 2018 ME Set 2 · Q61The arc lengths of a directed graph of a project are as shown in the figure. The shortest path length from…
- GATE 2017 ME Set 2 · Q48A product made in two factories, P and Q, is transported to two destinations, R and S. The per unit costs of…
Question from the official GATE 2014 ME paper (Set 3), IIT Kharagpur. Solutions by PARIXO AI. All 65 questions of this paper.