Introduction to Algorithm 4th edition을 번역 및 정리한 글입니다.

1. 포드-풀커슨 방법 분석

이전 글에서 다뤘던 최대 유량 최소 컷 정리와 포드-풀커슨 방법의 pseudo-code를 다시 보자.

최대 유량 최소 컷 정리

f가 소스 s, 싱크 t를 가지는 유량 네트워크 G=(V,E)의 흐름이라 하자. 다음의 세 조건은 서로 동치다.
1. $f$가 $G$의 최대 유량이다.
2. 잔여 네트워크에 $G_f$​ 증가 경로가 존재하지 않는다.
3. $G$의 어떤 컷 $(S,T)$에 대해, $|f∣=c(S,T)$ 다.

포드-풀커슨 방법의 pseudo-code

FORD-FULKERSON(G, s, t)
  for each edge $(u, v) \in G.E$
    $(u, v).f = 0$
  while there exists a path $p$ from $s$ to $t$ in the residual network $G_f$
    $c_f(p) = min\{c_f(u, v) : (u, v) \text{ is in } p\}$
    for each edge $(u, v)$ in $p$
      if $(u, v) \in G.E$
        $(u,v).f = (u, v).f + c_f(p)$
      else $(v, u).f = (v.u).f - c_f(p)$
return $f$

이 pseudo-code는 최대 유량 최소 컷 정리에 따라, while문이 종료하는 경우, 다시 말해 더 이상 $s$에서 $t$로의 증가 경로를 찾을 수 없는 경우 최대 유량을 반환한다.

문제는 어떤 경우 while 문이 끝나지 않는 경우가 발생할 수 있다는 것, 즉 계속해서 증가 경로를 찾는 데 성공하는 경우가 있을 수 있다는 점, 게다가 이때 흘려보내는 유량이 구하고자 하는 최대 유량에 수렴조차 하지 않는 경우가 있을 수 있다는 점이다.

2.무리수 용량 간선이 포함된 경우의 무한 루프 사례 (링크)

다음을 만족하는 수열 $\{a_n\}$을 생각해보자.

$r = (\sqrt{5} - 1)/2$는 위를 만족하니 이 값을 쓰도록 하자.

이제 아래와 같은 네트워크를 보자.

이때 $e_1, e_2, e_3$의 용량은 각각 $a_0 = 1, a_1 = r, 1$이고, 나머지 간선의 용량은 모두 어떤 큰 정수 $M \geq 4$라 하자. 위 네트워크의 최대 유량은 $2M + 1$이 된다.

여기서 잠깐 간선 $e_1, e_2, e_3$의 잔여 용량이 각각 $a_n, a_{n + 1}, 0$인 경우를 생각해보자.

만약 네트워크의 증가 경로에 $e_1, e_2, e_3'$($e_3'$를 $e_3$의 역방향 잔여 간선이라고 하자)가 있고, $e_2$가 핵심 간선(critical edge), 즉 경로 상에서 잔여 용량이 가장 작은 간선이라면, 이 경로를 따르는 흐름은 $c_f(e2) = a_{n + 1}$이 될 것이다.

이 흐름은 $e_1, e_2$에 $a_{n+1}$만큼의 흐름을 더하고, $e_3$에서는 $a_{n + 1}$만큼의 흐름을 덜어내기에, $e_1, e_2, e_3$의 잔여 용량은 각각 $a_n - a_{n + 1} = a_{n + 2}, 0, a_{n+1}$로 바뀐다.

이제 다음과 같은 세 경로 $p_1, p_2, p_3$를 생각해보자. $p_1$은 앞서 설명한 경우와 같다.

여기서 다음의 경로를 따라 1의 유량이 흘렀다고 해보자.

이제 $e_1, e_2, e_3$의 잔여 용량은 각각 $a_0, a_1, 0$이 된다.

간선 $e_1, e_2, e_3$의 잔여 용량이 각각 $a_n, a_{n + 1}, 0$이고, 나머지 간선들의 잔여 용량은 적어도 1은 된다고 해보자. 이때 경로 $p_1$의 핵심 간선은 $e2$이고, 이 경로를 따랐을 때 각 간선의 잔여 용량은 $a_{n + 2}, 0, a_{n + 1}$로 변하고, 흐름의 값은 $|f|$에서 $|f|$ + $|c_f(e2)|$로 증가했다.

이 상태에서 경로 $p_2$를 골라보자. 이 간선의 핵심 간선을 찾아보면 $e_3$가 되고, 그 잔여 용량은 $a_{n+ 1}$이다. 이를 따라 흐름을 보냈을 때 간선 $e_1, e_2, e_3$의 잔여 용량은 $a_{n + 2}, a_{n + 1}, 0$이 된다. 이후로도 $e1$을 핵심 간선으로 가지는 $p1$, $e3$를 핵심 간선으로 하는 $p_3$를 골라 유량을 흘려 보내면, $e_1, e_2, e_3$는 다시 $(a_{n}, a_{n + 1}, 0)$ 꼴의 잔여 용량을 가지게 된다.

위와 같은 네 번의 증가를 통해 유량은 $2a_n + 2a_{n+1} = 2a_{n - 1}$만큼 증가한다.

