<style>
.blue {
color: #38bdf8
}
</style>
# Maximum Flow
## Introduction
### Definition
---
:::info
#### ***Flow networks***
:::
A flow network $G = (\ V,\ E\ )$ is a directed graph in which each edge $(u,\ v) \in E$ has nonnegative capacity $c \ (u, \ v) \ge 0$
* $if \ (u, \ v) \in E \implies (v, u) \not\in E$ (not allow self-loops)
* each network contains a source $s$ and a sink $t$
* $\forall \ v \in V$ always exists a path $s \rightarrow v \rightarrow t$
* $|\ E\ | \ge |\ V\ | - 1$
> each vertex other than $s$ has at least one entering edge
>
> each eage is labeled by $f(u,v)/c(u,v)$
:::info
***Flow***
:::
A flow in $G$ is a real-valued function $f : V \times V \rightarrow \mathbb {R}$
> vetex之間有一實數代表flow (直觀理解)
* **Capacity constraint**
$\forall \ u, \ v \in V ,\ \ 0 \le f\ (u,\ v) \le c\ (u,\ v)$
> 點跟點之間flow不可能超過capacity
* **Flow conservation**
$\forall \ u \in V - \{s,\ t\}\ , \ \sum\limits_{v \ \in V} f\ (v,\ u)=\sum\limits_{v \ \in V} f\ (u,\ v)$
> 有多少水流流進 $u$ 就有多少水流從 $u$ 流出
* **The value of a flow**
$|\ f\ | = \sum\limits_{v \ \in V} f\ (s, \ v) - \sum\limits_{v \ \in V} f\ (v, \ s)$
> $|\ f \ |$代表flow value，類似於向量長表示法
> the total flow out of the source minus the flow into the source
:::warning
maximun-flow problem 主要目標是最大化 $|\ f\ |$
:::
:::info
***Residual networks***
:::
Given a flow network $G=(V,\ E)$ and a flow $f$ , the residual network of $G$ induced by $f$ is $G_f = (V,\ E_f)$ , where
$E_f = \{\ (u,\ v) \in V \times V: c_f(u, \ v) \gt 0\}$
Residual network consists of edges whose capacities represent how the flow can change on edges of $G$ . We define the <span class="blue">residual capacity</span> $c_f\ (u, \ v)$ by
\begin{align}
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}
\end{align}
> 如果 (u, v) edge存在於 $G$，對應的意義是可<span class="blue">額外增加</span>多少流量
> 如果 (v, u) edge存在 $G$，對應的意義是可<span class="blue">撤回</span>多少流量
:::warning
$(u, \ v) 、 (v, \ u)$不能同時存在，因為flow network的定義不允許雙向邊(self-loops)
:::
:::warning
$(v,\ u) \in E$，雖然$(u,\ v) \not\in E$ 不存在於 $G$，但其存在於$G_f$ (residual network)中，代表著<span class="blue">減少流量</span>，其目的是為了能夠撤銷$(v,\ u)$ flow，以便增加整體flow value
:::
> (a) represent the flow network and (b) represent the residual network of (a)
***property***
* $|\ E_f \ | \le 2\ |\ E\ |$
> residual network可表示flow network可增加或撤回的flow (最多2個edge)，故residual edge一定不會超過flow networks edge 2 倍數量
:::info
***Augmentation***
:::
:::warning
A flow in a residual network provides a roadmap for adding flow to the original flow network.
:::
Let $f$ is a flow in $G$ , and $f^{\ '}$ is a flow in $G_f$ , we define $f \uparrow f{\ '}$ , the <span class="blue">augemntation</span> of flow $f$ by $f^{\ '}$, to be a function from $V \times V$ to $\mathbb {R}$ , defined by
\begin{align}
(f \uparrow f^{\ '}) (u,\ v) =
\begin{cases}
&f(u,\ v)+f^{\ '}(u, \ v)-f^{\ '}(v, \ u)
&if\ (u,\ v)\in E \\
&0
&otherwise
\end{cases}
\end{align}
> 這個式子表達了原本的flow增加與減少進行形成新的flow
> 舉個例子，A $\rightarrow$ B 原本有5份水流，如今增加3份水流過去，同時又有2份水流過來
> 那麼現今A $\rightarrow$ B的flow也理所當然為 $5+3-2=6$ 份水流
:::warning
Pushing flow on the reverse edge in the residual network is known as <span class="blue">cancellation</span>
:::
***Lemma 1***
Let $G = (V, \ E)$ be a flow network with source $s$ and sink $t$, and let $f$ be a flow in $G$. Let $G_f$ be the residual network of $G$ induced by $f$ , and let $f^{\ '}$ be a flow in $G_f$. Then the function $f \uparrow f^{\ '}$ is a flow in $G$ with value $|\ f \uparrow f^{\ '}\ |=|\ f\ |+|\ f^{\ '}\ |$
> 這個定理直觀的理解就是原本的flow $f$ 透過flow $f^{\ '}$作用形成新的flow $f \uparrow f^{\ '}$，而這個flow value為個別的flow value相加
:::info
***Augmenting paths***
:::
an <span class="blue">augmenting path</span> $p$ is a simple path from $s$ to $t$ in the residual network $G_f$
> (b)圖中藍色的線就是augmenting path
> 我們可以觀察到這段路徑可以通過最大容量為4 (取該路徑最小容量)
:::warning
注意: 藍色路徑同時包含增加flow與撤回flow (對$G$而言)
:::
We call the maximum amount by which we can increase the flow on each edge in an augmenting path $p$ the <span class="blue">residual capacity</span> of $p$ , given by
$c_f(p)=min\{ c_f(u,\ v):(u,\ v)\ is\ in\ p \}$
***Lemma 2***
Let $G = (V,\ E)$ be a flow network, let $f$ be a flow in $G$ , and let $p$ be an augmenting path in $G_f$. Define a function $f_p : V \times V \rightarrow \mathbb {R}$ by
\begin{align}
f_p(u,\ v) =
\begin{cases}
&c_f\ (p)
&if\ (u,\ v)\ is\ on\ p \\
&0
&otherwise
\end{cases}
\end{align}
Then, $f_p$ is a flow in $G_f$ with value $|\ f_p\ |=c_f\ (p) \gt 0$
> augmenting path $p$ 可以形成flow其值為該路徑的最小容量
***Corollary 3***
By ***Lemaa 1*** and ***Lemaa 2*** , we can conclude $|\ f \uparrow f_{p}\ |=|\ f\ |+|\ f_{p}\ | \gt |\ f\ |$
:::info
***Cuts of flow networks***
:::
A <span class="blue">cut</span> $(S,\ T)$ of flow network $G=(V,\ E)$ is a partition of $V$ into $S$ and $T=V-S$ such that $s \in S$ and $t \in T$
if $f$ is a flow, then the <span class="blue">net flow</span> $f(S,\ T)$ across the cut $(S,\ T)$ is defined to be
$f(S, T)=\sum\limits_{\ u\ \in S}\sum\limits_{\ v\ \in T}f(u,\ v)-\sum\limits_{\ u\ \in S}\sum\limits_{\ v\ \in T}f(v,\ u)$
> net flow的意義是從 $S$ 流向 $T$ 減去 $T$ 流向 $S$ 的flow，其計算方式就是將每個點跟點之間的流量加總
> 例如上圖，$f(v_1,\ v_3)+f(v_2,\ v_4)-f(v_3,\ v_2)=12+11-4=19$
The <span class="blue">capacity</span> of the cut $(S,\ T)$ is
$c(S,\ T)=\sum\limits_{u \in S}\sum\limits_{v \in T} c(u,\ v)$
> capacity這裡只計算 $S$ 到 $T$ 的容量
>如上圖，$c(v_1,\ v_3)+c(v_2,\ v_4) = 12+14=26$
***Lemma 4***
Let $f$ be a flow in a flow network $G$ with source $s$ and sink $t$ , and let $(S,\ T)$ be any cut of $G$. Then the net flow across $(S,\ T)$ is $f(S,\ T)=|\ f\ |$
***Corollay 5***
The value of any flow $f$ in a flow network $G$ is bounded from above by the capacity of any cut of $G$
> 此推論描述，maximum flow一定不會超過任意cut的capacity
---
### Theorem
:::info
***Max-flow min-cut theorem***
:::
if $f$ is a flow in a flow network $G=(V,\ E)$ with source $s$ and sink $t$, then the following conditions are equivalent:
1. $f$ is maximum flow in $G$
2. $G_f$ contains no augmenting paths
3. $|\ f\ | = c(S,\ T)$ for some cut of $(S,\ T)$ of $G$
:::warning
透過這個定理我們可以得出只要$G_f$不存在augmenting path時，代表此時已完成到最大流計算
:::
---
### Ford-Fulkerson algorithm
:::info
***basic version***
:::
:::danger
Ford-Fulkerson若使用DFS尋找augmenting path，使得worse case complexity為$O(|\ f\ | * E)$
:::
> 如上圖所示，需要迭代2000000回才能得出答案
:::info
***The Edmonds-Karp algorithm***
:::
為了避免worse case，The Edmonds-Karp algorithm採用BFS選擇路徑，亦即尋找shortest path
$Time\ Complexity:\ O(VE^2)$
$Space\ Complexity:\ O(V)$
```cpp=
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
struct Edge {
int from;
int to;
int flow;
int capacity;
};
class Graph {
private:
int nv, ne, min;
vector<vector<int>> graph;
vector<vector<int>> residual;
vector<int> paths;
vector<Edge> edges;
public:
Graph(int nv = 0, int ne = 0): nv(nv), ne(ne) {
graph.reserve(nv);
residual.reserve(nv);
paths.reserve(nv);
int s, d, c;
for (int i = 0; i < ne; i++) {
cin >> s >> d >> c;
edges.push_back({s, d, 0, c});
edges.push_back({d, s, 0, 0});
graph[s].push_back(edges.size()-2);
residual[d].push_back(edges.size()-1);
residual[s].push_back(edges.size()-2);
}
}
bool findAugmenting() {
// bfs
queue<int> q;
vector<bool> visited(nv, false);
bool found = false;
int now = 0;
for (int& i : residual[now]) {
if (edges[i].capacity > 0)
q.push(i);
}
visited[now] = true;
while (!q.empty()) {
int i = q.front();
q.pop();
now = edges[i].to;
visited[now] = true;
paths[now] = i;
if (now == nv-1) {
found = true;
break;
}
for (int& j : residual[now]) {
if (edges[j].capacity > 0 && !visited[edges[j].to]) {
q.push(j);
}
}
}
return found;
}
int fordFulkerson() {
int v, flow = 0, index;
while (findAugmenting()) {
v = nv-1;
min = INT_MAX;
minCapacity(v);
while (v) {
index = paths[v];
Edge& e = edges[index];
if (index % 2 == 0) {
// exist in origin graph
e.capacity -= min;
e.flow += min;
// add backward edge
edges[index+1].capacity = e.flow;
}
else {
// cancelation
edges[index-1].flow -= min;
edges[index-1].capacity += min;
// decrease bafckward edge capacity
e.capacity = edges[index-1].flow;
}
v = e.from;
}
}
for (int i : graph[0]) {
flow += edges[i].flow;
}
return flow;
}
void minCapacity(int v) {
if (!v)
return;
Edge& e = edges[paths[v]];
if (e.capacity < min) min = e.capacity;
minCapacity(e.from);
}
void printPath(int v) {
if (!v)
return;
Edge& e = edges[paths[v]];
printPath(e.from);
cout << e.from << " " << e.to << " " << e.flow << " " << e.capacity << endl;
}
void printGraph() {
for (int i = 0; i < nv; i++) {
for (int j = 0; j < graph[i].size(); j++) {
cout << edges[graph[i][j]].from << " " << edges[graph[i][j]].to << " " << edges[graph[i][j]].capacity << endl;
}
}
}
};
int main() {
int nv, ne;
cin >> nv >> ne;
Graph g(nv, ne);
cout << g.fordFulkerson() << endl;
return 0;
}
```
> input
> 6 9
0 1 16
0 2 13
1 3 12
2 1 4
2 4 14
3 2 9
3 5 20
4 3 7
4 5 4
> output
23
---
### Reference
---
* Introduction to algorithms 4th edition
>[name=Sky]
###### tags: `Algorithm`
Sign in with Wallet
Connect another wallet