## Basic Definition and Application

- 有向图与无向图
- 图的表示
- 邻接矩阵
- 查看二点间是否有边很方便， $\Theta(1)$
- 遍历复杂度较高, $\Theta(n^2)$

- 邻接表
- 利于稀疏图
- 遍历复杂度 $\Theta(m+n)$， m个结点，n条边
- 检查(u,v)是否为边， O(deg(u))，检查与u相邻的边

- 邻接矩阵

- Paths and Connectivity
- Def. A path in an undirected graph G = (V, E) is a sequence P of nodes v1 , v2 , …, v(k-1) , vk with the property that each consecutive pair vi , v(i+1) is joined by an edge in E.
- Def. simple path: 路径上结点不重复
- Def. connected graph: 任意两个结点间都存在路径

- Cycles
- Def. cycle: a path (v1,v2…vk)，前k-1个结点不重复

- Tree
- Def: 不含cycle的无向图
- Theorem
- connected
- no cycle
- n-1 edges (n is number of nodes)

- Rooted tree. Given a tree T, choose a root node r and orient each edge away from r.

## Graph Traversal

- s-t connectivity problem 连通性问题
- s-t shortest path problem 最短路径问题
- Applications
- Maze traversal.
- Fewest number of hops in a communication network.
- Driving direction in Google Maps

### Breadth First Search

- Algorithm
- 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 .
- L(i+1) = all nodes that do not belong to an earlier layer, and that have

an edge to a node in Li .

- Theorem. For each i, Li 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 (x, y) be an edge of G. Then the level of x and y differ by at most 1.

### Depth First Search

- 走到底再回溯

### BFS/DFS Analysis

- O(m+n) 邻接表存储
- Pf.
- 初始化 访问O(n)
- 访问一条边 deg(u)，每条边访问两次
- 总访问时间 sum(deg(u)) = 2m

- BFS/DFS也可以用于查找Connected Component，连通分支

## Testing Bipartiteness

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

- Testing bipartiteness
- 给定一个图，判断是否是二分图
- 若给定图是二分图，很多图的相关问题会变得更简单

- independent set: 多项式时间算法

### Lemma

- 二布图不含奇数长度的环（充分必要
- BFS时，以下命题仅一个发生
- (i) 没有一条边连接同一层的两个结点，为二布图
- (ii) 同一层的两个结点中至少一条边，含奇数长度的环，不为二布图

- Pf. (i)
- Suppose no edge joins two nodes in the same layer.
- Bipartition: red = nodes on odd levels, blue = nodes on even levels.

- Pf. (ii)
- Suppose (x, y) is an edge with x, y in same level L j .
- Let z be lowest common ancestor of x, y in BFS tree.
- Let L i 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.

## Connectivity in Directed Graph

- Directed reachability
- Directed s-t shortest path problem
- Graph search
- Web crawler
- Strong Connectivity
- Def. mutually reachable. u->v and v->u
- Def. 任意两个结点都可相互抵达，则strong connectivity

- Lemma. Let s be any node. G is strongly connected iff every node is reachable from s, and s is reachable from every node.

### Strong Connectivity: Algorithm

- Theorem. Can determine if G is strongly connected in O(m + n) time.
- Pick any node s.
- Run BFS from s in G.
- Run BFS from s in Grev(reverse orientation of every edge in G).
- Return true iff all nodes reached in both BFS executions.
- Correctness follows immediately from previous lemma.

## DAGs and Topological Ordering

- Directed Acyclic Graphs
- 有向无环图
- 拓扑序列: A topological order of a directed graph G = (V, E) is an ordering of its nodes as v1 , v2 , …, vn so that for every edge (vi , vj) we have i < j.
- Applications of Precedence Constraints
- Edge (vi , vj) means task vi must occur before vj .
- 课程先修图, course vi must be taken before vj .
- 编译顺序, module vi must be compiled before vj .
- Pipeline of computing jobs, output of job vi needed to determine input of job vj.

### Lemma

- Lemma1: 若一张图有拓扑排序，则为DAG（充分必要）。证明如下：
- Suppose that G has a topological order v1 , …, vn 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 vj be the node just before vi; thus (vj , vi) is an edge.
- By our choice of i, we have i < j.
- On the other hand, since (vj , vi) is an edge and v1 , …, vn is a topological order, we must have j < i, a contradiction.

- Lemma2: DAG中存在一个结点，没有边指向它。证明如下:
- 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.

- Lemma3: 若一张图为DAG，则有拓扑排序。证明如下：
- 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.
- (即不断删除没有边指向的点)

### Running Time

- Theorem. 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

- count[w] = remaining number of 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

- Maintain the following information: