# 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 incoming

edge. Let's see what happens. - Pick any node v, and begin following edges backward from v. Since v

has 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 walk

backward 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 layers

produced 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

略

每次添加 能够到已经遍历过节点的最近节点即可