Minimum Spanning Trees MCQs For Gate Exam

Minimum Spanning Trees

1. In a connected undirected weighted graph, an MST is:
   A) Unique for any edge weights B) Always unique if all edge weights distinct C) Never unique D) Unique only for complete graphs
   Answer: B
   Explanation: Distinct weights prevent ties at cut steps, so MST is unique.
2. Kruskal’s algorithm sorts edges then adds smallest non-cycle edge. Its time complexity using union-find and sorting m edges is:
   A) O(m log n) B) O(m log m + α(n)m) ≈ O(m log m) C) O(n²) D) O(mn)
   Answer: B
   Explanation: Sorting dominates O(m log m); union-find contributions nearly linear.
3. Prim’s algorithm with binary heap on graph with n vertices and m edges runs in:
   A) O(n²) B) O(m log n) C) O(m + n) D) O(m log m)
   Answer: B
   Explanation: Each decrease-key/extract-min is O(log n), total O(m log n).
4. The cut property: any lightest edge crossing a cut belongs to some MST. This property is:
   A) True (cut property) B) False C) Only for directed graphs D) True only if weights positive
   Answer: A
   Explanation: Fundamental MST correctness property.
5. The cycle property: in any cycle, the heaviest edge cannot be in an MST (if unique heaviest). True or False?
   A) True B) False C) Only for complete graphs D) Only for equal weights
   Answer: A
   Explanation: Removing heaviest in cycle reduces cost — so it’s not in MST.
6. Reverse-delete algorithm sorts edges descending and deletes if still connected. It yields:
   A) An MST B) A maximum spanning tree C) A shortest path tree D) Incorrect result
   Answer: A
   Explanation: Reverse-delete uses cycle property to maintain MST.
7. For MST, if you increase the weight of a non-MST edge, the MST:
   A) Stays same or unaffected B) Always changes C) Becomes invalid D) Gains edge
   Answer: A
   Explanation: Non-MST edge not used; raising it can’t produce better alternative.
8. For MST, if you decrease weight of an MST edge, the existing MST:
   A) Remains MST (still optimal) B) Must change C) Becomes non-spanning D) Causes cycles
   Answer: A
   Explanation: Decreasing an included edge only helps objective; MST remains valid.
9. The MST of a disconnected graph is properly called:
   A) Minimum Spanning Forest B) No MST exists C) Minimum path tree D) Minimum cut
   Answer: A
   Explanation: Each connected component gets its MST → forest.
10. For graph with equal edge weights, number of distinct MSTs can be:
    A) More than 1 B) Exactly 1 always C) Zero D) At most 2
    Answer: A
    Explanation: Ties allow multiple MSTs.
11. Kruskal chooses edges in increasing order; ties can be broken arbitrarily. Will it still produce an MST?
    A) Yes B) No C) Only if prim used too D) Only for trees
    Answer: A
    Explanation: Any tie-breaking still yields an MST (cut property handles equal weights).
12. Prim’s algorithm with adjacency matrix (dense graph) runs in:
    A) O(n²) B) O(m log n) C) O(n log n) D) O(m²)
    Answer: A
    Explanation: Dense graphs: Prim with array best is O(n²).
13. The bottleneck edge of a spanning tree is:
    A) The maximum-weight edge on the tree B) The minimum-weight edge overall C) The sum of weights D) The average weight
    Answer: A
    Explanation: Bottleneck = largest edge weight in tree; MST minimizes this.
14. Every MST is a minimum bottleneck spanning tree (MBST). True or False?
    A) True B) False C) Only for distinct weights D) Only for trees
    Answer: A
    Explanation: MST minimizes maximum edge, hence MBST.
15. Is every MBST an MST?
    A) Not always — MBST may not minimize total weight B) Yes always C) Only for unique weights D) Only in trees
    Answer: A
    Explanation: MBST minimizes max edge but may have larger sum.
16. Second-best MST (next minimal total weight) can be found by:
    A) Considering replacing one edge on MST with non-MST edge and recomputing best swap B) Running Prim twice C) Sorting vertices D) Not possible
    Answer: A
    Explanation: For each non-tree edge, consider max edge in path between its endpoints; compute minimal increase.
17. In Kruskal, union-find operations use union by rank and path compression giving amortized:
    A) α(n) per op (inverse Ackermann) B) O(log n) per op C) O(1) exact D) O(n)
    Answer: A
    Explanation: Amortized nearly constant α(n).
18. For a complete graph with n vertices and random unique weights, expected MST total edges =
    A) n−1 B) n C) n/2 D) 2n
    Answer: A
    Explanation: Any spanning tree has n−1 edges.
19. Borůvka’s algorithm repeatedly picks cheapest outgoing edge per component; it runs in:
    A) O(m log n) or O(mα(n)) with improvements B) O(n²) strictly C) O(2^n) D) O(mn)
    Answer: A
    Explanation: Borůvka reduces components fast; combined with union-find efficient.
20. A graph with n vertices and m edges, the MST has how many edges?
    A) n−1 if connected B) m−n C) n D) m
    Answer: A
    Explanation: Spanning tree edges = vertices − 1.
21. In Kruskal, an edge that connects two vertices in same union-find set is:
    A) Discarded (would form cycle) B) Chosen C) Delayed D) Marked as heavy
    Answer: A
    Explanation: Adding it would create cycle so skip.
22. A light edge crossing a cut must belong to all MSTs?
    A) If it is uniquely light — yes B) Never C) Only for directed graphs D) Only in dense graphs
    Answer: A
    Explanation: Unique lightest across cut is forced into every MST.
23. Prim’s algorithm grows tree from a start vertex; is choice of start vertex important for final MST weight?
    A) No — any start yields same MST total weight (maybe different tree) B) Yes always C) Only for unique weights D) Only for complete graphs
    Answer: A
    Explanation: Different trees but equal total weight.
24. In graphs with negative weights, MST algorithms like Kruskal/Prim:
    A) Still valid (weights can be negative) B) Fail C) Need modification D) Work only if positive edges exist
    Answer: A
    Explanation: MST uses ordering of weights; negativity is fine.
25. The maximum spanning tree (MaxST) can be found by:
    A) Running Kruskal on edges sorted descending B) Running Prim only once C) Running Dijkstra D) Not possible
    Answer: A
    Explanation: Reverse edge order gives maximum total weight tree.
26. If two edges have same weight, and are both minimal across different cuts, can both be in MST?
    A) Yes B) No C) Only one D) Only if graph is complete
    Answer: A
    Explanation: Ties permit multiple MSTs possibly including both.
27. Minimum spanning tree of planar graphs can be computed faster using planarity; true or false?
    A) True (special algorithms exist) B) False C) Only for trees D) Only for triconnected graphs
    Answer: A
    Explanation: Planar-specific optimizations improve constants/exponents.
28. If all edge weights are multiplied by constant c>0, MST set:
    A) Unchanged (same edges) B) Completely different C) Only total scales but edges differ D) Only for c integer
    Answer: A
    Explanation: Relative order preserved; MST unchanged.
29. In dynamic graph where edges inserted, maintaining MST can be done faster than recomputing from scratch; true or false?
    A) True (dynamic MST algorithms exist) B) False C) Only deletions handled D) Only for trees
    Answer: A
    Explanation: Dynamic MST uses link-cut trees, etc., for updates faster in many cases.
30. In maximum bottleneck path between u and v, MST can be used because MST minimizes bottleneck globally. So bottleneck path equals maximum edge on unique path in MST. True or false?
    A) True B) False C) Only for unique MST D) Only for trees
    Answer: A
    Explanation: MST solves minimax edge problem.
31. For sparse graphs (m ≈ n), Prim with Fibonacci heap runs in:
    A) O(m + n log n) ≈ O(n log n) B) O(m log n) C) O(n²) D) O(m²)
    Answer: A
    Explanation: Fibonacci heap yields improved decrease-key amortized cost.
32. Kruskal’s algorithm is naturally parallelizable during early stage — true or false?
    A) True (sorting and disjoint unions parallelizable) B) False C) Only Prim parallelizable D) Only Borůvka parallelizable
    Answer: A
    Explanation: Edges can be processed in parts; Borůvka even more parallel-friendly.
33. If you run Kruskal and remove the heaviest edge in any cycle, you get:
    A) An MST (reverse-delete idea) B) Not necessarily MST C) A min-cut D) Shortest paths
    Answer: A
    Explanation: Removing heavy cycle edges yields MST.
