Special Graph Classes | Algorithms II

Directed Acyclic Graphs (DAGs)

A DAG is a directed graph containing no directed cycles. Many real-world dependency structures are naturally acyclic: course prerequisites, build system targets (make), version histories.

Existence of sources and sinks: Every DAG has at least one source (in-degree 0) and at least one sink (out-degree 0). Proof: pick any vertex and follow incoming edges backward. Since there are no cycles and the graph is finite, this walk must terminate at a source. Symmetrically, following outgoing edges forward reaches a sink. This property is used in the source-removal topological sort algorithm.

Topological ordering: A linear ordering exists such that all edges go left to right iff the graph is a DAG. See topological sort for the full algorithm.

SSSP on DAGs: Relax edges in topological order. Correctness: when vertex $u$ is processed, all incoming paths to $u$ have already been considered because all predecessors appear earlier in the topological order. Thus one pass suffices. Running time: $\Theta(|V| + |E|)$ , even with negative edge weights (provided no cycles exist, which they cannot in a DAG). This is the fastest SSSP algorithm amongst those covered.

Longest path on DAGs: By negating all edge weights, or replacing $\min$ with $\max$ during relaxation, the longest path can also be found in $\Theta(|V| + |E|)$ . For general graphs, the longest path problem is NP-hard; DAGs are a notable exception.

Bipartite Graphs

A graph is bipartite if its vertex set can be partitioned into two disjoint sets $L$ and $R$ such that every edge has one endpoint in each set. No edges exist within $L$ or within $R$ .

Characterisation: An undirected graph is bipartite iff it contains no cycle of odd length. A graph with a triangle ( $K_3$ ) is never bipartite; a tree is always bipartite.

Testing bipartiteness (BFS-based algorithm):

Pick any unvisited vertex, colour it BLACK.
Run BFS from it. Colour each vertex at distance $d$ : BLACK if $d$ is even, RED if $d$ is odd (alternating by parity).
Scan all edges. If any edge connects two vertices of the same colour, an odd cycle exists — the graph is not bipartite.
Repeat for each connected component until all vertices are processed.

Both colouring and conflict checking run in $O(|V|+|E|)$ , so the full test is $\Theta(|V|+|E|)$ . BFS’s distance-level property guarantees the alternating colour assignment is correct: vertices at the same BFS level cannot be adjacent in a bipartite graph.

Worked example: 4-cycle: $V = \{1,2,3,4\}$ , $E = \{\{1,2\}, \{2,3\}, \{3,4\}, \{4,1\}\}$ . BFS from 1: dist(1)=0 (BLACK), dist(2)=dist(4)=1 (RED), dist(3)=2 (BLACK). No conflict — bipartite with $L=\{1,3\}$ , $R=\{2,4\}$ .

Worked non-example: Triangle $K_3$ : $V=\{1,2,3\}$ , $E=\{\{1,2\},\{2,3\},\{3,1\}\}$ . BFS from 1: dist(1)=0 (BLACK), dist(2)=dist(3)=1 (RED). Edge $\{2,3\}$ connects two RED vertices — conflict, not bipartite.

Applications: Matching problems (assigning students to rooms, workers to tasks) are modelled as bipartite graphs. Maximum bipartite matching reduces to a max-flow problem and can be solved with Ford-Fulkerson or Hopcroft-Karp.

Complete Graphs

The complete graph $K_n$ has all $\binom{n}{2}$ possible edges; every vertex has degree $n-1$ . $K_n$ is $(n-1)$ -regular. A clique is any complete induced subgraph.

Trees (Detailed)

For an undirected graph on $n$ vertices, the following are equivalent definitions of a tree:

Connected and acyclic.
Connected and has exactly $n-1$ edges.
Acyclic and has exactly $n-1$ edges.
Between any two vertices, exactly one simple path exists.
Maximally acyclic: adding any edge creates exactly one cycle.
Minimally connected: removing any edge disconnects the graph.

Every tree with $n \ge 2$ has at least two leaves (vertices of degree 1). A rooted tree designates one vertex as root; parent and child relationships emerge from distances to the root. The depth of a vertex is its distance from the root. A binary tree restricts each vertex to at most two children. Every tree is bipartite (alternate levels).

Transpose, Complement, and Square

Transpose $G^T$ : reverses all edges. $(u,v) \in E \iff (v,u) \in E^T$ . Essential for Kosaraju’s algorithm.
Complement $\overline{G}$ : same vertices, $(u,v) \in E(\overline{G})$ iff $(u,v) \notin E(G)$ . A clique in $G$ is an independent set in $\overline{G}$ .
Square $G^2$ : edge $(u,v)$ exists iff a path of length $\le 2$ connects them in $G$ .

Summary

Graph Class	Key Property	Detection Time
DAG	No directed cycles; $\ge 1$ source and sink	$\Theta(V+E)$ (DFS)
Bipartite	No odd cycles; 2-colourable	$\Theta(V+E)$ (BFS)
Complete $K_n$	All $\binom{n}{2}$ edges present	$O(1)$ (check degrees)
Tree	$\lvert E \rvert = \lvert V \rvert - 1$ , connected and acyclic	$\Theta(V+E)$ (DFS/BFS)
Forest	Disjoint union of trees	$\Theta(V+E)$

Property	DAG	General digraph
SSSP time	$\Theta(V+E)$	$O((V+E)\log V)$ / $O(VE)$
Longest path	$\Theta(V+E)$	NP-hard
Topological sort	Always exists	Only if acyclic

Past paper questions: y2026p1q10 (DAG, topological sort, transitive closure for DAGs), y2025p1q9(b)(i) (connected components labelling).