---
tags: Algorithms, Algorithms - 交大江蕙如
---

# Algorithms Chapter 3 Graphs (3/4) - 交大江蕙如

## Video
- [Lec08 演算法 第四週課程 (2/2)](交大OCW網址)

## Content

[TOC]

### Summary: Implementation

- traverse the graph: 透過 explore adjacency list/matrix 來畫出整張圖
- adjacency list: $O(n+m)$
- adjacency matrix: $O(n^2)$
- storage for dense graph
- adjacency list: edge list 需要的 space 是 edge 數的兩倍
- adjacency matrix: $O(n^2)$ 雖然 order 是一樣的，不過仍然小贏 adjacency list

## Testing Bipartiteness - Application of BFS

### Bipartite Graphs
- $G = (X, Y, E)$
- $X, Y$ are disjoint sets
- $E$: edges
- edge 只會在不同的 set 之間互連
- bipartite graphs 中文為 **二分圖**


### Is a Graph Bipartite?
- 判斷是否 bipartite 其實等同於著色問題
- bipartite $\leftrightarrow$ edge 兩邊必定不同顏色

- 如果 $G$ 是 bipartite，則裡面不會存在 odd-length cycle (這是可以證明的)
- 像圖上的 3-node cycle 就是 odd cycle 的最簡單的形式
- > Q: ***如何證明 存在 odd cycle 就不是 bipartite graph??***
- 大概是歸納法，若 n-length cycle 成立則 (n+2)-length cycle 也一定成立
- > Q: ***不對啊好像應該是要證明 bipartite graph 必不存在 odd cycle 吧***
- > Q: ***所以能不能利用 顏色的方式來證明啊，還是說也要先證明 testing bipartite 等同於 two-coloring??***
- > Q: ***是的話要怎麼證 testing bipartite 等價於 two-coloring???***

### Testing Bipartiteness
- BFS + 著色/check顏色 即可
- 假設 $L_0$ 塗紅色，那 $L_1$ 「尚未著色」的 neighbor 就要塗藍色，依此類推
- 每個 node 的 next layer neighbor 要塗色，last layer neighbor (uncle) 要 check 顏色 (next layer 的 painted neighbor 也要 check 顏色)
- 反正就用 BFS 檢查 neighbor，尚未著色就著色；以著色就 check


### Implementation: Testing Bipartiteness

- 只要在 BFS 加上 著色的動作即可
- > Q: ***有這麼簡單ㄇ@@???***


### Proof: Correctness (1/2)
- 【注意】我們之前證明過 BFS 的 nontree edge 的 layer index 差距會小於等於 1，(而 tree edge 也只會跨一層)因此任何 edge $(x,y)\in E$ 的 layer index $i,j$ 差距都不大於 1。
- case 1: 沒有 edge 會連接相同的 (BFS) layer，$G$ is bipartite
- 左圖 (bipartite)
- 這裡要證明就很 trivial，因為既然沒有 edge 是在同一層，那就代表所有 edge 都恰好跨一層，跨一層的 edge 本來就會著不同顏色，因此 two coloring 必定成功，trivial。
- case 2: 有 edge 連接相同的 (BFS) layer，$G$ 有 odd-length cycle (因此 $G$ is not bipartite)
- 右圖 (有 odd cycle)
- 證明見下頁

### Proof: Correctness (2/2)
- 假設 $x,y$ 往 root 走的時候最早會在 node $z$ 匯集
- 所以 【$(x,z)$ 和 $(y,z)$ (長度相等)】 和 【$(x,y)$(長度為1)】 就構成了一個 odd cycle 啦

延伸問題諸如 3-coloring 的問題，是 np-complete 的問題
- 3-coloring 就是每次從3種顏色挑一種，一樣要保持 edge 兩端不同顏色
- 要保持 edge 兩端不同顏色的這種問題就叫 coloring problem
- 這類問題在 EE 領域最近很常見

## Connectivity in Directed Graphs
- 要確定兩個方向都存在 path，才能說兩點是 connected

### Recap: Directed Graphs

- adjacency list
- 可能會存 incoming / outgoing 兩個 list
- 考慮方向性之後，右下這張就不是 connected 了

### Strong Connectivity
- 在 directed graph 中，兩點 $u,v$ 互相都有 path 可以到達對方，則稱為 **mutually reachable**
- 若 directed graph 中，任意兩點之間都是 mutually reachable，我們才稱該 graph 有 **strong connectivity**
- 雖然很難要求 graph 有 strong connectivity，但是我們可以切割 graph 使得每個 sub graph 都有 strong connectivity 的特性，也就是 **strongly connected component**。
- 【重要】Lemma
- **if $(u,v)$ mutually reachable, and $(v,w)$ mutually reachable, then $(u,w)$ mutually reachable**
- **strongly connected component 也一樣必須是 maximum set**


### Testing Strong Connectivity
- 能不能在 linear time $O(n+m)$ check strong connectivity?
- 可以，直接做兩次 BFS
- 第一次在 $G$ 上檢查某個 node $s$ 是否能 reach 所有 point (用 BFS)
- 第二次在 $G^{rev}$ 檢查同個 node $s$ 是否能 reach 所有 point (用 BFS)
- 其實就是在檢查本來的 $G$ 是否所有 node 都能 reach 到 $s$
- 太神啦！！！

- > Q: ***Correctness 可能要思考一下要證明的東西&證法***
- Q: How to partition a directed graph into strongly connected components?
- 改天來想
- 老師表示，概念上可以用兩次 BFS 做到；也可以用兩次 DFS 做到，因此也可以 linear time。