34. Which algorithm can be used to compute MST in O(m α(n)) expected without sorting?
    A) Borůvka combined with randomization and union-find B) Prim with heap C) Dijkstra D) Floyd–Warshall
    Answer: A
    Explanation: Borůvka phases with union-find can produce near-linear time.
35. In a graph with n vertices and m edges, storing edges in adjacency list uses O(n + m) memory. For MST algorithms, this is:
    A) Standard and efficient B) Inefficient C) Incorrect for weighted graphs D) Only for directed graphs
    Answer: A
    Explanation: Weighted adjacency lists store weights too; memory remains O(n+m).
36. Suppose you replace every edge weight w by w^2 (square). Does MST edge set always remain same?
    A) Yes (monotone transform preserving order) if squaring preserves order for nonnegative weights B) No C) Only if weights in {0,1} D) Only for integer weights
    Answer: A (if weights nonnegative)
    Explanation: Squaring is monotone increasing for nonnegative numbers; ordering preserved.
37. If edges are distinct and you run Kruskal, whenever you take an edge it’s always in all MSTs?
    A) Yes (unique due to distinct weights) B) No C) Only if cut unique D) Only after all unions
    Answer: A
    Explanation: Distinct weights make chosen edges uniquely forced.
38. The minimum spanning tree is also the minimum weight connected subgraph with n−1 edges. True or False?
    A) True B) False C) Only for trees D) Only for connected graphs
    Answer: A
    Explanation: MST is minimal weight connected spanning tree.
39. To find MST on complete graph with n nodes using Prim is:
    A) O(n²) with an array implementation (better than sorting m=Θ(n²)) B) O(m log n) slower C) O(n log n) always D) O(1)
    Answer: A
    Explanation: For dense graphs array-based Prim O(n²) is optimal.
40. For graphs with integer weights bounded by W, you can sort edges in O(m + W) using counting sort and run Kruskal faster. True or False?
    A) True B) False C) Only if W small relative to m D) Only if weights distinct
    Answer: A
    Explanation: Counting/radix sorts help when weights small.
41. In Kruskal, initial sets = single vertices; after first phase combining cheap edges components shrink. Which algorithm uses picking cheapest outgoing edge from each component simultaneously?
    A) Borůvka B) Prim C) Dijkstra D) Bellman-Ford
    Answer: A
    Explanation: Borůvka picks cheapest outgoing per component each round.
42. MST is invariant under adding same constant to all edge weights. True or False?
    A) True (order preserved) B) False C) Only for positive constants D) Only if graph complete
    Answer: A
    Explanation: Adding constant shifts all weights equally; relative order unchanged.
43. Minimum spanning tree problem is polynomial-time solvable. True or False?
    A) True (Kruskal/Prim) B) False C) NP-hard D) Requires exponential time
    Answer: A
    Explanation: Classic polynomial-time algorithms exist.
44. In a graph where many edges have identical smallest weight, Kruskal picks some of them; can it miss an MST of smaller total weight than produced?
    A) No — any resulting spanning tree is MST if Kruskal completed properly. B) Yes C) Only when cycles present D) Only for directed graphs
    Answer: A
    Explanation: Kruskal always produces an MST regardless of tie decisions.
45. If the graph has negative cycles, MST concept:
    A) Irrelevant (MST defined for undirected; cycles allowed but negative irrelevant) B) MST undefined C) Must be directed acyclic D) Minimum spanning forest only
    Answer: A
    Explanation: Negative cycles concept is for directed weighted graphs; MST is undirected spanning tree unaffected by directed cycles.
46. In MST, lightest edge overall in the graph is always part of some MST. True or False?
    A) True (cut separating its endpoints contains that edge as lightest) B) False C) Only if unique D) Only for trees
    Answer: A
    Explanation: Global lightest edge is safe.
47. To get a minimum spanning forest in a dynamic setting with deletions, which data structure helps?
    A) Link-cut tree (dynamic tree) B) Simple array C) Stack D) Heap only
    Answer: A
    Explanation: Link-cut trees support dynamic connectivity and updates.
