This covers minimum spanning trees (MSTs), Kruskal's algorithm, Floyd-Warshall for all-pairs shortest paths, and the hidden-city flight extension. You need to know MST properties cold (same weight, cycle creation, when uniqueness holds), recognise when a graph problem maps to MST or shortest-path, and be able to extend Floyd-Warshall for non-standard path definitions.
Difficulty: Intermediate
Prerequisites: basic graph terminology (vertices, edges, weights, paths, trees, cycles), Big-O notation, and familiarity with greedy algorithms. You should also be comfortable with the concept of a spanning tree before reading this.
Graph algorithms form a major strand of EECS 376. The midterm focuses on two families: minimum spanning tree algorithms (Kruskal, Prim) and shortest-path algorithms (Floyd-Warshall). Both appear in direct questions ("which algorithm solves this?") and in extended problems where you modify the standard algorithm for a new objective (hidden-city flights). Understanding MST properties is also essential for the True/False and All/Some/No sections, which test whether you can reason about edge weights, cycle formation, and what happens when you perturb a graph.
The vertex-assignment problem (maximising a value function by flipping vertex labels) ties graph structure to the potential-function termination technique from the algorithms unit, bridging the two halves of the midterm.
Minimum Spanning Tree (MST)
A subset of edges of a connected, weighted graph that connects all vertices with the minimum possible total edge weight and contains no cycles. In simple terms, it is the cheapest way to wire every node together without any loops.
Kruskal's Algorithm
A greedy algorithm that builds an MST by sorting all edges by weight and adding them one by one, skipping any edge that would create a cycle. Think of it as "always pick the cheapest edge that does not close a loop."
Floyd-Warshall Algorithm
A dynamic-programming algorithm that computes the shortest path between every pair of vertices in a weighted graph, using an intermediate-vertex relaxation: d^k(i, j) = min(d^(k-1)(i, j), d^(k-1)(i, k) + d^(k-1)(k, j)). In simple terms, it asks: "Is it cheaper to go from i to j directly, or to route through vertex k?"
Hidden-City Flight
A path from u to v in a graph where v is an intermediate or final vertex. The cost is the total edge weight of the entire path, not just the portion up to v. The cheapest hidden-city flight from u to v is the minimum of the shortest direct path from u to v and the shortest path from u through v to any other vertex.
Spanning Tree
A subgraph that is a tree (connected, acyclic) and includes every vertex of the original graph. A connected graph with n vertices has a spanning tree with exactly n - 1 edges.
Graph Weight (of a tree or path)
The sum of the weights of all edges in the tree or path.
All MSTs of a single graph G have the same total weight. The proof is by contradiction: if two MSTs had different weights, the one with higher weight would not be minimum.
Adding any edge to an MST creates exactly one cycle. An MST is "maximal without cycles," meaning it has n - 1 edges for n vertices and any additional edge closes a loop.
Having two edges of the same weight does not guarantee multiple MSTs. Counterexample: a path graph A-B-C where both edges have weight 1. There is only one spanning tree (the path itself), and it contains both equal-weight edges.
If you add a new vertex v with two edges to existing vertices u and w, then T (the old MST) union {(v,u), (v,w)} is never an MST of the new graph. It has n edges for n + 1 vertices, which means it contains a cycle. An MST must be acyclic.
Doubling the weight of the third-lightest edge sometimes increases the MST weight and sometimes does not, depending on whether that edge is in the MST and whether an alternative exists.
Kruskal builds an MST greedily: sort edges by weight, add each edge if it does not create a cycle (using a union-find structure).
The beehive-cover problem is a classic MST application: hives are nodes, distances are edge weights, and you want to connect all hives with minimum total covering. Kruskal solves it directly.
Checking whether a given tree T is an MST of a graph G is decidable: compute an MST T' of G using Kruskal, verify T is a spanning tree, and check that T and T' have equal total weight.
Floyd-Warshall computes shortest paths between all pairs of vertices by relaxing through intermediate vertices one at a time:
d^0(i, j) = w(i, j) (direct edge weight, or infinity if no edge)
d^k(i, j) = min(d^(k-1)(i, j), d^(k-1)(i, k) + d^(k-1)(k, j))
After |V| iterations, d^|V|(i, j) is the shortest path from i to j.
Hidden-city extension: a hidden-city path from u to v is any path that starts at u and passes through v (v may be intermediate or final). The cheapest such path is:
h(i, j) = min over all k of { d(i, j) + d(j, k) }, initialised to h(i, j) = d(i, j).
This works because a hidden-city path is either a standard shortest path to v, or a standard shortest path to v followed by a standard shortest path from v onwards.
A common mistake is trying to compose two hidden-city paths. If the best hidden-city path from u to z is (u, z, w) and from z to v is (z, v), combining them gives two disjoint segments (u, z, w) and (z, v), which is not a valid path.
Given a graph with edge weights, assign each vertex a value in {-1, +1} to maximise a value function Val(S).
The greedy flipping algorithm: start with all vertices set to 1, then repeatedly flip any vertex whose flip increases Val(S). Stop when no improving flip exists.
Termination proof: Val(S) is bounded (between negative and positive sum of all |w(e)|) and strictly increases with each flip by at least 1 (since weights are integers and the change is a sum of integer weights). This gives an upper bound of 2 * sum(|w(e)|) on the number of iterations for integer weights, or sum(w(e)) for positive weights.
Alternative termination argument: there are only 2^|V| possible assignments. Since Val(S) strictly increases, no assignment is visited twice, so the algorithm terminates in at most 2^|V| - 1 iterations.
Floyd-Warshall recurrence
d^0(i, j) = w(i, j) d^k(i, j) = min( d^(k-1)(i, j), d^(k-1)(i, k) + d^(k-1)(k, j) )
Final answer: d^|V|(i, j) for all pairs (i, j).
Hidden-city algorithm
d = FloydWarshall(G, w)
For all i, j: h(i, j) = d(i, j)
For all i, j: for all k: h(i, j) = min( h(i, j), d(i, j) + d(j, k) )
Return h
Vertex assignment value (Version 1, integer weights)
Val(S) = sum over edges (u,v) of S(v) * S(u) * w(e)
Bounded by: -sum(|w(e)|) <= Val(S) <= sum(|w(e)|)
Vertex assignment value (Version 2, positive weights)
Val(S) = sum over edges (u,v) of (1/2) * |S(v) - S(u)| * w(e)
Bounded by: 0 <= Val(S) <= sum(w(e))
Students often think that two edges of equal weight automatically mean multiple MSTs. This is false. Equal-weight edges produce multiple MSTs only if they are interchangeable within the MST structure (e.g. a triangle with all edges weight 1).
A frequent error on the hidden-city problem is attempting to compose two hidden-city sub-paths into one. A valid hidden-city path from u to v is a single connected path, not two separate segments.
Students sometimes forget that adding any edge to an MST necessarily creates a cycle. This is the defining property that makes T union {new edges} fail to be a tree.
On the vertex-assignment problem, students try to argue termination from the number of vertices alone without establishing that Val(S) strictly increases. You need both: a bounded quantity and strict monotonicity.
MST True/False questions are common. Know: all MSTs share the same weight; adding an edge to an MST creates a cycle; equal-weight edges do not guarantee multiple MSTs; a multi-tape TM deciding MST membership is no more powerful than a single-tape TM (MST membership is decidable regardless).
The beehive-style word problem ("connect everything with minimum total cost") maps to MST. Expect to identify the algorithm, not just name it.
Floyd-Warshall may appear as a building block for a custom problem (hidden-city flights). Know the recurrence and be ready to modify the outer loop or post-processing step.
The vertex-assignment problem tests your ability to identify a potential function in a non-obvious setting and bound the number of iterations.
True or False: All MSTs of a graph have the same total weight.
True or False: Adding any edge to an MST produces a graph with exactly one cycle.
Fill in the blank: Floyd-Warshall's time complexity is O(___).
True or False: The composition of two hidden-city paths is always a valid hidden-city path.
True or False: A graph with two equal-weight edges always has more than one MST.
Answers: 1. True. 2. True. 3. |V|^3. 4. False (the combined segments may not form a connected path). 5. False (counterexample: a path graph).
Q: Diego wants to connect all his beehives with the minimum total covering. Which algorithm solves this and why?
A: Kruskal's algorithm. The hives are nodes in a complete graph, edges are weighted by distance between hives, and an MST connects all hives with minimum total distance.
Q: Let L = {(T, G) : T is an MST of graph G}. Is L decidable?
A: Yes. A decider computes an MST T' of G using Kruskal, verifies that T is a spanning tree of G, and checks that T and T' have equal total weight.
Q: You add a new vertex v to a graph G with edges to existing vertices u and w. Is T union {(v,u), (v,w)} an MST of the new graph?
A: Never. T has n - 1 edges for n vertices. Adding two edges and one vertex gives n + 1 edges for n + 1 vertices. A spanning tree needs exactly n edges for n + 1 vertices, so the result has one too many edges and contains a cycle.
Q: Describe how to find the cheapest hidden-city flight from u to v using Floyd-Warshall.
A: First run Floyd-Warshall to get all-pairs shortest distances d(i, j). Then for each pair (i, j), set h(i, j) = min over all k of { d(i, j) + d(j, k) }, starting from h(i, j) = d(i, j). The key insight is that a hidden-city path is either a standard path to v, or a standard path through v and then on to some further vertex.
Kruskal's algorithm is a greedy algorithm, connecting to the paradigm-identification questions in the algorithms unit. Floyd-Warshall is dynamic programming, and its intermediate-vertex relaxation is a pattern that appears in other DP problems. The vertex-assignment termination proof uses potential functions, the same technique applied to the Euclidean algorithm. MST decidability connects to the computability unit: the language {(T, G) : T is an MST of G} is decidable because you can compute and compare in finite time.
EECS 376, Foundations of Computer Science, UMich, midterm review, minimum spanning tree, MST, Kruskal's algorithm, Prim's algorithm, Floyd-Warshall, all-pairs shortest paths, hidden-city flight, hidden-city ticketing, graph algorithms, spanning tree, edge weight, cycle property, cut property, greedy MST, dynamic programming shortest path, vertex assignment, graph cut, potential function, termination, weighted graph