Skip to main content

Worked Examples

Try each prompt before uncovering its derivation. The examples distinguish output values from witnesses and name the assumptions that make the method valid.

1. One drawing, several contracts​

Declare vertices 0–3 and edge records 0:(0,1,5), 1:(0,1,2), 2:(1,2,0). For directed additive routing, distances from 0 are [0,2,2,None] and a route to 2 uses edge IDs [1,2]. Treating zero as absence loses the route's last edge; forgetting isolated vertex 3 changes the output domain. Treating records as undirected changes reachability from 2. A scalar adjacency matrix may keep the minimum parallel weight for distances, but must also retain an edge ID if a physical-route witness is required. Transfer: capacities may be combined for a flow value, but recovering per-channel flows then needs additional work.

2. BFS needs a layer invariant and a path witness​

For 0→1,0→2,1→3,2→3 and isolated 4, BFS from 0 gives [0,1,1,2,None]. The source enters the queue at level zero. Scanning either level-one predecessor first can discover 3 at level two; mark it immediately so the second predecessor does not enqueue it again. The two possible parent paths to 3 are both correct.

Any shorter route would have a predecessor in an earlier completed layer, which would already have discovered 3. Verify the selected edge sequence starts at 0, ends at 3, is contiguous and has length 2. Transfer: assigning direct edge 0→3 weight 10 makes it the fewest-hop route even if a two-edge route costs only 2; BFS has not become a minimum-weight solver.

3. SCCs isolate cycles, not every blocked vertex​

Graph 0→1,1→0,1→2,2→3 with isolated 4 has SCCs {0,1},{2},{3},{4}. Its condensation is {0,1}→{2}→{3} plus {4}. Kahn's original-graph order cannot emit 0,1,2,3, but only 0 and 1 lie on a cycle. Calling all unemitted vertices "cyclic" misdiagnoses 2 and 3, which are downstream victims.

Kosaraju first records real DFS finish events, then searches the transpose in decreasing finish order. For first root 0 and increasing adjacency order, one finish sequence is 3,2,1,0,4. Transpose traversal in reverse finds the components above. The component order is incidental; mutual reachability determines correctness. Transfer: replacing finish order with discovery order or omitting transposition can merge or split components incorrectly.

4. Dijkstra finalizes at extraction​

Edges by ID: 0:0→1:5, 1:0→2:1, 2:2→1:1, 3:1→3:2. After source relaxation, the heap contains cost 5 for 1 and cost 1 for 2. Extract 2 and improve 1 to cost 2; extract 1 and discover 3 at 4. Final distances are [0,2,1,4], with parent edges [None,2,1,3]. The older cost-5 record for 1 is stale and skipped. Stopping when 1 was first discovered would give the wrong answer. The nonnegative suffix of any alternative path is what makes current minimum extraction safe. Transfer: change 2→1 to -10 and use source edges of weights 2 and 5; standard finalization can fail.

5. Bellman–Ford has three result states​

Edges are 0→1:2,1→2:-3,2→1:1,2→3:4,0→4:7,5→5:-1. Cycle 1→2→1 has total -2 and is reachable from 0; traversing it repeatedly reduces cost without bound before continuing to 3. Thus from 0 the answer is [0,-inf,-inf,-inf,7,None]. Vertex 4 is reachable but not downstream of that cycle. Vertex 5 has a negative self-loop but is unreachable from 0.

After V-1 in-place passes, seed heads of still-improving reachable edges and mark their descendants. Do not propagate affected status backward to unrelated ancestors or sideways to every reachable vertex. A finite path to vertex 4 remains an appropriate witness; no finite optimum path exists for 3. Transfer: from source 5, only vertex 5 is unbounded and the other vertices are unreachable. A global cycle flag loses this distinction.

6. Tied MST edges require existential statements​

For an undirected triangle with all weights 1, every pair of edges is an MST of total 2. Each edge is a maximum on the cycle but each also belongs to some MST. The non-strict cycle rule promises that some MST excludes a chosen maximum; only a uniquely heaviest cycle edge is excluded from every MST.

To extend a chosen forest, take a cut respecting that forest and a light crossing edge. If an optimum lacks it, add it and exchange out another crossing edge on the resulting cycle, without increasing weight or removing a committed edge. On disconnected input add one tree per component; isolated vertices need no edge. Transfer: for four vertices with 0–1:2,1–2:-1,0–2:4, the forest uses the first two edges for total 1 and leaves vertex 3 isolated.

7. MST paths answer a different question​

Triangle 0–1:2,1–2:2,0–2:3 has MST edges 0–1 and 1–2, total 4. Its 0-to-2 tree route costs 4 while the direct route costs 3, so it is not an additive shortest-path tree from 0. However its largest route edge is 2, better than the direct route's largest edge 3. Removing a maximum tree-path edge gives a cut that every alternate route must cross with an edge at least that heavy, or the MST could be improved. Transfer: triangle weights 1,2,2 also has a minimum-bottleneck tree of total 4; minimum bottleneck does not imply minimum sum.

8. Residual cancellation repairs a matching choice​

Use unit edges s→a,s→b,a→x,a→y,b→x,x→t,y→t. First augment s→a→x→t with one unit. Then augment s→b→x→a→y→t; residual x→a cancels flow on original a→x. Final positive paths are s→a→y→t and s→b→x→t. The original-edge flow vector in the listed order is [1,1,0,1,1,1,1].

Every internal vertex conserves flow and each edge stays within capacity. Source cut {s} has capacity 2, matching flow value 2, so optimum is certified. Without reverse arcs the first choice can trap a forward-only implementation at 1. Transfer: an original x→a edge, if added, has its own capacity and flow; it is not interchangeable with the cancellation record of a→x.

9. A correct maximum value with an invalid witness still fails​

For edges s→a:3,a→t:2,s→t:1, optimum value is 3 using flows [2,2,1]. The cut {s,a} has outgoing capacity 2+1=3. Claimed flows [3,2,1] obey individual capacities but violate conservation at a and disagree on terminal net values. A checker that tests only the scalar value 3 misses the defect.

Reconstruct positive residual reachability from the per-edge witness: forward residual capacity c-f and reverse capacity f. Validate that the reported cut is the reachable source side and excludes t. Transfer: lower a→t capacity to 1; both a new feasible flow and an equal-capacity cut are needed to certify value 2.

10. Matching is a reduction with limits​

Allowed worker/job pairs (0,0),(0,1),(1,0) admit two matches, (0,1),(1,0). Greedy (0,0) alone is maximal but not maximum. Each matching gives an integral unit flow; conversely the capacity-one edges incident to each worker/job enforce distinct endpoints in an integral flow. This proves objective preservation in both directions, rather than relying on a suggestive network drawing.

If three workers all connect only to jobs 0 and 1, no complete assignment exists: their neighbor set has size two. If workers may take two jobs, increase source capacities and change the output contract. If preferences must be stable or assignments minimize monetary cost, maximum cardinality alone is insufficient.