Skip to main content

MST Variants and Applications

What This Concept Is​

Changing an MST requirement can change both the algorithm and its proof. Maximum total spanning weight can be reduced by negating weights. Every MST is a minimum-bottleneck spanning tree, but a minimum-bottleneck tree need not minimize the total. A directed spanning arborescence requires a root and orientation constraints; undirected Kruskal is not a solution to that problem.

Why It Matters Here​

Extensions are useful only with explicit assumptions. Extra terminals, degree limits, reliability constraints or tie semantics are not harmless additions to the original objective. Use this lesson to practice revising a proof when the problem changes, rather than memorizing variant names.

Concrete Examples​

Triangle weights 1,2,2 has an MST of total 3 and bottleneck 2. The tree using both weight-2 edges also has bottleneck 2 but total 4, proving the converse false.

For any MST tree path from s to t, remove its maximum-weight edge e. Every alternative s-to-t path crosses that cut with an edge of weight at least w(e), or exchanging it would improve the MST. Thus the tree path minimizes maximum edge weight, though not necessarily the sum.

For complete nonnegative metric TSP, double an MST, traverse the resulting Eulerian walk, then shortcut repeated vertices using triangle inequality and return to the start. Cost is at most twice optimum. The repeated-vertex walk itself is not a Hamiltonian tour; shortcutting and metric assumptions are essential.

Common Confusion / Misconceptions​

"Second best" may mean another tree of equal optimum cost or the smallest strictly larger cost. On the 1,2,2 triangle, adding a non-tree weight-2 edge and removing a maximum weight-2 tree edge finds another optimum. To get strict cost 4 one may instead remove the weight-1 edge. Simply discarding zero-cost maximum edge swaps can miss the strictly second-best answer.

How To Use It​

Pick one extension and state its objective, feasibility and assumptions. Single-linkage clustering under a defined dissimilarity model can use Kruskal's merge sequence; it does not universally solve other clustering objectives. Steiner and directed arborescence algorithms belong on a separate depth path, not as unexplained required coding tasks in this foundations module.

Check Yourself​

  1. Why does minimum bottleneck not imply minimum total weight?
  2. Where does metric TSP shortcutting use triangle inequality?
  3. What ambiguity does "second best" hide?
  4. Why is a directed arborescence not an undirected MST?

Mini Drill or Application​

Enumerate every tree of the 1,2,2 triangle and report both "different optimum" and "strictly more expensive optimum" answers. Prove the minimax path property on a fresh graph. Do not claim a universal reliability optimization without specifying how edge reliability combines. See P16.

Read This Only If Stuck​

Find MST variants, minimax paths, and approximation assumptions in Skiena, CLRS, or Sedgewick and Wayne. These are book indexes, not exact section links. The reading guide names bounded assignments and local source files. Attempt the worked examples before adding more reading.