:+1: [2020 競技程設教材 HackMD Book](https://hackmd.io/@nckuacm/ryLIV6BYI) :+1:

2019 Week 13: Graph 2
=

本週主題內容較為複雜，時間會帶給各位對圖論演算法的直覺感悟

# 最大流 (Maximum flow)
:::info
給圖 $G=(V, E)$，對邊 $(u, v) \in E$ 有**剩餘容量** $R(u, v)$
求從點 $s$ 到點 $t$ 的最大流量。
:::

以下圖為例：
邊上面的數字代表**容量上限**
> 例如 $R(e, b) = 2$

digraph {
  a -> b[label=1]
  b -> t[label=2];
  s -> e[label=2]
  e -> f[label=1];
  
  rankdir="LR";
  { rank="same" s->a [label=1]}
  { rank="same" e->b [label=2]}
  { rank="same" f->t [label=1]}
}

而 $s \rightarrow e \rightarrow b\rightarrow t$ 可得流量 $1$ 或 $2$，
且當此路徑流量為 $1$ 時，剩餘容量皆為 $1$
> 流量 $2$ 則剩餘容量皆 $0$

digraph {
  a -> b[label=1]
  b -> t[label=2, color=red];
  s -> e[label=2, color=red]
  e -> f[label=1];
  
  rankdir="LR";
  { rank="same" s->a [label=1]}
  { rank="same" e->b [label=2, color=red]}
  { rank="same" f->t [label=1]}
}

若 $s \rightarrow e \rightarrow f\rightarrow t$
則這流量最大只能為 $1$，是由於邊**最多承載**容量為 $1$

digraph {
  a -> b[label=1]
  b -> t[label=2];
  s -> e[label="1/2", color=red]
  e -> f[label="1/1", color=red];
  
  rankdir="LR";
  { rank="same" s->a [label=1]}
  { rank="same" e->b [label=2]}
  { rank="same" f->t [label="1/1", color=red]}
}

==這裡 $x/y$ 表示 $x$ 流量，$y$ 容量**上限**，而剩餘容量為 $y-x$==

也就是說：
$s \rightarrow e \rightarrow f\rightarrow t$ 流量 $1$
$s \rightarrow a \rightarrow b\rightarrow t$ 流量 $1$
能得流量 $2$

digraph {
  a -> b[label="1/1", color=red]
  b -> t[label="1/2", color=red];
  s -> e[label="1/2", color=red]
  e -> f[label="1/1", color=red];
  
  rankdir="LR";
  { rank="same" s->a [label="1/1", color=red]}
  { rank="same" e->b [label=2]}
  { rank="same" f->t [label="1/1", color=red]}
}

若是
$s \rightarrow e \rightarrow f\rightarrow t$ 流量 $1$
$s \rightarrow e \rightarrow b\rightarrow t$ 流量 $1$
$s \rightarrow a \rightarrow b\rightarrow t$ 流量 $1$
能得流量 $3$，這就是**最大流**

digraph {
  a -> b[label="1/1", color=red]
  b -> t[label="2/2", color=blue];
  s -> e[label="2/2", color=blue]
  e -> f[label="1/1", color=red];
  
  rankdir="LR";
  { rank="same" s->a [label="1/1", color=red]}
  { rank="same" e->b [label="1/2", color=red]}
  { rank="same" f->t [label="1/1", color=red]}
}

在找到最大流量之前，得先討論怎樣的圖，存在著一條可以獲得流量($>0$)的路徑

## Augmenting path

給下圖：

digraph {
  s
  t
  Node[label=""]
  s -> 5 -> 6[dir=none];
  2 -> 3 -> 4 -> t[dir=none];
  
  rankdir="LR";
  s -> 1 -> 2 [dir=none];
  { rank="same" 2->6 [dir=none] }
  6 -> 7 -> 8 -> t [dir=none];
}

**隨便找**到一條流 $f_1$：

digraph {
  s
  t
  Node[label=""]
  s -> 5 -> 6[dir=none];
  2 -> 3 -> 4 -> t[dir=none];
  
  rankdir="LR";
  s -> 1 -> 2 [color=red, penwidth=4]
  { rank="same" 2->6 [color=red, penwidth=4]};
  6 -> 7 -> 8 -> t [color=red, penwidth=4]
}

找到第二條流 $f_2$：
這是無向邊，所以它想要往上跑
如果==邊容量允許==的話這是可行的

digraph {
  s
  t
  Node[label=""]
  s -> 5 -> 6[color=blue, penwidth=4];
  2 -> 3 -> 4 -> t[color=blue, penwidth=4];
  { rank="same" 6->2 [color=blue, penwidth=4]};
  { rank="same" 2->6 [dir=none] }
  
  rankdir="LR";
  s -> 1 -> 2 [color=red, penwidth=4]
  { rank="same" 2->6 [color=red, penwidth=4]};
  6 -> 7 -> 8 -> t [color=red, penwidth=4]
}

### 若 $f_1 = f_2$
中間兩流相遇的部份會**相消**

digraph {
  s
  t
  Node[label=""]
  { rank="same" 2->6 [dir=none] }
  rankdir="LR";
  s -> 1 -> 2 [color=red, penwidth=4]
  6 -> 7 -> 8 -> t [color=red, penwidth=4]
  s -> 5 -> 6[color=blue, penwidth=4];
  2 -> 3 -> 4 -> t[color=blue, penwidth=4];
  
}

### 若 $f_1 > f_2$
中間相遇部份 $f_1$ 多少會被減弱一些
> 所以將顏色改變一下，因為**流量**不見得與另外兩色相同

digraph {
  s
  t
  Node[label=""]
  s -> 1 -> 2 [color=red, penwidth=4]
  6 -> 7 -> 8 -> t [color=red, penwidth=4]
  
  rankdir="LR";
  s -> 5 -> 6[color=blue, penwidth=4];
  { rank="same" 2->6 [color=orange, penwidth=4]};
  2 -> 3 -> 4 -> t[color=blue, penwidth=4];
}

### 具體來說

給下圖：
> 幾乎跟上面例子一樣

特別注意，$R(b, f) = 3$ 而 $R(f,b)=0$

digraph {
  s
  t
  b
  f
  Node[label=""]
  s -> e -> f[ label=1];
  b -> c -> d -> t[ label=1];
  
  rankdir="LR";
  s -> a -> b [ label=3];
  { rank="same" a->e [ style=invis] }
  { rank="same" b->f [ label=3] }
  { rank="same" c->g [ style=invis] }
  { rank="same" d->h [ style=invis] }
  f -> g -> h -> t [ label=3];
}

一樣的 $f_1$：

digraph {
  s
  t
  b
  f
  Node[label=""]
  t [label="t:3"];
  s -> e -> f[ label=1];
  b -> c -> d -> t[ label=1];
  
  rankdir="LR";
  s -> a -> b [ label="3/3", color=red];
  { rank="same" a->e [ style=invis] }
  { rank="same" b->f [ label="3/3", color=red] }
  { rank="same" c->g [ style=invis] }
  { rank="same" d->h [ style=invis] }
  f -> g -> h -> t [ label="3/3", color=red];
}

接著 $f_2$：

digraph {
  s
  t
  b
  f
  Node[label=""]
  t [label="t:3"];
  s -> e -> f[ label="1/1", color=blue];
  b -> c -> d -> t[ label=1];
  
  rankdir="LR";
  s -> a -> b [ label="3/3", color=red];
  { rank="same" a->e [ style=invis] }
  { rank="same" b->f [ label="3/3", color=red] }
  { rank="same" c->g [ style=invis] }
  { rank="same" d->h [ style=invis] }
  f -> g -> h -> t [ label="3/3", color=red];
}

但是 $f_2$ **過不去**，因為剩餘容量為 $0=R(f, b)$
若在流 $f_1$ 形成時，給予**反向邊[^4]容量**，就能使得 $f_2$ 流得過去

也就是：
接下來**只需紀錄剩餘容量**就足夠知道流量為何了
所以==現在邊上數字代表的是**剩餘容量**==

digraph {
  s
  t
  b
  f
  Node[label=""]
  t [label="t:3"];
  s -> e -> f[ label=1];
  b -> c -> d -> t[ label=1];
  
  rankdir="LR";
  s -> a -> b [ label="0", color=red];
  { rank="same" a->e [ style=invis] }
  { rank="same" b->f [ label="0", color=red] }
  { rank="same" c->g [ style=invis] }
  { rank="same" d->h [ style=invis] }
  f -> g -> h -> t [ label="0", color=red];
}

然後**給予反向邊容量**：
>這裡避免圖過於複雜，把 $0$ 邊去掉

digraph {
  s
  t
  b
  f
  Node[label=""]
  t [label="t:3"];
  s -> e -> f[ label=1];
  b -> c -> d -> t[ label=1];
  
  rankdir="LR";
  s -> a -> b [ label="3", dir=back];
  { rank="same" a->e [ style=invis] }
  { rank="same" b->f [ label="3", dir=back] }
  { rank="same" c->g [ style=invis] }
  { rank="same" d->h [ style=invis] }
  f -> g -> h -> t [ label="3", dir=back];
}

所以現在 $f_2$ 能流過去了！

digraph {
  s
  t
  b
  f
  Node[label=""]
  t [label="t:4"];
  s -> e -> f[ label=1, color=blue];
  b -> c -> d -> t[ label=1, color=blue];
  
  rankdir="LR";
  s -> a -> b [ label="3", dir=back];
  { rank="same" a->e [ style=invis] }
  { rank="same" b->f [ label="3", dir=back, color=blue] }
  { rank="same" c->g [ style=invis] }
  { rank="same" d->h [ style=invis] }
  f -> g -> h -> t [ label="3", dir=back];
}

實際上， $b$ 到 $t$ 的流量原本 $3$，經過 $f_2$ 後變為 $\textbf{2}$
也就是說，若==現在邊上代表的是**流量**==：

digraph {
  s
  t
  b
  f
  Node[label=""]
  t [label="t:4"];
  s -> e -> f[ label=1, color=blue];
  b -> c -> d -> t[ label=1, color=blue];
  
  rankdir="LR";
  s -> a -> b [ label="3", color=red];
  { rank="same" a->e [ style=invis] }
  { rank="same" b->f [ label="2", color=orange] }
  { rank="same" c->g [ style=invis] }
  { rank="same" d->h [ style=invis] }
  f -> g -> h -> t [ label="3", color=red];
}

所以直覺的，每次**找到 augmenting path**，讓流送到 $t$
**不斷重複**這個過程，直到找不到 augmenting path，就能求得最大流
> 這稱作 Ford-Fulkerson method

## Edmonds-Karp algorithm
如果邊是無向的，

digraph {
  rankdir=LR
  u -> v[dir=none, label=x]
}

則將邊變為兩條**剩餘容量相等**的**有向邊**

digraph {
  rankdir=LR
  u -> v [dir=back, label=x]
  u -> v [style=invis]
  u -> v [label=x]
}

用 **BFS** 找出從 $s$ 到 $t$ 的 augmenting path
將路徑上各邊的剩餘容量扣除**流量**，以及將各反向邊[^4]剩餘容量加上**流量**。

**重複** BFS 直到找不到 augmenting path

int max_flow = 0;

while (1) {
  memset(vis, false, sizeof(vis));
  vis[s] = true;
  
  memset(flow, 0, sizeof(flow));
  flow[s] = INF;
  
  queue<int> Q;
  Q.push(s); 
  
  while (!Q.empty()) {
    int u = Q.front(); Q.pop();

    for (int v = s; v <= t; v++) {
      if (!R[u][v] || vis[v]) continue;
      vis[v] = true;
      
      flow[v] = min(flow[u], R[u][v]); // 流只挑最小的剩餘容量
      Q.push(v);
      pre[v] = u; // 紀錄 augmenting path
    }
  }
  
  if (flow[t] == 0) break;
  max_flow += flow[t];

  for (int v = t; v != s; v = pre[v]) {
    int u = pre[v];
    R[u][v] -= flow[t];
    R[v][u] += flow[t];
  }
}

> 感受下圖像化的流程： [WilliamFiset/ Edmonds Karp Algorithm](https://www.youtube.com/watch?v=RppuJYwlcI8)

#### 練習：
[UVa OJ 820 Internet Bandwidth](https://uva.onlinejudge.org/external/8/820.pdf)
[UVa OJ 10330 Power Transmission](https://uva.onlinejudge.org/external/103/10330.pdf)
[UVa OJ 11987 Almost Union-Find](https://uva.onlinejudge.org/external/119/11987.pdf)
[POJ 2584 T-Shirt Gumbo](http://poj.org/problem?id=2584)
[POJ 3228 Gold Transportation](http://poj.org/problem?id=3228)

<!--

考慮下圖：

digraph {
  s
  t
  Node[label=""]
  s -> e -> t[ label=q];
  rankdir="LR";
  s -> a -> t[ label="p"];
  { rank="same" e->a [label="1"] }
}

如果每次 augmenting path 流量都為 $1$，則時間成本為 $p + q$
故演算法複雜度 -->

# Articulation point
Articulation point 中譯 關節點 (簡稱 AP)，
當連通圖上此**點**被拔除，圖會分為多塊**連通圖**
:::info
給定連通圖，找到所有 AP
:::

考慮**樹**，顯然除**葉**以外，其餘的節點都為 AP
且若**根**只有一個子節點，則不為 AP

graph {
  3 -- 4;
  3 -- 5 -- 6;
  5 -- 7;
  7 -- 8;
}

如何讓 AP 不再是 AP 呢？
例如： 將 $5$ 變非 AP，可讓 $7$ 連到 $3$，及 $6$ 連到 $4$。

graph {
  {9 [ style=invis, width=0, label=""]}
  {3 -- 9 [ style=invis]}
  {3 -- 9 [ style=invis]}
  3 -- 4;
  {"10" [ style=invis, width=0, label=""]}
  {3 -- 10 [ style=invis]}
  3 -- 5 -- 6;
  6 -- 4 [color=red];
  { rank="same" 4--5 [ style=invis] }
  5 -- 7;
  7 -- 3 [color=red];
  { rank="same" 6--7 [ style=invis] }
  7 -- 8;
  
}

也就是說，若問**連通圖**中有哪些點是 AP，先遍歷出棵**樹** (例如 DFS 樹)
接著直覺的，節點的子孫**有邊**回到比此節點還高[^5] (淺)的節點，則此節點非 AP。
> 高指的是 level 數字較小，淺指的是 depth 數字較小

而這個**連向祖先的邊**，稱作 **back edge**

## Tarjan’s algorithm for APs

實作上透過下列兩個函數，以找出所有 AP
- $\text{dep}(n)$ 代表節點 $n$ 的 depth
若節點還未拜訪過 $\text{dep}(n) = -1$
- $\text{low}(n)$ 代表節點 $n$ 透過 back edge 能連向**最高**節點的 depth 值，
若無 back edge 則為 $\text{dep}(n)$

 [^tarjamapdemo]

Tarjan 用 DFS 遍歷出樹：

void dfs(int p, int u, int d) { // p := previous, d := depth
  dep[u] = low[u] = d;
  int cnt = !!d; // (parent and children of u) in dfs tree
  bool back_error = false;

  for (int v: E[u]) if (v != p) {
    if (dep[v] != -1) {
      low[u] = min(low[u], dep[v]);
      continue;
    }
    
    cnt++;
    dfs(u, v, d+1);
    
    low[u] = min(low[u], low[v]);
    if (low[v] >= d) back_error = true;
  }

  if (cnt > 1 && back_error) AP.push_back(u);
}

#### 練習：
[UVa OJ 315 Network](https://uva.onlinejudge.org/external/3/315.pdf)
[ICPC World Finals 2003 Building Bridges](https://icpcarchive.ecs.baylor.edu/external/27/2721.pdf)
[CODEFORCES 194C Cutting Figure](https://codeforces.com/contest/194/problem/C)

# Strongly Connected Components (SCC)
強連通是只屬於**有向圖**的概念

根據[第十一週教材](https://hackmd.io/s/SkCtEVcq4)，
- 把圖的**方向**拿掉，連通的話稱此圖**弱連通**
- 加上方向後仍然連通，則此圖**強連通**

雖然有向圖不總有強連通性，但能把圖分成幾塊**強連通分塊**：

[^scc]

:::info
給定圖，求圖**至少**有幾塊強連通分塊
:::
## Kosaraju's Algorithm
連通意味著任兩點 $u, v$ 之間有路
那麼把 $u\leadsto v$ 的各邊反過來，對 $v\leadsto u$ 也反過來，圖理當也連通
> $u\leadsto v$ 表示 $u$ 到 $v$ 路徑

因為 $u\leadsto v$ 及 $v\leadsto u$ 兩路合併，能得到環，**環反過來還是環**
也就是說，對於強連通圖：

digraph {
  node[label=""]
  rankdir="LR"
  b -> c -> a
  a -> d [dir=back]
  c -> e -> d
  a -> b
}

把邊方向反過來仍具有強連通性：

digraph {
  node[label=""]
  edge[dir=back]
  rankdir="LR"
  b -> c -> a
  a -> d [dir=forward]
  c -> e -> d
  a -> b
}

- 對於**無相圖**，[第四週教材](https://hackmd.io/s/SJ7nxwRL4#%E7%AF%84%E4%BE%8B-UVa-OJ-572-Oil-Deposits%EF%BC%9A)提到 DFS 能判斷是否具有連通性
- 對於**有向圖** DFS 拜訪到的節點與反邊圖 DFS 拜訪的**節點相同**，則為強連通
> 反邊圖就是把圖上的邊全改為反向

void forward(int u) {
  vis[u] = true;
  for (int v = 0; v < n; v++) if (E[u][v] && !vis[v]) forward(v);
  st.push(u);
}

void backward(int u) {
  vis[u] = true;
  for (int v = 0; v < n; v++) if (E[v][u] && !vis[v]) backward(v);
}

> 這裡 `E` 是鄰接矩陣

stack `st` 紀錄有哪些點是在 forward 走過，但 backward 沒走過

memset(vis, false, sizeof(vis));
for (int u = 0; u < n; u++) if (!vis[u]) forward(u); 

memset(vis, false, sizeof(vis));
int cnt = 0; // 紀錄有多少強連通分塊
while (!st.empty()) {
  int u = st.top(); st.pop();
  if (!vis[u]) cnt++, backward(u);
}

基於 stack 的特性，可將 forward 先一次做完，再一次次做 backward

#### 練習：
[ICPC Regionals 2008 Taipei Road Networks](https://icpcarchive.ecs.baylor.edu/external/42/4262.pdf)
[UVa OJ 247 Calling Circles](https://uva.onlinejudge.org/external/2/247.pdf)
[UVa OJ 11838 Come and Go](https://uva.onlinejudge.org/external/118/11838.pdf)
\* [ICPC Regionals 2010 Hangzhou Traffic Real Time Query System](https://icpcarchive.ecs.baylor.edu/external/48/4839.pdf)
<!--
## Tarjan's algorithm for SCCs -->

[^4]: 當邊為點 $u$ 到點 $v$，則*反向邊*指的是 $v$ 到 $u$

[^5]: 所謂的比較高，意思是距離根比較近
[^tarjamapdemo]: [Wikipedia/ A demo of Tarjan's algorithm to find cut vertices.](https://en.wikipedia.org/wiki/Biconnected_component#/media/File:TarjanAPDemoDepth.gif)
[^scc]: [Wikipedia/ Graph with strongly connected components marked](https://en.wikipedia.org/wiki/Strongly_connected_component#/media/File:Scc.png)