48. MST uniqueness must hold if no two edges have same weight. True or False?
    A) True B) False C) Only if connected D) Only for small n
    Answer: A
    Explanation: Distinct weights enforce unique MST.
49. If you add a vertex with zero-weight edges to all existing vertices (star edges weight 0), the new MST will include how many new edges?
    A) 1 (connect with cheapest zero) — actually, connecting new vertex requires exactly 1 edge to include it; zero-weight edges might replace existing; but final MST must add 1 edge for new vertex.
    Answer: A
    Explanation: A new vertex increases vertices by 1 ⇒ MST grows by 1 edge.
50. In a graph with parallel edges (multi-graph), Kruskal handles them by:
    A) Considering each edge separately; union-find prevents cycles B) Ignoring duplicates C) Merging them first D) Fails
    Answer: A
    Explanation: Kruskal treats parallel edges; the cheaper parallel may be chosen.
51. For computing all-pairs minimax (minimize maximum edge along path) between all pairs, building an MST and querying max on path is:
    A) Correct for undirected graphs (max edge on MST path is minimax) B) Incorrect C) Only for directed graphs D) Only for trees
    Answer: A
    Explanation: MST minimizes maximum edge between any pair.
52. The number of possible different MSTs for a graph with many equal weights can be exponential in n. True or False?
    A) True B) False C) At most polynomial D) At most linear
    Answer: A
    Explanation: Lots of symmetry yields exponentially many MSTs in worst case.
53. To find second-best MST, one approach is to consider each non-tree edge and compute max edge on path in current MST. Complexity naive: O(m n). But using LCA preprocessing you can do it in O(m log n). True or False?
    A) True B) False
    Answer: A
    Explanation: Preprocess MST for max-edge queries on paths to speed up.
54. Minimum spanning tree edges form a basis for cut space? (Graph theory) True or False?
    A) True — MST edges are independent spanning tree edges forming basis-like structure. B) False
    Answer: A (informal)
    Explanation: Tree edges form independent set connecting vertices; matroid view available.
55. A minimum spanning tree minimizes sum of distances between all pairs of vertices. True or False?
    A) False — MST minimizes total edge weight, but not sum of pairwise distances. B) True
    Answer: A
    Explanation: Different objective (Steiner or tree metric) would minimize pairwise sums.
56. In Kruskal, if edges sorted by weight, we can early-stop when we have n−1 edges selected. True or False?
    A) True B) False
    Answer: A
    Explanation: Once n−1 edges chosen spanning all vertices, result MST.
57. MST algorithms are applicable to directed graphs as-is. True or False?
    A) False — MST notion is for undirected graphs; directed version (arborescence) needs algorithms like Edmonds. B) True
    Answer: A
    Explanation: Directed spanning arborescences require different algorithms.
58. The MST is a subgraph of the shortest-path tree from any source. True or False?
    A) False — no general containment; these trees optimize different metrics. B) True
    Answer: A
    Explanation: Shortest-path tree minimizes sum distances from source, not total edge cost.
59. For a graph with metric distances satisfying triangle inequality, the MST approximates TSP tour within factor 2 by doubling MST and shortcutting. True or False?
    A) True (MST gives 2-approx for metric TSP) B) False
    Answer: A
    Explanation: Twice-around-tree technique yields ≤ 2× OPT.
60. A minimum spanning tree must contain the minimum-weight edge incident to each vertex. True or False?
    A) False — not necessarily; cut arguments determine inclusion. B) True
    Answer: A
    Explanation: Edge minimal at a vertex may link to same component; not guaranteed to be in MST.
61. If you contract an edge that is in every MST, the MST of contracted graph corresponds to MST of original with contraction undone. True or False?
    A) True B) False
    Answer: A
    Explanation: Contracting safe edges preserves MST relationships.
62. In dense graphs, Prim with adjacency matrix beats Kruskal because:
    A) Complexity O(n²) vs sorting O(m log m)=O(n² log n) B) Kruskal faster C) Both same D) Not comparable
    Answer: A
    Explanation: For m~n², Prim O(n²) is better.
63. If you remove a non-MST edge, MST remains unaffected. True or False?
    A) True B) False
    Answer: A
    Explanation: Non-tree edges not in MST don’t affect current MST.
