Practice Solutions and Feedback

Compare reasoning as well as values. Different traversal orders, optimal trees, cuts and matchings may be valid; check their contracts instead of incidental labels.

P1–P4: model and representation

P1. Directed distances are [0,2,2,None], route to 2 uses original IDs 1,2. Vertex 3 stays declared and unreachable. Zero weight is a real edge. Undirected interpretation permits travel back from 2 to 0; that is a changed graph contract. P2. Matrix: 100 million cells, 800 million payload bytes at eight bytes each. Lists: 10,000 headers and 30,000 directed records; bytes depend on containers, references and record layout. A scalar matrix cannot preserve parallel identities without additional metadata. P3. Triangle plus one isolated vertex has V=4, E=3 but is not a tree. Directed edges 0→1,1→2,0→2 form a DAG with an undirected triangle. An undirected triangle is not bipartite. E<=3V-6 needs a simple planar graph and V>=3. P4. Use B→A for prerequisite-first ordering. Matching maps each allowed selected pair to a unit path and integral unit flow maps back to distinct-endpoint pairs. Capacity two at worker edges changes the feasible output from matching to a capacitated assignment; update the proof and extraction.

P5–P8: traversal and structure

P5. Distances [0,1,1,2,None]. Vertex 3 can parent through 1 or 2. FIFO processing completes earlier layers first, so a shorter predecessor would already have discovered the vertex. Mark on enqueue. A direct cost-10 edge versus a two-hop route of costs 1,1 separates hop count from weighted cost.

P6. Discovery 0,1,2; finish 2,1,0. Edge 2→1 is back to a gray ancestor; later 0→2 is forward to a finished descendant. An iterative frame must retain the next neighbor to examine and finish only after exhaustion. In an undirected multigraph skip only the reverse incidence of the tree-edge ID; another parent edge can close a two-edge cycle.

P7. SCCs {0,1},{2},{3},{4} with condensation edge sequence {0,1}→{2}→{3} and isolated {4}. One original finish order is 3,2,1,0,4; search the transpose in reverse. Weak connectivity merges 0 through 3, and one source traversal gives reachability, neither mutual reachability nor maximal groups. Check all vertex pairs against a reachability oracle and ensure each vertex occurs exactly once.

P8. [0,1,4,2,3] and [4,1,0,2,3] are valid. Adding 3→2 creates a cycle on 2,3; 0,1,4 can still be emitted by Kahn, but there is no full topological order. A vertex reached by an edge out of this cycle can also stay blocked while belonging to no cycle. Use SCCs to distinguish the cause from downstream effects.

P9–P12: route semantics

P9. Unit hops: BFS. Signed DAG: topological relaxation. Nonnegative general graph: Dijkstra. General signed graph: Bellman–Ford with scoped cycle effects. Small dense all-pairs: Floyd–Warshall is a candidate if its V² storage and V³ arithmetic fit. Unbounded requires a negative cycle reachable from source and able to reach target; unreachable means no source-to-target walk at all.

P10. Distances [0,2,1,4], parent IDs [None,2,1,3]. (5,1) is stale after improvement to (2,1). Finalize at current minimum extraction, not first discovery. O(E) improving entries yield O(V+E log(E+2)) time and O(V+E) space including graph construction for the lazy implementation. Indexed-heap bounds do not automatically apply to this heap.

P11. Snapshot first round gives [0,1,None]; listed-order in-place pass gives [0,1,2]. The latter can use several newly improved edges in one pass. In the six-vertex graph, source-0 labels are [0,-inf,-inf,-inf,7,None]: cycle 1–2 has weight -2, reaches 3 but not 4, and the cycle at 5 is disconnected from source. Affected status follows outgoing reachability from negative-cycle effects.

P12. Initial rows are [0,4,9], [None,0,-2], [None,None,0]. Allowing intermediate 1 improves 0→2 to 2; k outside the i,j loops implements the allowed-intermediate invariant. Retain the minimum parallel weight, not the last seen one. An isolated negative self-loop at 3 makes only pair (3,3) unbounded; pairs to/from other vertices stay unreachable and previous finite pairs stay finite.

P13–P16: forests and changed objectives

P13. Each of the triangle's three two-edge subsets is an MST of weight 2. A light cut edge belongs to some MST; if uniquely light, every MST. A heavy cycle edge can be omitted by some MST; if uniquely heavy, it belongs to no MST. Respecting the chosen forest ensures the exchanged crossing edge is not committed. Equal weights yield another optimum, not a strict contradiction.

P14. Choose IDs 1 and 0 for total 1; vertex 3 stays isolated. The negative loop cannot improve a forest because it violates acyclicity. There are c=2 components, so V-c=2 edges. Enumerate subsets of that size, retain those with exactly the input component partition, and minimize sum. Coverage plus edge count implies a forest; checking weight alone would admit invalid subsets.

P15. MST uses 0–1 and 1–2, total 4; shortest-path tree from 0 uses direct 0–1 and 0–2 with source distances 2 and 3. Prim key is attachment edge cost; Dijkstra key is accumulated source route cost. Prim restarts for each component. Lazy queue state can scale with E; indexed queue state keeps one key per vertex.

P16. Tree sums are 3,3,4, and every tree's bottleneck is 2. Two different optima exist at 3; strictly second-best cost is 4. A maximum-edge replacement with equal weights finds another optimum. Ignoring that zero-cost swap without considering removal of the lower edge misses the strict alternative. Define the question before selecting an extension algorithm.

P17–P20: flow and reduction

P17. Second residual path s→b→x→a→y→t cancels a→x. In listed input order, final flow [1,1,0,1,1,1,1] has value 2. Each original record owns its own forward/reverse residual pair; original antiparallel channels remain separate.

P18. Integral augmentations increase value by at least one, but the numeric maximum may be enormous compared with its binary encoding. Edmonds–Karp bounds critical saturation events by O(V) per oriented edge using nondecreasing BFS levels and a two-level increase before repeated critical use. It yields O(VE) augmentations and the usual O(VE²) search work. Scaling every capacity in P17 by 10^30 permits two bottleneck augmentations of 10^30 each; integer arithmetic still depends on bit width rather than being literally free.

P19. Flows [2,2,1] are feasible and value 3. Cut {s,a} has capacity 2+1=3. [3,2,1] leaves an excess unit at a and inconsistent terminal values, so it fails even if reported scalar value is 3. With no residual source-to-sink path, reachable side S has saturated outgoing cut edges and zero incoming cut flow, establishing value equals outgoing original capacity. Count incoming flows negatively in the net-flow identity, not as extra capacity.

P20. {(0,0)} is maximal of size 1; {(0,1),(1,0)} is maximum of size 2. Capacity-one terminal edges prevent repeated endpoints; integrality makes positive pair flows actual discrete assignments. Three left vertices sharing only two neighbors form a Hall obstruction: |N(X)|=2<3=|X|. Stability preferences and minimum money cost are additional objectives, not consequences of cardinality.