COMP9123 — Week 8
Foundations & proof moves
Week 8 foundations turn graph traversal into a set of reusable proof habits: count vertices and edges correctly, match representation to runtime, use BFS layers for distance arguments, and use DFS tree structure to detect bridges and cut vertices.
Counting Facts: Small Identities That Prevent Big Mistakes
Graph proofs get much easier when a few identities are automatic. These facts are the graph equivalent of knowing how many edges a binary tree has or how many terms a summation contributes.
| Fact | Meaning | How it gets used |
|---|---|---|
| \(\sum_{v\in V}\deg(v)=2m\) for undirected graphs | Each undirected edge contributes to two endpoint degrees. | This is the cleanest way to justify many \(O(m)\) degree-sum arguments. |
| A tree on \(n\) vertices has \(n-1\) edges | Trees are exactly connected acyclic graphs with the minimum number of edges needed for connectivity. | Helps check whether a spanning subgraph can really be a tree. |
| Simple undirected graph: \(m \le n(n-1)/2\) | You can choose at most one edge per unordered vertex pair. | This is why adjacency matrices become plausible only when the graph is dense. |
Representation Cost: Why the Same Traversal Can Be Linear or Quadratic
The lecture's performance table is one of the highest-value slides in the week. It teaches a habit that goes beyond graphs: whenever an algorithm repeatedly asks “what are the neighbors of this object?”, the underlying representation can completely change the runtime.
| Operation | Adjacency list | Adjacency matrix |
|---|---|---|
| Space | \(O(n+m)\) | \(O(n^2)\) |
incidentEdges(v) |
\(O(\deg(v))\) | \(O(n)\) |
getEdge(u,v) |
\(O(\min(\deg(u),\deg(v)))\) | \(O(1)\) |
| BFS / DFS traversal | \(O(n+m)\) | \(O(n^2)\) |
This is exactly why the tutorial includes a special adjacency-matrix problem about a get-stuck vertex. Sometimes the matrix is not a mistake; it is the right representation for the query pattern.
Traversal Invariants: The Correctness Story Behind DFS and BFS
Most Week 8 proofs are invariant proofs in disguise. They ask what stays true about discovered vertices, parent edges, or layer numbers while the traversal runs.
Each time DFS discovers a new vertex, the parent pointer records a tree edge in the DFS forest. Once the traversal of a component finishes, those parent edges form a spanning tree of that component.
If a vertex is first discovered in layer \(L_i\), then there exists a path of exactly \(i\) edges from the source to that vertex, and no shorter path exists. This is the engine behind shortest-path and bipartite proofs.
Suppose \(u\) is in layer \(L_i\). Then BFS has already found a path of length \(i\) from the source to \(u\).
If \((u,v)\) is an edge, then appending that edge gives a path to \(v\) of length at most \(i+1\), so \(v\) cannot be in a layer farther than \(L_{i+1}\).
By symmetry, \(u\) cannot be more than one layer away from \(v\) either, so \(|d(u)-d(v)| \le 1\).
Bridge Criterion: Turning DFS Structure into a Linear-Time Test
The bridge material is the first moment in the graph unit where DFS stops being just a traversal and becomes an information-extraction tool. The traversal tree tells you what the obvious upward routes are, and the back edges tell you what alternative upward routes still exist.
For each vertex \(v\), the lecture defines level[v] in the DFS tree and down_and_up[v], the highest ancestor level reachable by first moving down the DFS tree and then using one back edge upward.
For a DFS tree edge \((u,v)\) where \(u = parent[v]\), the edge is not a bridge if and only if down_and_up[v] ≤ level[u]. If that inequality fails, the subtree under \(v\) has no alternate route back.
Cut vertices are the natural follow-up. The tutorial asks you to adapt the cut-edge reasoning by asking whether removing a vertex destroys the last route between parts of the DFS tree.
Applications: Recognizing Which Traversal Fact Solves Which Problem
The later tutorial problems are pattern-recognition drills. They are not asking for ten unrelated algorithms. They are asking whether you can match a problem to the right graph invariant.
| Problem type | Main idea | Relevant Week 8 fact |
|---|---|---|
| Bipartite testing | Use BFS layers as a two-coloring guide | An edge inside one layer is evidence against bipartiteness |
| Get-stuck vertex in adjacency matrix | Eliminate impossible candidates without scanning every matrix entry | Representation matters as much as the graph property |
small(i) for each vertex |
Compute component minima and assign them to whole components | Connected components are the natural reusable unit |
| Snakes and Ladders | Model board positions as vertices and legal moves as edges | BFS gives the minimum number of dice rolls |
How to review this page well
The three quick checks are now attached directly to the facts they test: tree counting, BFS layer reasoning, and BFS-based bipartite detection. If one feels shaky, the fix is local: re-read that section and narrate the argument using a tiny hand-drawn graph.
Tutorial review
Open the tutorial after the study guide, not before. Week 8 goes much better when the pictures in the sheet feel like instances of ideas you already understand rather than fresh notation to decode.
Tutorial 8 checklist. You should be able to compare adjacency lists against matrices, trace one BFS layering and one DFS order by hand, explain why disconnected graphs require a restart loop, prove the layer bound \(|d(u)-d(v)| \le 1\), identify the BFS sign of non-bipartiteness, and state the down-and-up bridge criterion in words.