64. In an MST, every edge is a bridge in the tree. True or False?
    A) True — removing any tree edge disconnects tree. B) False
    Answer: A
    Explanation: Trees have all edges as bridges.
65. For graphs with multiple components, running Kruskal over all edges yields:
    A) A minimum spanning forest (MSF) covering all components B) Error C) One MST only D) Shortest paths
    Answer: A
    Explanation: Kruskal picks minimal connecting edges per component → MSF.
66. The cycle property implies: if you find a cycle in graph, the maximum weight edge in that cycle is not in at least one MST. True or False?
    A) True B) False
    Answer: A
    Explanation: Removing max-weight in cycle can only help.
67. The matroid formulation: Graphic matroid permits greedy algorithm to find max-weight forest — True or False?
    A) True — MST corresponds to greedy on the graphic matroid. B) False
    Answer: A
    Explanation: MST fits matroid greedy optimality.
68. In computing MST on GPU/parallel machine, Borůvka is often preferred due to embarrassingly parallel phases. True or False?
    A) True B) False
    Answer: A
    Explanation: Borůvka picks cheapest outgoing edges per component independently.
69. If you replace any edge weight by its rank order (1..m) preserving order, MST edges remain same. True or False?
    A) True B) False
    Answer: A
    Explanation: Only ordering matters.
70. A bridge (cut-edge) of original graph must be in every MST. True or False?
    A) True — since removing it disconnects graph, it’s required in any spanning tree. B) False
    Answer: A
    Explanation: Bridges are mandatory in any spanning tree hence MST.
71. For streaming edges where memory limited, can you compute MST online exactly?
    A) With limited memory impossible in one pass generally; need multiple passes or sketches. B) Always possible in one pass. C) Use Prim easily. D) Use Kruskal easily.
    Answer: A
    Explanation: One-pass streaming exact MST is challenging; semi-streaming algorithms exist.
72. If you run Prim but break ties by highest vertex id, result tree:
    A) Is an MST (tie-breaking arbitrary ok) B) Might not be MST C) Fails for nonconnected graphs D) Only for distinct weights
    Answer: A
    Explanation: Any tie-break yields an MST.
73. In MST, replacing an edge e in MST by an edge f not in MST that connects two components formed by removing e gives new spanning tree. The weight increases by w(f)−w(e). For second-best MST, you pick minimal positive such increase. True or False?
    A) True B) False
    Answer: A
    Explanation: Swap analysis gives next minimal spanning tree.
74. Edge-sparsification techniques produce smaller graphs that preserve MST — true or false?
    A) True — e.g., graph sparsifiers maintain approximate MST structure. B) False
    Answer: A
    Explanation: Sparsifiers preserve cuts and approximate MST properties.
75. In a weighted graph, MST is also a minimum spanning tree for the square of weights (w^2) if all weights nonnegative. True or False?
    A) True (monotone transform preserves ordering) B) False
    Answer: A
    Explanation: Monotone transforms keep order of weights.
76. Minimum spanning tree problem is equivalent to finding maximal acyclic subset of edges with minimal total weight. True or False?
    A) True B) False
    Answer: A
    Explanation: MST picks acyclic spanning set minimizing sum.
77. In graph with two equal vertices connected by multiple zero-weight edges, MST will include at most one of those edges. True or False?
    A) True B) False
    Answer: A
    Explanation: More would form cycle; need one to connect.
78. If you know an MST and then lower weight of some non-tree edge, the MST may change and you can update by checking path between endpoints. True or False?
    A) True B) False
    Answer: A
    Explanation: If new weight beats max edge on path, swap occurs.
79. For computing MST in metric spaces using geometric graphs (like Euclidean MST), algorithms exploit geometry for better time. True or False?
    A) True B) False
    Answer: A
    Explanation: Delaunay triangulation reduces candidate edges.
80. Minimum spanning trees are used in clustering (single-linkage). True or False?
    A) True B) False
    Answer: A
    Explanation: MST cut yields single-linkage hierarchical clustering.
81. If you contract all zero-weight edges, MST unaffected (except contracted vertices). True or False?
    A) True B) False
    Answer: A
    Explanation: Safe contraction preserves MST relationships.
