플로우 네트워크와 실현 가능한 유량
플로우 네트워크는 서로 다른 시작점(source) $s$와 싱크(sink) $t$를 지정한 유한 유향 그래프 $G=(V,E)$이다. 각 간선 $e$에는 유한한 음이 아닌 용량 $c_e$가 주어진다. 끝점이 같더라도 간선은 서로 구별되는 객체로 취급한다. 이는 평행 간선이나 서로 반대 방향인 간선이 있을 때 중요하다.
유량은 원래 그래프의 각 간선 $e$에 실수 $f_e$를 할당하는 것이다. 다음 용량 조건을 만족하고
\[0\le f_e\le c_e \qquad(e\in E)\]$s,t$ 이외의 모든 정점에서 유입 유량과 유출 유량이 같으면 그 유량은 실현 가능하다.
\[\sum_{e:\,\operatorname{head}(e)=v} f_e =\sum_{e:\,\operatorname{tail}(e)=v} f_e \qquad(v\in V\setminus\{s,t\}).\]실현 가능한 유량의 값은 시작점에서 나가는 순유량으로 정의한다.
\[|f|=\sum_{e:\,\operatorname{tail}(e)=s} f_e -\sum_{e:\,\operatorname{head}(e)=s} f_e.\]시작점과 싱크를 제외한 모든 정점에서의 유량 보존을 합하면, 이는 싱크로 들어오는 순유량과 같음을 알 수 있다.
\[|f|=\sum_{e:\,\operatorname{head}(e)=t} f_e -\sum_{e:\,\operatorname{tail}(e)=t} f_e.\]따라서 $s$로 들어오는 간선이나 $t$에서 나가는 간선이 있을 때, 유량의 값은 단순히 $s$에서 나가는 유량 또는 $t$로 들어오는 유량의 합이 아니다.
잔여 간선과 잔여 네트워크
실현 가능한 유량 $f$가 주어졌을 때 원래 간선 $e=(u,v)$ 하나는 원래 간선에 대한 표시를 각각 붙인 잔여 간선을 최대 두 개 만든다.
- 정방향 잔여 간선 $(u,v,e,+)$의 잔여 용량은 $c_e-f_e$이다. 이는 $e$를 따라 추가로 보낼 수 있는 유량을 나타낸다.
- 역방향 잔여 간선 $(v,u,e,-)$의 잔여 용량은 $f_e$이다. 이는 $e$에 이미 흐르는 유량을 줄여 취소하거나 되돌릴 수 있는 양을 나타낸다.
잔여 용량이 양수인 간선만 잔여 네트워크에서 사용할 수 있다. 잔여 간선은 원래 그래프의 간선과 혼동해서는 안 된다. 특히 $e=(u,v)$에 속하는 역방향 잔여 간선은 반대 방향 $v\to u$로 향하는 원래 간선과 별개다. 원래 간선이 양방향으로 존재한다면 각 원래 간선은 자신의 정방향 및 역방향 잔여 간선을 각각 만든다.
모든 실현 가능한 유량의 상한인 컷
$s$–$t$ 컷은 $V=S\mathbin{\dot\cup}T$, $s\in S$, $t\in T$를 만족하는 분할이다. 컷 용량은 $S$에서 $T$로 향하는 원래 간선들의 용량 합이다.
\[c(S,T)=\sum_{e=(u,v)\in E:\,u\in S,\ v\in T}c_e.\]임의의 실현 가능한 유량에 대해 $S$에 속한 정점들의 순유출량을 합하면
\[|f|=\sum_{e=(u,v)\in E:\,u\in S,\ v\in T}f_e -\sum_{e=(u,v)\in E:\,u\in T,\ v\in S}f_e \le c(S,T)\]를 얻는다. 따라서 모든 실현 가능한 유량은 모든 $s$–$t$ 컷의 용량 이하이다.
증가 경로
| 증가 경로는 잔여 네트워크에서 양의 잔여 용량을 가진 간선만 따라 $s$에서 $t$까지 가는 경로이다. 경로의 병목 용량은 경로에 속한 잔여 간선들의 잔여 용량 중 최솟값이다. 이 최솟값을 $\Delta$로 하여 유량을 증가시킨다. 경로의 각 정방향 잔여 간선이 원래 간선 $e$에 속하면 $f_e$를 $f_e+\Delta$로 바꾸고, 역방향 잔여 간선에 속하면 $f_e$를 $f_e-\Delta$로 바꾼다. 이렇게 얻은 유량은 모든 용량 조건과 중간 정점의 유량 보존을 만족하며, 값은 $ | f | +\Delta$가 된다. |
실현 가능한 유량이 최대 유량일 필요충분조건은 그 유량의 잔여 네트워크에 $s$에서 $t$로 가는 증가 경로가 없는 것이다. 이는 원래 그래프가 아니라 현재 유량의 잔여 네트워크에 대한 조건이다. 증가 경로가 있으면 양의 병목 용량만큼 유량을 늘려 더 큰 실현 가능 유량을 만들 수 있다. 반대로 증가 경로가 없으면 양의 잔여 용량 간선만 따라 $s$에서 도달 가능한 정점들이 $s$–$t$ 컷을 이룬다. 이 컷을 가로질러 바깥으로 향하는 원래 간선은 용량까지 사용되었고, 반대 방향 간선에는 유량이 흐르지 않는다. 따라서 유량의 값이 그 컷의 용량과 같으므로 더 큰 유량은 존재할 수 없다.
이 조건은 최적성을 판정하지만, 증가 경로를 고르는 모든 절차가 유한 번 만에 종료한다는 뜻은 아니다. 영 유량에서 시작하고 용량이 정수이면 포드–풀커슨 알고리즘의 각 증가는 정수 유량을 유지하고 정수인 유량 값을 적어도 1씩 늘린다. 유량 값은 시작점에서 나가는 유한한 총 용량으로 제한되므로 알고리즘은 종료한다. 유리수 용량도 공통 분모를 곱해 정수 용량으로 바꿀 수 있으므로 같은 보장이 성립한다. 임의의 실수 용량에서는 경로 선택에 따라 최대 유량에 도달하지 못한 채 증가가 무한히 계속될 수 있다.