다시 1의 유량을 흘려보내 $e_1, e_2, e_3$의 잔여 용량이 각각 $a_0, a_1, 0$이 됐을 때를 보자. 위와 같이 증가 경로를 택해 흐름을 보내면 무한 루프에 빠질 뿐만 아니라, 그 수렴값도 $1 + 2\sum_{n = 2}^{\infty}a_n = 3$ 정도로 , 앞서 찾았던 최대 유량 $2M + 1$에는 한참 못 미치게 된다.

3. 유리수 용량 간선만이 주어진 경우

그래도 보통 최대 유량 문제에서는 정수 용량의 간선들을 사용하고, 그렇게 정수 용량의 간선들만 있는 경우, 포드-풀커슨 방법은 무한 루프 없이 최대 유량을 반환할 수 있음이 보장된다. 간선의 용량이 정수가 아니라 유리수로 주어지는 경우에도, 간선들의 용량에 적절한 정수를 곱해 정수로 만들 수 있으니 포드-풀커슨 방법을 사용해 최대 유량을 구할 수 있다.

이전 글에 나왔던 두 정리를 다시 보자.

Lemma 2

유량 네트워크 $G = (V, E)$와 흐름 $f$를 생각하자. $p$가 $G_f$의 증가 경로라 할 때, $f_p : V \times V \rightarrow \mathbb{R}$를 다음과 같이 정의하면, $f_p$는 $|f_p| = c_f(p) > 0$인 $G_f$의 흐름이다.

$f_p(u, v) = \begin {cases} c_f(p) & \text{if } (u,v)\ \text{is on } p, \\ 0 & \text{otherwise.} \end {cases}$

Corollary 1

$G = (V, E)$가 유량 네트워크고, $f$를 $G$의 흐름, $p$는 $G_f$에서의 증가 경로라 하자. $f_p$가 위에 정의된 것과 같고, $f$가 $f_p$만큼 증가하는 경우, 함수 $f \uparrow f_p$는 값 $|f \uparrow f_p| = |f| + |f_p| > |f|$을 가지는 $G$의 흐름이다.

Corollary 1에서 포드-풀커슨 방법의 매 스텝을 거칠 때마다 흐름의 값은 $|f_p|$만큼 증가한다. 이때 주어진 간선들의 용량이 모두 정수이므로, 만약 $|f|$가 정수라면 경로의 잔여 용량 $c_f(p)$ 또한 정수가 될 수 밖에 없고, 따라서 $|f_p|$도 정수다. 맨 처음 시작할 때 유량은 $f = 0$이므로, 모든 스텝에서 흐르는 유량은 정수들이다.

$f^*$가 네트워크의 최대 유량이라고 하자. 모든 간선이 정수 용량을 가지므로 $|f^*|$도 정수가 될 수 밖에 없다. 매 스텝마다 흐름의 값이 적어도 1 이상의 정수만큼 증가하므로, 최대 $|f^*|$ 번 만큼 유량을 1씩 반복해서 증가시키면 최대 유량에 도달할 수 있다.

(1) 정수 용량 네트워크에서의 포드-풀커슨 시간 복잡도

유량 네트워크 $G = (V, E)$가 주어졌다고 하자. 흐름 $f$가 주어졌을 때, 잔여 네트워크 $c_f$에는 최대 $2|E|$개의 간선이 있을 수 있으므로, DFS, 혹은 BFS를 사용해 $c_f$에서 증가 경로를 찾는 데 걸리는 시간은 $O(|V| + 2|E|) = O(|E|)$가 된다.

앞서 $f^*$가 네트워크의 최대 유량일 때, 최대 $|f^*|$번 증가가 이루어질 수 있다고 했으므로, 전체 시간복잡도는 $O(|E||f ^*|)$가 된다. 최대 유량일 때의 값 $|f^*|$이 충분히 작을 때에야 괜찮겠지만, $|f^*|$가 상당히 크고, 매번 유량이 1씩 증가하도록 증가 경로를 찾게 되는 경우, 이 시간복잡도는 실제로 사용하기에는 상당히 부담스러워진다.

위 유량 그래프의 최대 유량은 $2,000,000$이다. $s \rightarrow u \rightarrow v \rightarrow t$로 1의 유량이 흐른 후, $s \rightarrow v \rightarrow u \rightarrow t$로 1의 유량이 흘렀다고 해보자. 이후로도 계속 $s \rightarrow u \rightarrow v \rightarrow t$, $s \rightarrow v \rightarrow u \rightarrow t$의 증가 경로를 고르는 경우, 유량을 1씩 증가시키기를 $2,000,000$번 반복하게 된다.

• Thomas H. Cormen et al. Introduction to Algorithms, Fourth Edtion, 2022, Pages 686-689, ISBN: 9780262046305
• Uri Zwick, The smallest networks on which the Ford-Fulkerson maximum flow procedure may fail to terminate, Theoretical Computer Science, Volume 148, Issue 1, 1995, Pages 165-170, ISSN 0304-3975, https://doi.org/10.1016/0304-3975(95)00022-O. (https://www.sciencedirect.com/science/article/pii/030439759500022O