2020 競技程設教材 HackMD Book

2019 Week 13: Graph 2

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

最大流 (Maximum flow)

給圖

$G=(V,E)$，對邊

$(u,v)\in E$ 有剩餘容量

$R(u,v)$
求從點

$s$ 到點

$t$ 的最大流量。

以下圖為例：
邊上面的數字代表容量上限

例如

$R(e,b)=2$

而

$s\to e\to b\to t$ 可得流量

$1$ 或

$2$，
且當此路徑流量為

$1$ 時，剩餘容量皆為

$1$

流量

$2$ 則剩餘容量皆

$0$

若

$s\to e\to f\to t$
則這流量最大只能為

$1$，是由於邊最多承載容量為

$1$

這裡

$x/y$ 表示

$x$ 流量，

$y$ 容量上限，而剩餘容量為

$y-x$

也就是說：

$s\to e\to f\to t$ 流量

$1$

$s\to a\to b\to t$ 流量

$1$
能得流量

$2$

若是

$s\to e\to f\to t$ 流量

$1$

$s\to e\to b\to t$ 流量

$1$

$s\to a\to b\to t$ 流量

$1$
能得流量

$3$，這就是最大流

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

$>0$)的路徑

Augmenting path

給下圖：

隨便找到一條流

$f_1$：

找到第二條流

$f_2$：
這是無向邊，所以它想要往上跑
如果邊容量允許的話這是可行的

若

$f_1=f_2$

中間兩流相遇的部份會相消

若

$f_1>f_2$

中間相遇部份

$f_1$ 多少會被減弱一些

所以將顏色改變一下，因為流量不見得與另外兩色相同

具體來說

給下圖：

幾乎跟上面例子一樣

特別注意，

$R(b,f)=3$ 而

$R(f,b)=0$

一樣的

$f_1$：

接著

$f_2$：

但是

$f_2$ 過不去，因為剩餘容量為

$0=R(f,b)$
若在流

$f_1$ 形成時，給予反向邊^[1]容量，就能使得

$f_2$ 流得過去

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

然後給予反向邊容量：

這裡避免圖過於複雜，把

$0$ 邊去掉

所以現在

$f_2$ 能流過去了！

實際上，

$b$ 到

$t$ 的流量原本

$3$，經過

$f_2$ 後變為

$\mathbf{\text{2}}$
也就是說，若現在邊上代表的是流量：

所以直覺的，每次找到 augmenting path，讓流送到

$t$
不斷重複這個過程，直到找不到 augmenting path，就能求得最大流

這稱作 Ford-Fulkerson method

Edmonds-Karp algorithm

如果邊是無向的，

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

用 BFS 找出從

$s$ 到

$t$ 的 augmenting path
將路徑上各邊的剩餘容量扣除流量，以及將各反向邊^[1:1]剩餘容量加上流量。

重複 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

練習：

UVa OJ 820 Internet Bandwidth
UVa OJ 10330 Power Transmission
UVa OJ 11987 Almost Union-Find
POJ 2584 T-Shirt Gumbo
POJ 3228 Gold Transportation

Articulation point

Articulation point 中譯 關節點 (簡稱 AP)，
當連通圖上此點被拔除，圖會分為多塊連通圖

給定連通圖，找到所有 AP

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

如何讓 AP 不再是 AP 呢？
例如： 將

$5$ 變非 AP，可讓

$7$ 連到

$3$，及

$6$ 連到

$4$。

也就是說，若問連通圖中有哪些點是 AP，先遍歷出棵樹 (例如 DFS 樹)
接著直覺的，節點的子孫有邊回到比此節點還高^[2] (淺)的節點，則此節點非 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)$

^[3]

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
ICPC World Finals 2003 Building Bridges
CODEFORCES 194C Cutting Figure

Strongly Connected Components (SCC)

強連通是只屬於有向圖的概念

根據第十一週教材，

• 把圖的方向拿掉，連通的話稱此圖弱連通
• 加上方向後仍然連通，則此圖強連通

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

^[4]

給定圖，求圖至少有幾塊強連通分塊

Kosaraju's Algorithm

連通意味著任兩點

$u,v$ 之間有路
那麼把

$u⇝v$ 的各邊反過來，對

$v⇝u$ 也反過來，圖理當也連通

$u⇝v$ 表示

$u$ 到

$v$ 路徑

因為

$u⇝v$ 及

$v⇝u$ 兩路合併，能得到環，環反過來還是環
也就是說，對於強連通圖：

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

• 對於無相圖，第四週教材提到 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
UVa OJ 247 Calling Circles
UVa OJ 11838 Come and Go
* ICPC Regionals 2010 Hangzhou Traffic Real Time Query System

---

1. 當邊為點

   $u$ 到點
   $v$，則反向邊指的是
   $v$ 到
   $u$ ↩︎ ↩︎

2. 所謂的比較高，意思是距離根比較近 ↩︎

3. Wikipedia/ A demo of Tarjan's algorithm to find cut vertices. ↩︎

4. Wikipedia/ Graph with strongly connected components marked ↩︎