Flow network - 네트워크 플로우

이 글의 목차

인터랙티브

증가 경로, 잔여 간선, 최소 컷

증가자동초기화

유량 네트워크 (유량 / 용량)

증가 경로최소 컷유량

증가를 눌러 첫 번째 증가 경로를 찾으세요.

최대 유량 = 최소 컷

네트워크가 용량에 맞춰 유량을 보낸다

유량 네트워크는 서로 다른 시작점 $s$와 도착점 $t$를 가진 유한 유향 그래프입니다. 원래 간선 $e$에는 유한하고 음이 아닌 용량 $c_e$가 있습니다. 실현 가능한 유량은 각 간선에 양 $f_e$를 할당하여

$$0\le f_e\le c_e$$

를 만족하고, $s,t$ 이외의 모든 정점에서 유입량과 유출량을 같게 하는 것입니다. 유량값 $|f|$는 $s$에서 나가는 순유량이며, $t$로 들어가는 순유량과 같습니다.

끝점이 같은 간선도 각각 별개의 간선입니다. 평행 간선뿐 아니라 역방향 잔여 간선을 다룰 때 중요합니다. 특정 원래 간선에 대응하는 역방향 잔여 간선은 반대 방향으로 향하는 다른 원래 간선과 같은 것이 아닙니다.

잔여 간선: 추가하거나 취소하기

유량 $f_e$가 흐르는 원래 간선 $e=(u,v)$에는 정방향 잔여 간선 $u\to v$와 역방향 잔여 간선 $v\to u$가 생깁니다. 정방향 잔여 용량 $c_e-f_e$는 $e$에 더 보낼 수 있는 양이고, 역방향 잔여 용량 $f_e$는 이미 보낸 유량을 취소할 수 있는 양입니다. 잔여 용량이 양수인 간선만 사용할 수 있습니다.

증가 경로는 잔여 네트워크에서 $s$에서 $t$로 가는 경로입니다. 경로의 잔여 용량 중 최솟값을 $\Delta$라 하면, 정방향 잔여 간선에 대응하는 원래 유량은 $\Delta$만큼 늘리고 역방향 잔여 간선에 대응하는 유량은 그만큼 줄입니다. 병목값만큼만 바꾸므로 용량 조건이 유지됩니다. 경로 안쪽 정점에서는 유입과 유출의 변화가 같아 유량 보존도 유지되고, 유량값은 $\Delta$만큼 증가합니다.

취소는 단순한 계산 편의가 아니라 더 나은 경로를 찾는 데 필요합니다. 용량이 모두 1인 간선 $s\to a$, $a\to b$, $b\to t$, $s\to b$, $a\to t$를 생각합시다. 처음에 $s\to a\to b\to t$로 1을 보낼 수 있습니다. 두 번째 증가 경로는 $s\to b$, $a\to b$의 역방향 잔여 간선 $b\to a$, 그리고 $a\to t$입니다. 이 경로는 앞서 보낸 $a\to b$ 유량을 취소하고 재배치하여 유량값 2를 만듭니다.

컷은 유량의 상한을 인증한다

$s$–$t$ 컷은 정점을 $S,T$로 나누되 $s\in S$, $t\in T$인 분할입니다. 컷 용량에는 원래 간선 중 $S$에서 $T$로 향하는 간선만 합산합니다.

$$c(S,T)=\sum_{e=(u,v):u\in S,v\in T}c_e.$$

$S$의 순유출량을 합하면 내부 간선이 상쇄되어

$$|f|=\sum_{S\to T}f_e-\sum_{T\to S}f_e\le c(S,T)$$

를 얻습니다. 따라서 모든 실현 가능한 유량은 모든 컷의 용량 이하입니다. 위 단위 용량 예시에서 $S=\{s\}$인 컷의 용량은 2이고, 재배치한 유량값도 2이므로 최적임이 인증됩니다. 일반적으로 증가 경로가 더는 없을 때 $s$에서 잔여 도달 가능한 정점들이 컷을 정의합니다. 바깥쪽으로 향하는 원래 간선은 포화되고 반대 방향 간선에는 유량이 없으므로 컷 용량과 현재 유량값이 같습니다. 따라서 현재 유량은 최대입니다.

증가가 언제 끝나는가

증가 경로가 없다는 조건은 최대 유량을 판별하지만, 용량 종류에 관계없이 임의의 경로 선택이 유한 번 만에 그 상태에 도달한다는 뜻은 아닙니다. 영 유량에서 시작하고 용량이 정수이면 포드–풀커슨 알고리즘은 정수 유량을 유지합니다. 매번 정수 유량값이 적어도 1 증가하고, 시작점에서 나가는 총 용량이 유량값의 유한한 상한이므로 종료합니다. 유리수 용량은 공통 분모를 곱해 정수 용량으로 바꾸면 같은 보장이 있습니다. 임의의 실수 용량에서는 경로 선택에 따라 최대값에 유한 시간 안에 도달하지 못하고 증가가 무한히 이어질 수 있습니다.

핵심: 정방향 잔여 간선은 유량을 더하고 역방향 간선은 재배치를 허용합니다. 컷은 더 큰 유량이 불가능함을 보여주는 인증서입니다.