# Graph
圖論在計算機領域中佔有非常重要的一個地位
現在考研發現包刮離散、演算法、資結甚至OS都會用到
做一篇大統整
## 表示法
1. Adj Matrix
強連通圖的Adj Matrix為symmetric
邊數多的時候適合
2. Adj List
邊數少的時候適合
## 圖的種類及術語
* 分為有向圖及無向圖，$\{a,b\}=\{(a,b),(b,a)\}$，每個無向邊可視為兩個有向邊的集合
* multigraph: 存在$a,b\in V$使得a,b之間至少兩個邊，兩個點之間的邊數稱為重數multiplicity，邊集合會是multiset(有重複元素)
**基本術語**
| 名詞 | 定義 | 備註 |
| ----------- | -------------------------- | ---- |
| walk 路 | 從$v_i$到$v_j$經過的點集合 | |
| closed walk | 起點終點相同的walk | |
| trail 路線 | **不含重複邊**的walk | |
| path 路徑 | **不含重複點**的walk | 不含重複點就不會含重複邊，所以path也會是trail |
| circuit 迴路 | closed trail | 至少含一點 |
| cycle環路 | closed path | 至少含三點，cycle也會是circuit |
* $2*|E|=\sum_{i=0}^{n-1}deg(v_i)$
* 計算有向圖的in degree和out degree
利用adj list，$\Theta(n^2)$
利用adj matrix，$\Theta(n^2)$
```c=
//Adj list
Out_Deg(G){
for each u in G.V
u.out_deg=0
for each v in G.Adj[u]
u.out_deg+=1
}
In_Deg(G){
for each u in G.V
u.in_deg=0
for each u in G.V
for each v in G.Adj[u]
v.in_deg+=1
}
//Adj matrix,n是點的數量
Out_Deg(G,n){
for each u in G.V
u.out_deg=0;
for(int i=0;i<n;i++)
if(G.AdjM[u.id][i])
u.out_deg+=1;
}
In_Deg(G,n){
for each u in G.V
u.in_deg=0;
for(int i=0;i<n;i++)
if(G.AdjM[i][u.id])
u.in_deg+=1;
}
```
* 對任意無向圖，奇數點的點數必有偶數個
* 對於有向圖來說，$\sum_{v\in V}InDeg(v)=\sum_{v\in V}OutDeg(v)$ (因為in degree和out degree成對出現)
$2*|E|=\sum_{v\in V}InDeg(v)+\sum_{v\in V}OutDeg(v)$
$|E|=\sum_{v\in V}InDeg(v)=\sum_{v\in V}OutDeg(v)$
* 若$G=(V,E)$為simple graph，若每個vertex度數至少2，則$G$包含一個環路
若每個vertex度數至少$k$，則$G$包含一個長度至少$k+1$的環路 (證明)
- [ ] cycle detection algorithm(using DFS)
透過DFS來偵測是否有back edge，有就代表有cycle
- [ ] deadlock avoidance algorithm
* **DAG**: directed acyclic graph， 有向且無迴圈的圖
每個DAG都一定有自己的Topological sorting(不一定唯一)
```c=
Topological_Sort(G){
DFS(G);//compute finish time v.finish for every vertex
當vertex完成搜尋時(產生v.finish)，把它插入到linked list的最前方
return LList; //如果回傳的list length不等於|G.V|，代表此圖不是DAG
}
```
### 連通圖
| 名詞 | 定義 | 備註 |
| -------- | -------- | -------- |
| Connected Graph| (無向圖)$\forall x,y\in V,x\neq y$，存在由$x$到$y$的path | 連通圖: $\kappa(G)=1$，不連通圖: $\kappa(G)\ge 2$ |
| Strongly Connected Graph 強連通圖| (有向圖) 任意兩點間都存在有向path能互相到達| 邊數一定是偶數 |
| Unilaterally Connected Graph 單方向連通圖 | (有向圖) 任意兩點間存在path能從一點到另一點 | 強連通圖一定是單方向連通圖 |
| Weakly Connected Graph 弱連通圖 | 把有向圖的邊全部換成無向之後會是連通圖 | 把有向圖的邊全部換成無向之後會是連通圖，單方向連通圖必為弱連通圖，所以強連通圖也必為弱連通圖 |
|Strictly unilaterally connected Graph 嚴格單方向連通圖| 單方向連通圖但不為強連通圖 ||
|Strictly weakly connected graph 嚴格弱連通圖| 弱連通圖但不為單方向連通圖 | |
* 假設$|V|=n$，則滿足$G$為connected的最少邊數為$n-1$，同時也是一顆tree，所以一個graph的spanning tree會是一個graph的minimal connected subgraph
* 若$G=(V,E)$為一個undirected connected graph且$|V|\ge 1$，則$|E|\ge |V|-1$
* 假設$A$為$G$的adj matrix，則$A^r$的第$i,j$項為$v_i$到$v_j$長度為$r$的path的個數
* **找Strongly connected component的算法**
做兩次DFS
*把第二次得出的每個SCC當成一個node，cross edge當成邊，可以得到一個DAG*
```c=
SCC(G){
DFS(G);//compute v.finish
G.T = Transpose(G);
DFS(G.T); //按照第一次DFS算出的finish time的decreasing order來造訪G.V
//在第二次DFS中，每次產生的一個tree都是一個SCC
}
```
* 假設一個圖中有兩個SCC，C、C'，那$f(C)>f(C')$或$f(C')>f(C)$兩者必有一個成立，也就是其中一個SCC的vertexs的finish time一定都大於另一個SCC的finish time (證明)
<img src="https://i.imgur.com/JIiZt4p.png">
### 子圖 subgraph
原圖為$G=(V,E)$
| 名詞 | 定義 | 備註 |
| -------- | -------- | -------- |
| Subgraph | $G'=(V',E')$滿足 $\emptyset \neq V'\subseteq V$且$E'\subseteq E\bigcap (V'\times V')$| |
| 誘導子圖 | $E'=E\bigcap (V'\times V')$ | induced subgraph on $V'$ |
| 生成子圖 | $V'=V$ | spanning subgraph |
|分量圖| $G_1=(V_1,E_1)$為$G$的誘導子圖且不存在$G$的另一個誘導子圖$G_2=(V_2,E_2)$使得$V_1\subset V_2$ | $G$的分量圖個數記做$\kappa(G)$ |
- [ ] connected component algorithm
- [ ] DAG
- [ ] Topological sorting
* 圖的聯集
$G_1,G_2$為兩個無向簡單圖，$G_1\bigcup G_2=(V_1\bigcup V_2,E_1\bigcup E_2)$
* $G-v$表示去除掉點$v$還有和$v$相連的邊
$G-e$表示去掉邊$e$就好
| 名稱 | 定義 | 備註 |
| -------- | -------- | -------- |
| 切點 | $v\in V$滿足$G_1=(V-\{v\},E_1)$使得$G_1$為不連通圖 | cut point、articulation point |
| 切集 | 邊集$E_1\subseteq E$滿足$G_1=(V,E-E_1)$使得$G_1$為不連通圖，並且去掉任何$E_2\subset E_1$形成的$G_2=(V,E-E_2)$依然是連通圖 | cut set，切集不能縮小，放大之後只能說這個邊集和包含切集 |
| 切邊、橋 | 邊$e$形成切集$E_1=\{e\}$ | cut edge、bridge |
| 雙連通圖 | 一個loop free的連通無向圖且不含切點 | biconnected graph |
| 雙連通分量圖 | 一個loop free的連通無向圖可能有切點，$G$中的極大雙連通誘導子圖稱為雙連通分量圖 | biconnected component |
| 完全圖 complete graph | $K_n=(V,E)$，$\|V\|=n$，圖中任兩相異點恰有一邊相連 | $\|E\|=\dbinom{n}{2}$ |
| 有向完全圖 direct complete graph、complete tournament | 有向圖$K_n^*$ 中相異兩點$x,y$滿足$(x,y),(y,x)$洽有一邊在$G$ | 邊數為$\dbinom{n}{2}$，$K_n^*$並不唯一 |
| 雙分圖 | $G=(V,E)=(V_1\bigcup V_2,E)$， $V=V_1\bigcup V_2$ 且 $\emptyset=V_1\bigcap V_2$ | bipartite graph |
| 完全雙分圖 | 雙分圖$K_{m,n}$滿足$\|V_1\|=m,\|V_2\|=N,\forall x\in V_1,y\in V_2,\{x,y\}\in E$ | $\|E\|=mn$ |
* Biconnected Graph只有一個Biconnected component，也就是它自己
* $G$當中的兩個biconnected component頂多只會共享一個vertex，且不會共享任何邊
換言之，biconnected component會把$G$的edges給切分開
expample: $G=(V,E)$的兩個biconnected component $G_1=(V_1,E_1),G_2=(V_2,E_2)$，滿足$V_1\bigcap V_2=\{e\},E_1\bigcap E_2=\emptyset$，其中$e$為articulation point
* **怎麼找articulation point?**
先對一個graph做DFS並算出每個點的DFS number $dfn$，同時計算每個點的$low(v)$值
$low(v)$代表$v$透過自己、或自己的descendants，頂多一條back edge，能接觸到的最小$dfn$
能遞迴定義如下
$low(v)=min\{dfn(v), min\{low(x)| x.p=v\}, min\{dfn(x)|dfn(x)<dfn(v)\}\}$
情況一: root是articulation point若且唯若它有兩個以上的child(直接連接的那種)
情況二: 不為root的node $v$，若且唯若它至少有一個child $w$使得$low(w)\ge dfn(v)$
* $G$為bipartite graph $\Leftrightarrow$ $G$中不具有奇數長度的環路
<img src="https://i.imgur.com/H7nRz7R.png">
* **特殊圖**
| 名詞 | 定義 | 備註 |
| -------- | -------- | -------- |
| 規則圖 | k-regular graph，每個點的degree都是k ||
| $P_n$ | n個點的path | |
| $C_n$ | n個點的cycle ||
| $W_n$ | wheel graph，在$C_n$中加入一個新的點與$C_n$中每個點加上n個新的邊 ||
| $Q_n$ | hypercube，每個點以n個位元來表示，兩個點相鄰的條件為兩個點恰有一個位元不同，$\|V\|=2^n$，$Q_n$可由$Q_{n-1}$遞迴建構而成 | 為n-規則圖，每個點degree皆為n |
## 圖的同構
* Def:
假設$G_1=(V_1,E_1),G_2=(V_2,E_2)$為兩個simple graph，若存在一個函數$f:V_1\rightarrow V_2$滿足以下兩點，則$f$稱為isomorphism且$G_1\cong G_2$
1. $f$為one-to-one且onto function
2. $\forall a,b\in V_1,(a,b)\in E_1\Leftrightarrow (f(a),f(b))\in E_2$
若為multi graph，則還要加上每個邊的重數相同
* *同構的觀念就是重畫*
* **Graph invariant** (可用來判斷兩圖不同構，任一者不成立，即為不同構)
1. 兩圖頂點數相同
2. 兩圖邊數相同
3. 兩圖度數序列相同
4. 有相同子圖
5. 對應點距離相同
6. 對應點的連結性相同
## 圖的性質
* 對任意無向簡單圖或多重圖，奇數度數的點數必有偶數個
* maximal path: P為一條路徑且P不會包含於一個更長的路徑(即便如此，P未必是此圖中最長的路徑)
找最長路徑為NP-Complete的問題
* $G=(V,E)$為一個無向簡單圖，若$G$中每個點的度數至少k，則$G$包含一個長度至少$k+1$的環路
* $A$為一個adj matrix，$A^r$的第$(i,j)$項表示$v_i$到$v_j$長度為$r$的path的個數
* $G$為雙分圖 $\Leftrightarrow$ $G$中不具奇數長度的環路
## Graph Searching Algorithm
1. **DFS**
```c=
//recursive version
int t;
DFS(G){
for v in G.V
v.color = white;
v.parent = null;
v.start = INF; // this is also dfn
v.finish = INF;
t=0;
for v in G.V
if v.color == white
DFS_visit(G,v);
}
DFS_visit(G,u){
t += 1;
u.color = gray;
u.start = t;
for v in G.Adj[u]
if v.color == white
v.parent = u;
DFS_visit(G,v);
else if v.color == gray
print("back edge");
else if v.color == black
print("cross edge or forward edge");
u.color = black;
t += 1;
u.finish = t;
}
//iterative version
DFS(G,root){
Stack s;//init an empty stack
for v in G.V
v.parent = Null;
v.visit = false;
v.dfn = INF;
v.end = INF;
int t=0;
s.push(root);
while(!s.empty()){
t +=1;
u = s.top();
if(u.visit){
s.pop();
u.end = t;
continue;
}
u.visit = true;
u.dfn = t;
for v in G.Adj[u]
if !v.visit
v.parent = u;
s.push(v);
}
}
```
2. **BFS**
```c=
BFS(G,root){
for v in G.V
v.parent = NULL;
v.visit = false;
Queue q; //init an empty queue
q.push(root);
while(!q.empty()){
u = q.top();
q.pop();
u.visit = true;
for v in G.Adj[u]
if !v.visit
v.parent = u;
q.push(v);
}
}
```
3. **Best First Search**
* 不使用普通的queue或stack，使用priority queue，過程跟BFS有點相似，但換成使用priority queue，priority可以用邊的權重表示或者點的權重
```c=
Best_FS(G,root,goal){
for v in G.V
v.parent = NULL;
v.visit = false;
Priority_Queue pq; //init an empty queue
pq.push(root);
root.visit = true;
while(!pq.empty()){
u = pq.top();
pq.pop();
if(u == goal)
return;
for v in G.Adj[u]
if !v.visit
v.parent = u;
v.visit = true;
pq.push(v);
}
}
```
## Minimum Spanning Tree
* 問題描述: 若給一個連通圖上的每個邊weight，如何得到此圖具有最小weight的spanning tree?
* 暴力法: 最糟情況若此圖有n(n-1)條邊，則可能的spanning tree有$\dbinom{n^2-n}{n}$種可能
* 思考: 如果我們已經有此圖的MST的子集，A，要怎麼挑選edge加入A才能保證$A\bigcup e$同樣也是MST的子集?
將點分為兩邊，$(V_1,V-V_1)$稱為一個cut，挑選跨越此cut上weight最小的邊，可以稱它為light edge、safe edge，將此邊加入A可以保證加入後還是MST的子集
透過不同尋找light edge的方法(不同的方法來製造cut)，可以有以下幾種找MST的算法
### Kruskal algorithm
* 做法: 每次挑選連接不同set中的edge裡，weight最輕的那個，並將兩個set合併(算法執行的時候可以有超過兩個set，數個cut存在)
一開始先將每個點都做成一個set，並把edge依照weight排序，然後重複上述步驟直到把所有edge檢查完
*會用到union、find*
```c=
Kruskal(G,w){
A=NULL;
for each v in G.V
Make_set(v);
sort(G.E,w);//將edge依照weight，nondecreasing order排序
for each edge (u,v) in G.E
if Find_Set(u)!=Find_Set(v) //light edge
A = A+(u,v);
Union(u,v);
return A;
}
```
* 此算法的時間複雜度取決於我們怎麼實作set這個data structure，如果我們用disjoint set的方式，那時間複雜度可以降到$\Theta(|E|lg|V|)$
### Prim's Algorithm
* 也就是這算法做cut的方式都是$(A.V,V-A.V)$，每次選取此cut上的light edge，這是一個greedy algorithm
```c=
Prim(G,w,root){
A=NULL;
for each v in G.V
v.key = INF;
v.parent = NULL;
root.key = 0;
Queue Q = G.V;
while(!Q.empty()){
u = Q.Extract_Min();
for each v in G.Adj[u]
if v in Q and w(u,v) < v.key
v.key = w(u,v);
v.parent = u;
}
}
```
* 時間複雜度取決我們怎麼實作queue，如果使用binary min_heap，則會是$\Theta(ElgV)$，如果用Fibonacci heap，會是$\Theta(E+VlgV)$
- [ ] 經典問題: second best MST
- [ ] Bottleneck spanning tree
## Single-source Shortest Path Algorithms
* 給定一起點s，如何求得s到各點的最短路徑
* **shortest path的subpath也是shortest path**
<img src="https://i.imgur.com/cJS8KsE.png">
* 每個shortest path頂多有$|V|-1$條邊，更多的話代表有cycle，negative cycle的話shortest path length會是負無限大，而positive cycle不可能出現在shortest path裡面，0-weight cycle則是可以忽略
* shortest path spanning tree肯定也是MST嗎? 不是，有反例
* 最短路徑的算法都有以下重要特性
- **Triangle inequality**: $\forall (u,v)\in E,\delta(s,v)\le \delta(s,u)+w(u,v)$
<img src="https://i.imgur.com/ohG0BGt.png">
- **Path-relaxation property**: 如果$p=<v_0,...,v_k>$為$v_0$到$v_k$的shortest path，並且我們依照$(v_0,v_1),..,(v_i,v_{i+1}),..,(v_{k-1},v_k)$的順序relax他們，則$v_k.d=\delta(v_0,v_k)$
### Bellman-Ford Algorithm
* 可以有負邊
* 時間複雜度$\Theta(|V||E|)$
* 做$|V|-1$次迴圈是因為shortest path頂多$|V|-1$條邊，不管edge被嘗試relax的順序是如何，被成功relax的順序一定有按照$v_0,..,v_k$，最外圈第i次迴圈(有可能提前)一定會relax到$(v_{i-1},v_i)$，透過path-relaxation property知道，照順序把整個shortet path上的點都relax過的話可以確定找到shortest path
```c=
//G is graph, w is weight function, s is the source
Bellman_Ford(G,w,s){
for v in G.V
v.d=INF;
v.parent=NULL;
s.d=0;
bool relax;
for i=1:|G.V|-1
relax=false;
for each (u,v) in G.E
if v.d>u.d+w(u,v)
v.d=u.d+w(u,v);
v.parent=u;
relax = true;
if !relax
break;
for each (u,v) in G.E
if v.d>u.d+w(u,v)//negative cycle exists
return false;
return true;
}
```
* 可利用dp來做bellman-ford
$v_0=s$
$d^k[j]$表示$s$到$v_j$不走超過$k$個邊的shortest path length
$d^k[j]=\begin{cases}
w[0,j] \ \ if \ \ k=1\\
min\{d^{k-1}[j],min(d^{k-1}[i]+w[i,j])\} \ \ k>1
\end{cases}$
* 由於path relaxation property，如果我們可以按照順序relax每個邊，只需要把每個邊都relax一次就可以得出shortest path
用topological sort就可以找到這個順序(前提是此圖為DAG)
Time Complexity: $\Theta(V+E)$
```c=
DAG_Shortest_Path(G,w,s){
TopoSort(G);
Init(G,s);
for each u in G.V//now in topological sorting order
for each v in G.Adj[u]
if v.d>u.d+w(u,v)
v.d=u.d+w(u,v)
}
```
### Solving systems of difference constraints
* 一個線性系統每個長的像$x_j-x_i\le b_k$
* 思考三角不等式$\delta(v)\le \delta(u)+w(u,v)$，所以$\delta(v)-\delta(u)\le w(u,v)$，因此將每個變數看成一個vertex，並新增一個source vertex s，到各點的距離都為0，到每個點的shortest path length就會是一組解
### Dijkstra's Algorithm
* 不能有負邊
* 集合S當中的vertex的shortest path都已經確定了
* Greedy strategy
```c=
Dijkstra(G,w,s){
for each u in G.V
u.d = INF;
u.parent = NULL;
s.d = 0;
S = Init_Set(); //init an empty set
Q = Queue(G.V);
while (!Q.empty()){
u = Q.Extract_Min();
S += u;
for each v in G.Adj[u]
if(v.d>u.d+w(u,v))
v.d=u.d+w(u,v);
v.parent = u;
}
}
```
* 時間複雜度取決於我們如何實作此Min queue，用binary heap會是$\Theta(ElgV)$，用Fibonacci heap會是$\Theta(VlgV+E)$
## All pairs shortest path
* 會記錄一個predecessor matrix，$\prod=(\pi_{ij})$，$\pi_{ij}$代表i到j的shortest path上，j的predecessor
所以由這個matrix的第i個row所產生的subgraph就是以i為root的predecessor subgraph $G_{\pi,i}=(V_{\pi,i},E_{\pi,i})$，且$V_{\pi,i}=\{j\in V:\pi_{ij}\neq NIL\}\bigcup \{i\}, E_{\pi,i}=\{(\pi_{ij},j):j\in V_{\pi,i}-\{i\}\}$
### 類矩陣相乘法
* 假設$l_{ij}^{(m)}$代表i到j頂多經過m條邊的shortest path，可定義以下遞迴式
$l_{ij}^{(0)}=\begin{cases}
0 \ \ if \ \ i=j\\
\infty \ \ if \ \ i\neq j
\end{cases}$
$l_{ij}^{(m)}=min_{1\le k\le n}\{l_{ik}^{(m-1)}+w_{kj}\}$
由於shortest path頂多具有$n-1$條邊，所以可以保證$\delta(i,j)=l_{ij}^{(n-1)}=l_{ij}^{(n)}=l_{ij}^{(n+1)}=\cdots$
此算法時間複雜度是$\Theta(n^4)$，也可以透過reqeated squaring來加速讓它達到$\Theta(n^3lgn)$
```c=
//W 是weight matrix
All_pairs_shortest_path(W){
n = W.rows;
L = W;
for m = 2:n-1
for i = 1:n
for j = 1:n
for k = 1:n
L[i][j] = min(L[i][j],L[i][k]+W[k][j]);
return L;
}
Speedup(W){
n = W.rows;
L=W;
m = 1;
while m<n-1
for i = 1:n
for j = 1:n
for k = 1:n
L[i][j] = min(L[i][j],L[i][k]+L[k][j]);
m = 2*m;
return L;
}
```
### Floyd-Warshall Algorithm
* 可以有負邊，不能有負環
* 定義$d_{ij}^{(k)}$為i到j的shortest path且經過的intermediate verteices為$\{v_0,\cdots,v_k\}$，可定義以下遞迴式
$d_{ij}^{(k)}=\begin{cases}
w_{ij} \ \ if \ \ k=0\\
min(d_{ij}^{(k-1)},d_{ik}^{(k-1)}+d_{kj}^{(k-1)}) \ \ if \ \ k\ge 1
\end{cases}$
時間複雜度會是$\Theta(n^3)$
如果$d_{ii}^{(n-1)}<0$代表有負環
同時可以計算出predecessor matrix $M$，定義如下
$M_{ij}^{(0)}=\begin{cases}
NIL \ \ if \ \ i=j \ \ or \ \ w_{ij}=\infty\\
i \ \ if \ \ i\neq j \ \ and \ \ w_{ij}<\infty
\end{cases}$
$M_{ij}^{(k)}=\begin{cases}
M_{ij}^{(k-1)}\\
M_{kj}^{(k-1)}
\end{cases}$
```c=
Floyd_warshall(W){
n = W.rows;
D = W;
M={NULL};//init predecessor matrix
for i = 1:n
for j = 1:n
if i!=j && W[i][j]<INF
M[i][j]=i;
for k = 1:n
for i = 1:n
for j = 1:n
if D[i][j] > D[i][k]+D[k][j]
D[i][j] = D[i][k]+D[k][j];
M[i][j] = M[k][j];
return D;
}
```
* 可以利用此算法的概念來計算transitive closure，transitive closure $G^*=(V,E^*)$，若$(i,j)\in E^*$代表在$G$中，可以從$i$到$j$，定義$t_{ij}^{(k)}$代表從i到j經過$v_0\cdots v_k$能否到達，可定義以下遞迴式
$t_{ij}^{(0)}=\begin{cases}
0 \ \ if \ \ i\neq j \ \ and \ \ (i,j)\notin E\\
1 \ \ if \ \ i=j \ \ or \ \ (i,j) \in E
\end{cases}$
$t_{ij}^{(k)}=t_{ij}^{(k-1)}\vee (t_{ik}^{(k-1)}\wedge t_{kj}^{(k-1)})$
時間複雜度是$\Theta(n^3)$
```c=
Transitive_Closure(G){
n = G.V.size;
int T[n][n]={0};//init a matrix whose elements are all zero
for i=1:n
for j=1:n
if(i==j || (i,j) in G.E)
T[i][j]=1;
for k = 1:n
for i = 1:n
for j = 1:n
T[i][j] = T[i][j] or (T[i][k] and T[k][j]);
return T;
}
```
* 邊數較少的時候這樣做沒效率，可以直接執行$|V|$次的BFS時間複雜度會是$O(|V|(|E|+|V|))$
### Johnson's Algorithm for sparse graphs
* 重點在reweighting，剛開始給入的圖可以有負邊，透過reweighting將邊全部轉為非負，再對每個點做一次Dijkstra algorithm
* reweighting function : $\hat{w}(u,v)=w(u,v)+h(u)-h(v)$
1. 對於任意shortest path p來說，$w(p)=\delta(v_0,v_k) \Leftrightarrow \hat{w}(p)=\hat{\delta}(v_0,v_k)$
<img src="https://i.imgur.com/DtCPeZj.png">
2. $G$使用w沒有負環 iff $G$使用$\hat{w}$沒有負環
<img src="https://i.imgur.com/XM7YWgp.png">
* 如何決定$h(v)$的數值? 並讓它可以把每個edge重新做成nonnegative edge?
新增一個點$s$在圖中，並且此$w(s,v)=0,\forall v\in V$，計算出$\delta(s,v),\forall v\in V$，並讓$h(v)=\delta(s,v)$，透過triangle inequality可以知道$\delta(s,v)\le \delta(s,u)+w(u,v)$，所以$w(u,v)+\delta(s,u)-\delta(s,v)\ge 0$，所以可以定義$\hat{w}(u,v)=w(u,v)+\delta(s,u)-\delta(s,v)$
* 時間複雜度是一次Bellmand-Ford加上$|V|$次的Dijkstra所以是$\Theta(|V|^2lg|V|+|V||E|)$
```c=
Johnson(G,w){
G.V += s;//加入多的vertex s
for i = 1:|G.V|
G.E += (s,G.V[i]);
w(s,G.V[i]) = 0; //s到任意點的weight為0
if Bellman_Ford(G,w,s) == false
return "Neg cycle exists"
h[1..n];
for each v in G.V
h[v]=v.key;
for each (u,v) in G.E
w(u,v) = w(u,v)+h[u]-h[v]; //reweightin，v.key為Bellman-Ford過程中計算出的
D[0..n][0..n];
for each u in G.V
Dijkstra(G,w,u);//計算每個single source的最短路徑
for each v in V
D[u][v] = v.key + h[v] - h[u];//這裡的v.key是Dijkstra計算出的以u為source的最短路徑，reweighting
return D;
}
```
## Maximum Flow
* 問題描述: 給定一個flow network，是一個directed graph，每個邊有capacity $c(u,v)\ge 0$，且不允許self-loop，除了起點之外每個點都至少有一邊連到它，所以$|E|\ge |V|-1$
有以下幾個規定
Capacity constraint $0\le f(u,v)\le c(u,v),\forall u,v \in V$
Flow conservation: $\sum_{v\in V}f(v,u)=\sum_{v\in V}f(u,v),\forall u\in V-\{s,t\}$
* **deal with antiparallel edge**: 圖中若$(u,v)\in E$則$(v,u)\notin E$，若給定的圖兩點之間存在$(u,v),(v,u)\in E$，則在u、v之間加入一個新的點x，使得$c(u,x)=c(x,v)=c(u,v)$，如此一來就能替換掉antiparallel的情況產生 (證明正確性)
* **Multiple sources and sinks**
若給定的s、t不只一對，而是同時很多s跟t，則可以在圖中加入super source s'、super sink t'，使得$c(s',s_i)=\infty,c(t_i,t')=\infty$，並以(s',t')為source跟sink解此題 (證明)
### The Ford-Fulkerson method
* 稱為method而非algorithm，因為實作方式會導致時間複雜度不同
* **Residual networks**
除了本來給的圖，會建構一張residual network $G_f=(V_f,E_f)$，若$(u,v)\in E$則$(u,v),(v,u)\in E_f$，而每個邊個residual capacity定義如下
$c_f(u,v)=\begin{cases}
c(u,v)-f(u,v) \ \ if \ \ (u,v)\in E\\
f(v,u) \ \ if \ \ (v,u)\in E\\
0 \ \ otherwise
\end{cases}$
如果$(u,v)\in E$，則$c_f(u,v)$代表的是邊$(u,v)$在$G_f$當中還能增加的flow的量，$c_f(v,u)$則表示邊$(u,v)$目前已經有多少flow在上面，或者說能減去多少flow
所以$G_f=(V,E_f),E_f=\{(u,v)\in V\times V:c_f(u,v)>0\}$
從定義可以看出$|E_f|\le 2*|E|$
再定義$f'$，若$f$是$G$中的flow，則$f'$代表在$G_f$中對應的flow
可以定義augmentation of flow $f$ and $f'$，$f\uparrow f':V\times V\rightarrow R$
$(f\uparrow f')(u,v)=\begin{cases}
f(u,v)+f'(u,v)-f'(v,u) \ \ if \ \ (u,v)\in E\\
0
\end{cases}$
證明$(f\uparrow f')$為$G$中的flow，且$|f\uparrow f'|=|f|+|f'|$ (驗證capacity constraint和flow conservation)
* **augmenting paths**
a simple path from s to t in $G_f$
* **residual capacity** of a path p
$c_f(p)=min\{c_f(u,v):(u,v)\in p\}$
* **cuts of flow**
將vertex分為兩個集合S,T，$s\in S,t\in T$，net flow $f(S,T)=\sum_{u\in S} \sum_{v\in T} f(u,v)-\sum_{u\in S}\sum_{v\in T} f(v,u)$
capacity of the cut
$c(S,T)=\sum_{u\in S}\sum_{v\in T}c(u,v)$
* flow network $G$上的任意cut都滿足$f(S,T)=|f|$ (證明)
* 任何flow值都小於等於任何capacity of cuts (證明)
* 由以上定理可以知道，找maximum flow事實上就是在找minimum cut
因為任何cut的flow值都相同，且都小於任何cut的capacity，所以最大的flow會小於等於最小的cut capacity
如何證明$|f|=c(S,T)$ ?
* 以下三個敘述等價
1. $f$ is a maximum flow in $G$
2. The residual network $G_f$ contains no augmenting paths
3. $|f|=c(S,T)$ for some cut $(S,T)$ of $G$
```c=
Ford_Fulkerson(G,s,t){
for each edge (u,v) in G.E
(u,v).f=0;
while there exists a path p from s to t in Gf
residual_capacity = INF;
for each edge (u,v) in p
if c_f(u,v) < residual_capacity;
residual_capacity = c_f(u,v);
for each edge (u,v) in p
if (u,v) in G.E
(u,v).f = (u,v).f+residual_capacity;
else
(v,u).f = (v,u).f-residual_capacity;
}
```
* 時間複雜度取決於如何找到s到t的simple path
用BFS找: polynomial time
如果maximum flow = $|f^*|$，則時間複雜度會是$\Theta(E|f^*|)$
### Edmonds-Karp Algorithm
* 在ford-fulkerson method中，使用BFS來找augmenting path，每次都會找到最短的augmenting path，時間複雜度會是$\Theta(VE^2)$
### Maximum bipartite matching
* 雙分圖當中找到最大的matching cardinality
* 透過將原本的雙分圖$G$變成$G'=(V',E'),V'=V\bigcup \{s,t\}$，且每個邊的capacity設為1，再找到此圖的maximum flow，就會是maximum bipartite matching cardinality
## 尤拉迴路及漢米爾頓環路
| 名稱 | 定義 | 備註 |
| -------- | -------- | -------- |
| Euler circuit | 存在一個circuit經過$G$中每一個邊恰好一次 | |
| Euler trail | 存在一個trail經過$G$中每個邊恰好一次 ||
| Hamiltonian cycle | 存在一個cycle經過$G$中每個點恰好一次 ||
| Hamiltonian path | 存在一個path經過$G$中每個點恰好一次 ||
* $G$具有euler circuit $\Leftrightarrow$ $G$為連通圖且$\forall v\in V,deg(v)$為偶數
$K_n$具有euler circuit $\Leftrightarrow$ $n$為奇數
$K_{m,n}$具有euler circuit $\Leftrightarrow$ $m,n$皆為偶數
如果$G$為有向圖
$G$具有euler circuit $\Leftrightarrow$ $G$為強連通圖且$\forall v\in V,id(v)=od(v)$
* $G$具有euler trail $\Leftrightarrow$ $G$為連通圖且$G$中洽含0個或2個點的度數為奇數，其餘皆為偶數 (含奇數的那兩個點會是起點與終點)
* 以下三點為Hamiltonian cycle的必要條件，可用來否定一個graph是否具有Hamiltonian cycle
1. $\forall v\in V,deg(v)\ge 2$
2. 若$\exists v\in V,deg(v)=2$，則與$v$相鄰的兩邊必在Hamiltonian cycle中
3. 若$\exists v\in V,deg(v)\ge 2$，且知道$v$相鄰的某兩邊在Hamiltonian cycle中，則與$v$相鄰的其他邊必不在此cycle中
* $Q_n,n\ge 2$必具有Hamiltonian cycle (證明)
有向完全圖$K_n^*$必具有有向的Hamiltonian path
* $G=(V,E),|V|\ge 3$為一個無迴圈的無向圖，若$deg(x)+deg(y)\ge n-1,\forall x,y\in V,x\neq y$，則$G$具有Hamiltonian path
若$\forall v\in V,deg(v)\ge (n-1/2$，則$G$具有Hamiltonian path
* $G=(V,E),|V|\ge 3$為一個無迴圈的無向圖，若$deg(x)+deg(y)\ge n,\forall x,y\in V,x,y$不相鄰，則$G$具有Hamiltonian cycle
若$\forall v\in V,deg(v)\ge n/2$，則$G$具有Hamiltonian cycle
* $K_n,n\ge 3$必有Hamiltonian cycle
$G=(V_1\bigcup V_2,E)$為一個連通的雙分圖
1. 若$G$具有Hamiltonian cycle，則$|V_1|=|V_2|$
2. 若$G$具有Hamiltonian path，則$||V_1|-|V_2||\le 1$
## 平面圖
* 若G可以被重畫之後，每個邊都不產生交叉，則稱為平面圖
* **基本區分elementary subdivision**
$G=(V,E),E\neq \emptyset$為一個無迴圈的無向圖，若去掉$e=\{x,y\}\in E$並加入$\{x,z\},\{z,y\},z\notin V$，這動作稱為$G$的一個基本區分
* **同胚homeomorphic**
$G_1,G_2$為兩個無迴圈的無向圖，以下狀況稱這兩個圖同胚
1. $G_1\cong G_2$
2. 經由某圖$H$經過數次基本區分後皆可得到$G_1,G_2$
* **Kuratowski's theorem**
$G$為平面圖 $\Leftrightarrow$ $G$不含子圖與$K_5,K_{3,3}$同胚
* 平面圖可將平面分割成多個區域(region, face)，一個區域的度數為此區域邊界的邊數，所有區域的度數和洽為此圖邊數的兩倍
* $G=(V,E)$為一個平面圖且含$M$個分量圖，$r$表示區域個數，則$v-e+r=1+M$
* **Euler formula**
$G=(V,E)$為一個連通平面圖，$r$表示區域的個數，$v-e+r=2$
* $G=(V,E)$為一個無迴圈的簡單連通平面圖(樹)，$|V|=v,|E|=e\ge 2,r$為區域個數
1. $3r/2\le e\le 3v-6$，因為每個區域的度數至少為三，若$e\ge 3v-6$可以否定它為平面圖
2. 若$G$不含任何三角形，則$e\le 2v-4$，因為每個區域的度數至少為四
若此圖中每個環路至少由k個邊組成(每個區域的度數至少k)，$k\ge 3$，則$e\le (\cfrac{k}{k-2})(v-2)$ (證明)
## 著色問題
* 若$\forall (u,v)\in E,u,v$著不同顏色，則稱為$G$的一種正當著色
* $G$可以用n種顏色做正當著色，稱為n-colorable
可以使$G$為正當著色的最小n稱為$G$的chromatic number，$\chi(G)$，且稱$G$為n-chromatic
* 若$G$為n-colorable，則也會是(n+1)-colorable
$\chi(K_n)=n$
若$K_n$為$G$的子圖，則$\chi(G)\ge n$
$\chi(K_{m,n})=2$ (又一個判斷雙分圖的方式)
若$G$有k個分量圖，$\chi(G)=max_{1\le i\le k}(\chi(G_i))$
* 任意平面圖皆為4-colorable
* **著色多項式chromatic polynomial**
$P(G,\lambda)$表示最多使用$\lambda$種顏色對$G$做正當著色的不同方法數
$\chi(G)=min\{\lambda | P(G,\lambda)>0\}$
* 重要圖的著色多項式
1. $P(P_n,\lambda)=\lambda(\lambda-1)^{n-1}$
2. $P(K_n,\lambda)=P_n^{\lambda}=\lambda^{(n)}$
3. 有k個分量圖，$P(G,\lambda)=P(G_1,\lambda)\cdots P(G_k,\lambda)$
* **分解定理**
$G-e$表示把e={a,b}給移除，$G\cdot e$表示把$G-e$中的a,b給黏合
$P(G,\lambda)=P(G-e,\lambda)-P(G\cdot e,\lambda)$ (證明)
也可以表示成$P(G,\lambda)=P(G+e,\lambda)+P(G\cdot e,\lambda)$
* 若$G=(V,E),G_1=(V_1,E_1),G_2=(V_2,E_2),G=G_1\bigcup G_2,G_1\bigcap G_2=K_n$，則$P(G,\lambda)=\cfrac{P(G_1,\lambda)P(G_2,\lambda)}{\lambda^{(n)}}$
* $P(G,\lambda)$的常數項必定為0($P(G,0)=0$)，係數和也必定為0($P(G,1)=0$)
* $|V|=n$則$P(G,\lambda)$為$\lambda$的n次多項式且$\lambda^n$的係數必定為1
## 樹
| 名稱 | 定義 | 備註 |
| -------- | -------- | -------- |
| 森林 | acyclic graph，無向無環圖 | |
| 樹 | acyclic connected graph | 樹必為森林，森林未必為樹 |
| degenerate tree | 退化樹，只含一個點的樹 ||
| 有向樹 | $G$為有向圖，將其視為無向圖時為一顆樹 ||
| 有根樹 | 有向樹中存在唯一一點$r,id(r)=0$ ||
| leaf | 有根樹中的$v\in V,od(v)=0$ ||
| internal node | 有根樹中的$v\in V,od(v)\neq0$ ||
| m-ary tree | 有根樹每個內部節點至多m個兒子 ||
| full m-ary tre | 有根樹每個內部節點恰好m個兒子 ||
* 樹不含環路，所以不含奇數長度的環路，所以樹為雙分圖，所以樹必為2著色圖
樹為邊數最少的連通圖
* $G$為無迴圈的簡單無向圖，下列為等價
1. $G$為樹
2. $G$中不含環路且$|E|=|V|-1$
3. $G$為連通圖且$|E|=|V|-1$
* $G$為非退化樹，$|V|\ge 2$，以下條件為等價
1. 任兩點恰有唯一路徑兩連
2. 去掉任一邊變為unconnected graph
3. 加入任一個$\{x,y\}\notin E$，會使$G$產生一個環路且該新增的邊一定在環路中
* $T=(V,E)$為一個非退化樹，則$T$中至少含兩個懸吊點 (證明)
* $T=(V,E)$為一顆m-ary tree，$|V|=n,i,l$分別代表內部節點及樹葉的個數
1. $n\le mi+1$
2. $l\le (m-1)+1$
3. $i\ge \cfrac{l-1}{m-1}$ 且 $i\ge \cfrac{n-1}{m}$
Sign in with Wallet
Connect another wallet