Capstone — Modeling and Solving a Real Graph Problem
Graph Theory
Chapter 10 · Capstone — Modeling and Solving a Real Graph Problem
One continuous scenario, touching every chapter of this course in the order a real engineer would actually reach for each idea: Nimbus, a small startup, is standing up its own office and infrastructure — and every genuinely different problem that comes up along the way turns out to be a graph problem already covered by this course.
| Step | Problem | Chapter(s) used |
|---|---|---|
| 1 | Modeling the office & checking it's fully wired | Ch.2 (representation), Ch.3-4 (traversal, connectivity) |
| 2 | Cheapest dedicated cable run for one camera line | Ch.6 (Dijkstra) |
| 3 | Cheapest way to wire every room, not just one line | Ch.8 (Kruskal's MST) |
| 4 | Is the deployment plan even valid? What order? | Ch.4-5 (cycle check, topological sort) |
| 5 | Fastest request path through a caching layer | Ch.6-7 (Dijkstra fails, Bellman-Ford fixes it) |
| 6 | Reusing the org chart three different ways | Ch.9 (pre/post/level-order) |
Step 1 — The Office Network: Representation & Connectivity
Nimbus has six rooms — Lobby, Eng, Design, Sales, Server (the server closet), Kitchen — with possible direct cable runs between some pairs, weighted by meters of cable: Lobby-Eng(12), Lobby-Sales(8), Lobby-Kitchen(5), Eng-Design(6), Eng-Server(15), Design-Server(20), Sales-Kitchen(10), Server-Kitchen(18). Modeled exactly per Chapter 2: a weighted adjacency list, one entry per room.
{Lobby, Eng, Design, Sales, Server, Kitchen} — confirming Chapter 4's connectivity check: the network is a single connected component before any wiring decisions are even made.
Step 2 — One Dedicated Line: Cheapest Cable Run to the Server
A security camera needs its own dedicated line from the Lobby to the Server closet. Every weight here is real cable length — genuinely non-negative — so Dijkstra is not just usable but the right, efficient default per Chapter 6's own guidance.
{Lobby:0, Sales:8, Kitchen:5, Eng:12, Design:18, Server:23}. Shortest route to Server: Lobby → Kitchen → Server, 5+18=23m — cheaper than the direct-looking Lobby → Eng → Server route (12+15=27m).
Step 3 — Wiring Every Room: A Genuinely Different Question
Step 2 optimized a single point-to-point connection. Wiring the whole office is a different problem entirely — a Minimum Spanning Tree, per Chapter 8, minimizes total cable across every room at once, with no requirement that any particular pair's own route be the cheapest possible.
Lobby-Kitchen(5), Eng-Design(6), Lobby-Sales(8), Lobby-Eng(12), Eng-Server(15) — total 46m.
Eng-Server(15), reached through Lobby-Eng(12) — a combined 27m path to Server, worse than Step 2's dedicated 23m route through Kitchen. That's not a mistake: the MST is minimizing the total cost of connecting everything, and re-using the already-cheap Lobby-Eng-Design backbone costs less overall than also paying for Kitchen-Server(18) on top of Lobby-Kitchen(5). Shortest path and MST optimize genuinely different quantities, and can disagree on individual routes even while both being correct for what they're actually solving.
Step 4 — The Deployment Graph: Is the Plan Even Valid?
Nimbus's services depend on each other: auth→api, database→api, cache→api, api→frontend, api→notifications. Before deploying anything, Chapter 4's directed cycle check confirms this is actually possible.
auth, cache, database, api, frontend, notifications (the three zero-dependency services first, in whatever order, then api once all three of its dependencies are satisfied, then its own two dependents last).
notifications→auth. Re-running the cycle check catches it immediately: auth → api → notifications → auth is a genuine back edge — cycle detected, exactly Chapter 4's own package-manager scenario played out for real. The proposal is reworked to decouple the alert (e.g. via a message queue) rather than adding a direct dependency edge.
Step 5 — Request Latency: Where Dijkstra Actually Breaks
Modeling one request's path in milliseconds: gateway→auth(5), gateway→api(12), auth→api(3), api→database(2), api→cache(5), cache→database(−15), database→response(4). The cache edge is negative — a cache hit genuinely saves more time than it costs to check, exactly the kind of real negative weight Chapter 7 introduced.
database=10 (via api) before ever reaching cache, so response gets relaxed using that stale value: 10+4=14ms. Only afterward does cache(13) get processed, correcting database's own table entry to 13−15=−2 — but database is already finalized, so response never benefits. Dijkstra reports 14ms — the exact same self-correcting-vertex, stuck-downstream-value failure pattern as Chapter 6's own B/D counterexample, playing out again here.
V−1=5 rounds: {gateway:0, auth:5, api:8, cache:13, database:−2, response:2}. True fastest path: 2ms, not Dijkstra's wrong 14ms. The extra check round confirms no negative cycle — a real safety check here, since a negative cycle in a request-latency graph would mean a bug allowing infinite, unbounded "savings."
Step 6 — The Org Chart, Walked Three Different Ways
Nimbus's reporting tree: CEO→{CTO, VP_Sales}, CTO→{Eng_Lead, Design_Lead}, Eng_Lead→{Dev1, Dev2}, VP_Sales→{Sales_Rep}. The same tree, walked three genuinely different ways for three genuinely different real needs.
CEO, CTO, Eng_Lead, Dev1, Dev2, Design_Lead, VP_Sales, Sales_Rep.Level-order (budget-approval escalation, by seniority):
CEO, CTO, VP_Sales, Eng_Lead, Design_Lead, Sales_Rep, Dev1, Dev2.Post-order, used for a headcount rollup (
team_size[node] = 1 + sum of children's team_size, each computed only after its children are done): Dev1=1, Dev2=1, Eng_Lead=3, Design_Lead=1, CTO=5, Sales_Rep=1, VP_Sales=2, CEO=8 — the CEO's own total of 8 correctly matches the tree's actual 8 people, a direct payoff of post-order's own "children before parent" guarantee from Chapter 9.
What This Course Doesn't Cover
As stated honestly back in Chapter 1: network flow, graph coloring, planarity, and graph-database technology specifically were named as out of scope, and stayed out of scope through all ten chapters. This course built the core representational and algorithmic toolkit — traversal, connectivity, ordering, shortest paths, spanning trees, and tree structure — not an exhaustive catalog of every named graph algorithm.
Where This Course Connects
This course leaned directly on Algorithms & Complexity's own recursion and Big-O machinery throughout — Chapter 1 named this destination explicitly, and Chapters 3 through 8 all reused it for analyzing traversal and shortest-path cost. Discrete Mathematics Fundamentals' own relations material (Chapter 5 there) is the formal ancestor of a graph itself — this course is, in a real sense, what happens when a relation gets a name and a picture. Within Technical Support, netdiag1's own network-troubleshooting material and this course's shortest-path/connectivity chapters describe the same underlying kind of structure from two different angles — one diagnostic, one mathematical.
Hands-On Exercises
Nimbus adds a seventh room, Storage, connected only by Design-Storage(7). Using this chapter's own Step 3 MST as a starting point, state the new MST's total weight and explain why adding one new leaf edge to an existing MST never requires re-examining any of the other edges already chosen.
A new service, logging, needs to depend on api (edge api→logging), and nothing needs to depend on logging in return. Using this chapter's own Step 4 deployment graph plus this new edge, give a full valid deployment order via Kahn's algorithm, showing the in-degree of every service at the start.
Step 5 showed Dijkstra reporting 14ms for gateway→response when the true value is 2ms. Explain specifically why Dijkstra's own cache distance (13) and database distance (−2, after correction) both end up numerically correct in the final table, despite the overall response result being wrong — reusing this chapter's own explanation pattern from Step 5, not just restating that Dijkstra "doesn't work" with negative weights.
Chapter 10 Quick Reference
- Full worked project: representation & connectivity (Ch.2-4) → Dijkstra for one route (Ch.6) → Kruskal's MST for every room (Ch.8) → cycle check & topological deployment order (Ch.4-5) → Dijkstra fails, Bellman-Ford fixes it (Ch.6-7) → one tree, three traversal purposes (Ch.9)
- Shortest path and MST are genuinely different questions — they can and did disagree on Server's own best route
- The same negative-weight failure pattern from Chapter 6 (a self-correcting vertex whose correction never reaches a downstream neighbor) reproduced exactly in a completely different scenario
- Post-order's "children before parent" guarantee (Ch.9) is what makes a bottom-up rollup like a headcount total actually correct
- Out of scope: network flow, graph coloring, planarity, graph-database technology
- Course complete — Graph Theory, 10 chapters, from representation to a full worked infrastructure project