82. In Kruskal, when edges are processed in equal-weight blocks, you must ensure you don’t create cycles by simultaneous unions — process block carefully. True or False?
    A) True B) False
    Answer: A
    Explanation: Edges of same weight must be tested using current components before unions.
83. For extremely large graphs, approximate MST (sublinear) is often acceptable for applications. True or False?
    A) True B) False
    Answer: A
    Explanation: Approximate sparsifiers or streaming approximations used.
84. The cut property ensures greedy selection of cheapest edge across some cut always safe. True or False?
    A) True B) False
    Answer: A
    Explanation: It’s the basis of Kruskal/Prim correctness.
85. Minimum spanning tree weight equals half sum of minimum edge incident at each cut? No — tricky. Which statement is true?
    A) There’s no simple half-sum formula. B) Equals sum of minimal incident edges sum/2. C) Equals total degrees. D) Always zero.
    Answer: A
    Explanation: No simple per-vertex local formula yields MST weight.
86. MST edges are subset of edges in all minimum cuts? True or False?
    A) False — not generally. B) True
    Answer: A
    Explanation: Cuts and MST edges relate differently.
87. The set of maximum spanning trees forms a matroid as well. True or False?
    A) True (matroid duality holds; maximum via negating weights etc.) B) False
    Answer: A
    Explanation: Greedy works for matroid; reversing weights finds maximum.
88. For very sparse graphs m ≈ n, Kruskal and Prim have similar complexities. True or False?
    A) True (both near-linear) B) False
    Answer: A
    Explanation: m log m ~ n log n comparable.
89. MST problem with additional constraint that certain edges must be included is solvable by forcing them first and then running MST on contracted graph. True or False?
    A) True B) False
    Answer: A
    Explanation: Contract forced edges’ endpoints; check feasibility.
90. The MST maximizes the number of leaves among all spanning trees. True or False?
    A) False — MST not optimized for leaves count. B) True
    Answer: A
    Explanation: Different objective.
91. Using dynamic programming to compute MST is necessary for small graphs. True or False?
    A) False — greedy is sufficient and faster. B) True
    Answer: A
    Explanation: Greedy algorithms are optimal for MST.
92. The property “any subset of edges of an MST is contained in some MST of corresponding induced subgraph” — true or false?
    A) True (subtrees correspond to MSTs of components) B) False
    Answer: A (informal)
    Explanation: Induced subgraphs may have different structure; but subtree minimal in that component.
93. A heuristic that picks cheapest edge incident to smallest-degree vertex each time guarantees MST. True or False?
    A) False — no simple local-degree greedy guarantee. B) True
    Answer: A
    Explanation: Greedy rules must follow matroid/cut/cycle properties.
94. In a graph with metric weights, computing MST also helps approximate Steiner tree. True or False?
    A) True (approximation) B) False
    Answer: A
    Explanation: MST on metric closure yields approximation.
95. If we add a large constant C to only a subset of edges, MST might change. True or False?
    A) True B) False
    Answer: A
    Explanation: Changing weights selectively alters ordering causing different MST.
96. Kruskal’s algorithm requires sorting edges entirely before union-find operations. Can we avoid full sort?
    A) Using bucket/radix counting when weights bounded can avoid full comparison sort. B) No.
    Answer: A
    Explanation: Counting/radix sorts applicable for integers.
97. Maximum edge weight in MST is less than or equal to maximum edge weight in original graph. True or False?
    A) True B) False
    Answer: A
    Explanation: MST uses subset of original edges.
98. The minimum spanning tree is unique if and only if for every cut the minimum crossing edge is unique. True or False?
    A) True B) False
    Answer: A
    Explanation: Uniqueness equivalent to unique light edges across cuts.
99. MSTs and shortest path trees coincide when?
    A) Only in special graphs where edge weights satisfy certain properties; in general they differ. B) Always coincide.
    Answer: A
    Explanation: Different optimization goals; coincide under specific weight distributions.
100. Final conceptual: To prove Kruskal is correct, typical proof uses:
     A) Cut property and exchange argument (show each chosen edge can be extended to MST) B) Induction on vertices C) Probabilistic method D) Linear programming
     Answer: A
     Explanation: Cut property + exchange proof shows greedy choices are safe.

About the Author

examhopeinfo@gmail.com

Administrator

Visit Website View All Posts