A graph models objects and the relationships relevant to a question. In this chapter, a simple undirected graph is finite, has no loops, and has no multiple edges. A drawing can change without changing the graph: only its vertices and edges matter.
Key ideas & formulas
Definitions · rules · complexity
01
G = (V, E) · n = |V| (order) · m = |E| (size)
02
Simple undirected graph: E ⊆ {{u, v} : u, v ∈ V, u ≠ v}
03
u and v are adjacent ⇔ uv ∈ E
04
N(v) = {u ∈ V : uv ∈ E} · N[v] = N(v) ∪ {v}
05
H = (W, F) ⊆ G ⇔ W ⊆ V and F ⊆ E
06
G[W]: induced subgraph containing every edge between vertices in W
02
Topic 1.2
Representations and complexity
An edge list, adjacency lists, and an adjacency matrix represent the same graph. Choose according to memory limits and the operations you use most.
Key ideas & formulas
Definitions · rules · complexity
01
Edge list: space Θ(m) · test uv: O(m) · list N(u): O(m)
02
Adjacency lists: space Θ(n + m) · test uv: O(d(u)) · list N(u): Θ(d(u))
03
Matrix A: space Θ(n²) · test uv: O(1) · list N(u): Θ(n) · list E: Θ(n²)
04
Simple undirected graph: A[u,v] = A[v,u] and A[u,u] = 0
05
Simple graph: m ≤ n(n − 1)/2
06
f=O(g) ⇔ ∃C,n₀>0, ∀n≥n₀: f(n)≤Cg(n)
07
f=Ω(g) ⇔ ∃c,n₀>0, ∀n≥n₀: cg(n)≤f(n)
08
f=Θ(g) ⇔ ∃c,C,n₀>0, ∀n≥n₀: cg(n)≤f(n)≤Cg(n)
03
Topic 1.3
Degrees and double counting
The degree of a vertex is its number of neighbors. The handshaking lemma counts vertex-edge incidences once by vertices and once by edges.
Complete graph Kₙ: d(v) = n − 1 and m = n(n − 1)/2
04
Topic 1.4
Connectivity and the Components algorithm
A graph is connected if every pair of vertices is joined by a path. Connected components are the maximal connected vertex sets and partition the vertices.
Key ideas & formulas
Definitions · rules · complexity
01
V = C₁ ⊎ C₂ ⊎ … ⊎ Cₖ
02
With exactly k components: m ≤ (n − k + 1)(n − k)/2
03
comp[x] = comp[y] ⇔ x and y belong to the same component
04
Components: initialize comp[x] ← x; for each xy, merge labels if they differ
05
Time: O(m + n²) · auxiliary space: Θ(n) · at most n − 1 merges
