Graph
Basic Definitions and Applications
Undirected Graphs
Undirected graph. G = (V, E)
- V = nodes.
- E = edges between pairs of nodes.
- Captures pairwise relationship between objects.
- Graph size parameters: n = |V|, m = |E|.
Directed Graphs
Graph Representation
Adjacency matrix - 邻接矩阵
n-by-n matrix with $A_{uv} = 1$ if (u, v) is an edge.
- Two representations of each edge.
- Space proportional to $n^2$.
- Checking if (u, v) is an edge takes $\Theta(1)$ time.
- Identifying all edges takes $\Theta(n^2)$ time
Adjacency List - 邻接表
Adjacency list. Node indexed array of lists.
- Two representations of each edge.
- Space proportional to m + n.
- Checking if (u, v) is an edge takes $O(deg(u))$ time.
- Identifying all edges takes $\Theta(m + n)$ time
离散数学中图论部分补充的 关联矩阵
Definition
Paths and Connectivity
Path:
A path in an undirected graph G = (V, E) is a sequence P of nodes $v_1, v_2, …, v_{k-1}, v_k$ with the property that each consecutive pair $v_i, v_{i+1}$ is joined by an edge in E.
simple path:
A path is simple if all nodes are distinct.
没有回路,每个顶点只经过一次
connected:
An undirected graph is connected if for every pair of nodes u and v, there is a path between u and v.
Cycles:
A cycle is a path $v_1, v_2, …, v_{k-1}, v_k$ in which $v_1 = v_k, k > 2$, and thef irst k-1 nodes are all distinct.
Tree
An undirected graph is a tree if it is connected and does not contain a cycle.
Theorem. Let G be an undirected graph on n nodes. Any two of the following statements imply the third.
- G is connected.
- G does not contain a cycle.
- G has n-1 edges.
Rooted tree:
Given a tree T, choose a root node r and orient each edge away from r.
Algorithm
Connectivity in Undirected Graph
- s-t connectivity problem
Given two node s and t, is there a path between s and t?
- s-t shortest path problem
Given two node s and t, what is the length of the shortest path between s and t?
Connectivity in Directed Graphs
- Directed reachability
Given a node s, find all nodes reachable from s
- Directed s-t shortest path problem
Given two node s and t, what is the length of the shortest path between s and t?
- Graph search
BFS extends naturally to directed graphs.
Strong Connectivity
- mutually reachable:
Node u and v are mutually reachable if there is a path from u to v and also a path from v to u.
- strongly connected :
A graph is strongly connected if every pair of nodes is mutually reachable.
Lemma. Let s be any node. G is strongly connected iff every node is reachable from s, and s is reachable from every node
- Pf. Follows from definition.
- Pf. Path from u to v: concatenate u-s path with s-v path.Path from v to u: concatenate v-s path with s-u path.
Topological Ordering
- Def. A topological order of a directed graph G = (V, E) is an ordering of its nodes as $v_1, v_2, …, v_n$so that for every edge $(v_i, v_j)$ we have i < j.
- Lemma. If G has a topological order, then G is a DAG.
DAGs (Directed Acyclic Graphs) 有向无环图
Def. An DAG is a directed graph that contains no directed cycles
Ex. Precedence constraints: edge $(v_i, v_j)$ means $v_i$ must precede $v_j$.
Lemma. If G has a topological order, then G is a DAG.
Pf. (by contradiction)
- Suppose that G has a topological order $v_1, …, v_n$ and that G also has a directed cycle C. Let's see what happens.
- Let $v_i$ be the lowest-indexed node in C, and let $v_j$ be the node just before $v_i$; thus $(v_j, v_i)$ is an edge.
- By our choice of i, we have i < j.
- On the other hand, since $(v_j, v_i)$ is an edge and $v_1, …, v_n$is a topological order, we must have j < i, a contradiction.

Lemma. If G is a DAG, then G has a node with no incoming edges.
Pf. (by contradiction)
- Suppose that G is a DAG and every node has at least one incomingedge. Let's see what happens.
- Pick any node v, and begin following edges backward from v. Since vhas at least one incoming edge (u, v) we can walk backward to u.
- Then, since u has at least one incoming edge (x, u), we can walkbackward to x.
- Repeat until we visit a node, say w, twice.
- Let C denote the sequence of nodes encountered between successive visits to w. C is a cycle.

