# Definition
A flow network (also known as a transportation network) is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge
reference
플로우 네트워크 G는 모든 간선이 용량과 유량의 속성을 가지는 그래프이며 유량은 항상 용량을 초과할 수 없다.
# Term Definition
## Flows ##
flow를 정의하는 방법(notation)은 다양하다. 이 중 가장 직관적이며 대표적인 의사-유량(pseudo-flow라서 대충 의사-유량으로 번역하겠다)의 notation은 다음과 같다.
pseudo-fow는 함수 $f: \ V \times V \Rightarrow \mathbb{R}$ 이며
$\forall u, v \in V$에 다음과 같은 성질을 만족한다.
1) Capacity constraints
2) Skew symmetry
3) Flow conservation
4) Value(f)
1.
1번의 성질은
$\forall(u, v) \in E:$ $f(u, v) \leq c(u,v)$
으로기본 공리같은 느낌이며 직관적으로도 자명하다.
2.
Skew symmetric 하다는 것은 Skew-symmetric matrix과 같은 형식으로 표현 할 수 있다는 것이다.
Skew-symmetric matrix란 $A^T = -A$를 만족하는 Square matrix(정방행렬)을 의미한다.
(이에 따라 $f_{uu} = 0$도 성립하게 된다)
이와 비슷하게 flow에 대해서도 다음과 같은 성질이 성립한다.
$f_{uv} = -f_{vu}$
정점 u에서 v로 유량이 흐르것과 v에서 u로 같은 양의 다른 부호의 유량이 흐르는 것을 동치로 취급할 수 있게 되면 flow analysis의 직관성, 논리의 흐름이 굉장히 깔끔해진다(예를 들어 유량을 더 흘려보내주는 과정에서 $f_{uv}$와 $f_{wx}$가 각각 $\Delta f_{uv}$만큼 감소, $\Delta f_{uv}$만큼 증가하는 경우를 생각해보자. $f_{uv}-\Delta f_{uv}$, $f_{wx}+\Delta f_{wx}$로 표현한다면 표현의 통일성이 없고 $\Delta f(s, t)$의 값의 표현이 깔끔하지 않은 반면 성질 2를 이용하여 표현한다면 $f_{uv}+\Delta f_{vu}$, $f_{wx}+\Delta f_{wx}$로 통일성 있게 표현되기에 $\Delta f(s, t)$의 표현도 깔끔해진다.)
혹여 $u$에서 $v$로 $E_{uv} = 6$, $v$에서 $u$로 $E_{vu} = 2$인 경우 $f_{uv} = -f_{vu}$가 성립 안하는게 아니냐 라고 생각 하시는 분들을 위하여
flow analysis에서 논리의 흐름을 위하여 $f_{uv}$는 단순히 u에서 v로 직접적으로(다른 정점을 거치지 않고) 흐르는 유량 뿐만 아닌 가능한 모든 경로에 대한 유량의 합을 뜻한다.
다시 말하자면 모든 $u \Rightarrow v$로 갈 수 있는 경로들의 집합 $P(u,v) = \left\{p \ \mid \ p \colon \ path \ from \ u \ to \ v \right\}$에 대해서 유량 $f_{uv}$ $=\displaystyle\sum_{path \ p \in P} f(p)$으로 표현 할 수 있다.
따라서 $u$에서 $v$로 $E_{uv} = 6$, $v$에서 $u$로 $E_{vu} = 2$인 경우 $f_{uv} = 6 -2 = 4 = -(2 - 6) = -f_{vu}$이 성립하게 되는 것이다.
3.
Flow conservation은 정점 $v$로 들어오는 유량의 합의 절댓값과 나가는 유량의 합은 동일 하다는 성질이다.
$f_{v_{in}}=f_{v_{out}}$
$f_{v_{in}} = \displaystyle\sum_{u: (u, v) \in E} f_{uv}$ $= \displaystyle\sum_{u: (u, v) \in E} -f_{vu}$ $= \displaystyle\sum_{w: (w, v) \in E} -f_{vw}$ $=f_{v_{out}}$
를 얻을 수 있다.
4.
네트워크에서 유량의 값(value of flow)에 관한 성질이며 다음과 같다.
$|f| = f_{s_{out}} = f_{t_{in}}$
s에서 직접적으로(다른 정점을 거치지 않고) 연결되어있는 점들의 집합을 $DS=\left\{u\ | \ u: \ directly \ connected \ from \ s\right\}$라고 하자.
Flow conservation에 의해
$\displaystyle\sum_{u \in V, u \neq (s, t)}f_{u_{in}} - f_{u_{out}} = 0$
$\Rightarrow$ $0 = \displaystyle\sum_{u \in V, u \neq (s, t)}(\displaystyle\sum_{v: v \Rightarrow u} f_{vu}- \displaystyle\sum_{w: u \Rightarrow v} f_{uw})= 0$
$=\displaystyle\sum_{(u, v) \in V, u, v \neq (s, t)}f_{uv} - f_{uv}$ $+\displaystyle\sum_{u: s\Rightarrow u}f_{su}$ $-\displaystyle\sum_{u: u\Rightarrow t}f_{ut}
$=0$+\displaystyle\sum_{u: s\Rightarrow u}f_{su}$ $-\displaystyle\sum_{u: u\Rightarrow t}f_{ut}
$= f_{s_{out}} - f_{t_{in}}$
$\therefore f_{s_{out}} = f_{t_{in}}\ Q.E.D$
## Residual capacity ##
The residual capacity of an arc with respect to a pseudo-flow $f$, denoted $c_{f}$, is the difference between the arc's capacity and its flow. That is, $c_{f} (e) = c(e) - f(e)$
reference
잔류 용량이란 $c_{f}$으로 표기하며 얼마만큼의 유량이 더 흐를 수 있는지를 뜻한다. 용량이 유량의 최댓값이므로 잔류 용량은 $c_{f} (e) = c(e) - f(e)$으로 표현된다.
## Residual network ##
A residual network, denoted $G_{f} (V, E_{f})$, which models the amount of available capacity on the set of arcs in $G = (V, E)$
reference
잔류 네트워크란 잔류 용량에 초점을 맞추어 구성한 그래프이다. $G=(V,E)$라면 간선 $E_{uv} = $c_{f}(u, v)$로 표현 된다.
## Augmenting paths ##
An augmenting path is a path $(u_{1}, u_{2}, ..., u_{k})$ in the residual network, where $u_{1} = s, u_{k} = t$, and $c_{f} (u_{i}, u_{i} + 1) > 0. A network is at maximum flow if and only if there is no augmenting path in the residual network $G_{f}$.
reference
Augmenting path는 번역하면 증가 경로정도가 되겠다. 잔류 네트워크 $G_{f}$에 대해서 $s$에서 출발하여 $t$로 흐를 수 있는 경로가 Augmenting path이다.
경로는 다음과 같이 표현 할 수 있다.
$(u_{1}, u_{2}, ..., u_{k})$ $\subset G$,$u_{1} = s, u_{k} = t$, $c_{f} (u_{i}, u_{i} + 1) > 0$
증가 경로가 존재한다면 유량 $|f(G_{f})|$은 최댓값이 아니며 증가 경로가 존재하지 않을때 $|f(G_{f})|$이 최댓값, 즉 maximum flow가 된다. 역 또한 성립한다. 이의 증명은 Ford–Fulkerson algorithm의 포스팅에서 기술하겠다.