Lemma. If G is a DAG, then G has a topological ordering.
Pf. (by induction on n)
- Base case: true if n = 1.
- Given DAG on n > 1 nodes, find a node v with no incoming edges.
- G - { v } is a DAG, since deleting v cannot create cycles.
- By inductive hypothesis, G - { v } has a topological ordering.
- Place v first in topological ordering; then append nodes of G - { v } in topological order. This is valid since v has no incoming edges. ▪
不断地添加入度为0的节点并删除即可
Breadth First Search
Theorem: For each i
, $L_i$ consists of all nodes at distance exactly i
from s
. There is a path from s to t
iff t
appears in some layer
Property. Let T be a BFS tree of G = (V, E), and let (x, y) be an edge of G. Then the level of x and y differ by at most 1.
L0 = {s}.
L1 = all neighbors of L0
L2 = all nodes that do not belong to L0 or L1, and that have an edge to a node in L1
Li+1 = all nodes that do not belong to an earlier layer, and that have an edge to a node in Li
Analysis:
- The above implementation of BFS runs in $O(m + n)$ time if the graph is given by its adjacency representation.
Pf.
Easy to prove O(n2) running time:
- at most n lists L[i]
- each node occurs on at most one list; for loop runs n times
- when we consider node u, there are <= n incident edges (u, v), and we spend O(1) processing each edge
Actually runs in O(m + n) time:
- when we consider node u, there are deg(u) incident edges (u, v)
- total time processing edges is $\sum_{u∈V}deg(u) = 2m$
Connected Component
Find all nodes reachable from s.
R will consist of nodes to which S has a path
Initially R = {s}
While there is an edge (u, v) where u∈R and v∉R
Add v to R
Endwhile
Theorem. Upon termination, R is the connected component containing s.
- BFS = explore in order of distance from s.
- DFS = explore in a different way
无向图的联通分量及并查集,
有向图的强连通分量需要更多的算法思考
包括图的翻转等,可以参考 DSAA
Bipartite Graphs
Def: An undirected graph G = (V, E) is bipartite if the nodes can be colored red or blue such that every edge has one red and one blue end.
二分图,可以使用两种颜色完成染色,匹配问题
Applications:
- Stable marriage: men = red, women = blue.
- Scheduling: machines = red, jobs = blue.
Benefits:
If a giving graph is bipartite, then Many graph problems become
- easier if the underlying graph is bipartite (matching)
- tractable if the underlying graph is bipartite (independent set)
Lemma. If a graph G is bipartite, it cannot contain an odd length cycle.
Pf. Not possible to 2-color the odd cycle, let alone G.
Lemma. Let G be a connected graph, and let $L_0, …, L_k$ be the layersproduced by BFS starting at node s
. Exactly one of the following holds.
- (i) No edge of G joins two nodes of the same layer, and G is bipartite.
- (ii) An edge of G joins two nodes of the same layer, and G contains an odd-length cycle (and hence is not bipartite).
使用 BFS 检测二分,可结合下图理解

Pf. (1)
- Suppose no edge joins two nodes on same layer.
- By previous property on page 19, this implies every edge join two nodes in adjacent layers.
- Give nodes on odd levels = red, nodes on even levels = blue -> Bipartition.
Pf. (ii)
Suppose (x, y) is an edge with x, y in same level $L_j$.
Let $z = lca(x, y)$ = lowest common ancestor.
Let Li be level containing z.
Consider cycle that takes edge from x to y, then path from y to z, then path from z to x.
Its length is 1 + (j-i) + (j-i), which is odd.
(x, y) y->z z->x


Corollary. A graph G is bipartite iff it contain no odd length cycle.
Strong Connectivity
Theorem: Can determine if G is strongly connected in $O(m + n)$ time.
Pf.
- Pick any node s.
- Run BFS from s in G. ($O(m+n)$)
- Run BFS from s in $G^{rev}$. (s->v $G^{rev}$ become v->s in G)
- Return true iff all nodes reached in both BFS executions.
- Correctness follows immediately from previous lemma.
Tpological ordering.
不断地添加入度为0的节点,并从图中删除该节点及与它相连的边即可
The algorithm finds a topological order in $O(m + n)$ time.
Pf.
- Maintain the following information:
- count[w] = remaining number of incoming edges
- S = set of remaining nodes with no incoming edges
- Initialization: O(m + n) via single scan through graph.
- Update: to delete v
- remove v from S
- decrement count[w] for all edges from v to w, and add w to S if count[w] hits 0
- this is O(1) per edge ▪
Dijkstra's Shortest Path Algorithm
略
每次添加 能够到已经遍历过节点的最近节点即可