최대 흐름 문제(maximum flow problem)는 어떤 흐름 네트워크(flow network)가 주어졌을 때, 시점에서 종점으로 흐르는 최대 흐름을 찾는 문제입니다. 지난 두 포스트를 통해 우리는 이 문제에서 최대 흐름이 다음과 같은 흥미로운 특징을 갖는다는 것을 알게 되었습니다.
정리 1. 최대 흐름의 잔여 네트워크의 특징
최대 흐름의 잔여 네트워크(residual network)에서는 시점에서 종점으로 도달할 수 없다.
정리 2. 잔여 네트워크의 종점 비도달성의 특징
어떤 흐름의 잔여 네트워크에서 종점이 시점으로부터 도달 불가능할 때, 그것의 흐름양과 동일한 값의 용량을 갖는 절단(cut)을 찾을 수 있다. 그러므로, 이 흐름은 최대 흐름이다.
정리 1의 증명이 궁금하면 아래 글을 참조하세요.
2020/08/29 - [조합론적 최적화/Flow & Circulation] - 최대 흐름 문제 이해하기 (Maximum Flow Problem)
최대 흐름 문제 이해하기 (Maximum Flow Problem)
여러분이 상수도 공사의 직원이라고 해봅시다. 여러분의 업무는 물이 저장된 수원에서 물이 필요한 특정 지역까지 물을 공급하는 것입니다. 물을 공급하는 방법은 수원에서 해당 지역까지 연결
gazelle-and-cs.tistory.com
정리 2의 증명은 아래에서 찾으실 수 있습니다.
2020/08/29 - [조합론적 최적화/Flow & Circulation] - 최대 흐름 최소 절단 정리 (Max-Flow Min-Cut Theorem)
최대 흐름 최소 절단 정리 (Max-Flow Min-Cut Theorem)
저번 글에서는 최대 흐름 문제(maximum flow problem)가 무엇인지 알아 보고 최대 흐름이 만족하는 성질들도 함께 확인해 보았습니다. 최대 흐름 문제가 무엇인지 잘 모르신다면 이전 포스트를 참조하
gazelle-and-cs.tistory.com
정리 1과 2를 통해 우리는 어떤 흐름이 최대 흐름이 되기 위한 필요충분조건을 이끌어낼 수 있죠.
정리 3. 최대 흐름의 필요충분조건
임의의 네트워크에서 어떤 흐름이 최대 흐름이기 위한 필요충분조건은 그 흐름의 잔여 네트워크 위에서 시점에서 종점으로 가는 경로가 존재하지 않는다는 것이다.
이번 시간에는 이를 활용하여 실제로 최대 흐름을 구해 보도록 하겠습니다. 이 글은 다음과 같이 구성되어 있습니다.
- 문제 소개
- 포드-풀커슨 방법(Ford-Fulkerson method)
- 수행 시간 분석
- 용량이 무한한 간선
- 용량이 유리수인 간선
- 용량이 무리수인 간선
이 글의 정의나 용어, 기호 등은 모두 지난 글을 참조하고 있다는 점을 알려 드립니다.
문제 소개
이 글을 처음으로 보시는 분들을 위해서 문제를 간략히 소개하겠습니다. 최대 흐름 문제에서는 어떤 방향 그래프(directed graph) \(G = (V, E) \)와 간선의 용량(capacity) \(c : E \rightarrow \mathbb{R}_+\)으로 이루어진 흐름 네트워크(flow network)가 주어집니다. 일단 이 흐름 네트워크가 다음을 모두 만족한다고 가정하겠습니다.
- \(G\)에는 루프(loop), 평행 간선(parallel edge), 역평행 간선(anti-parallel edge)이 존재하지 않는다.
- \(|E| \geq |V| - 1 \)이다.
- 용량은 유한의 음이 아닌 정수로 주어진다. 다시 말해, 임의의 \(e \in E\)에 대해, \(c(e) < \infty\)이고 \( c(e) \in \mathbb{Z}_+ \)이다.
첫 번째는 일반성을 잃지 않고 가정할 수 있다고 지난 포스트에서 밝혀 두었습니다. 두 번째 가정은 간선의 개수가 정점의 개수만큼은 있다는 것입니다. 그렇지 않다면 네트워크 상에는 외따로 떨어진 정점들이 분명히 존재할 것이고, 그 정점들은 그냥 지워도 괜찮기 때문입니다. 세 번째는 약간 생소한 가정입니다만, 단계적으로 차차 이 가정을 완화해 갈 예정입니다. 그렇게 하면 어떤 현상이 발생하는지 아래에서 알아보도록 하겠습니다.
우리의 목표는 입력과 함께 정해지는 특별한 두 정점, 시점 \(s\)와 종점 \(t\)에 대해 \(s\)에서 \(t\)로 흐르는 흐름(flow) \(f : E \rightarrow \mathbb{R}_+\) 중 흐름양(flow value) \( |f| = \sum_{e \text{ out of } s} f(e) - \sum_{e \text{ into } s} f(e) \)이 가장 큰 것을 찾는 것입니다. 네트워크를 흘러 다니는 유체는 무엇이든 될 수 있겠지만, 이 글에서는 편의를 위해 '물'이라고 부르겠습니다.
포드-풀커슨 방법(Ford-Fulkerson Method)
현재 네트워크에 어떤 흐름 \(f\)가 흐르고 있다고 해 봅시다. 이 흐름을 기준으로 어떤 간선에는 물을 좀더 흘려주고 어떤 간선에서는 물을 빼 주면서 지금보다 더 많은 양의 물을 흘려주는 방법을 찾는 것이 우리가 하고자 하는 일입니다. 이를 위해서 우리는 \(f\)의 잔여 네트워크 \(G_f = (V, E_f), c_f : E_f \rightarrow \mathbb{R}_+\)를 만들었습니다. 간선 집합 \(E_f\)는 다음과 같이 정의되었습니다.
\[ E_f := \{ \langle u, v \rangle : \langle u, v \rangle \in E \text{, } f(u, v) < c(u, v) \} \cup \{ \langle u, v \rangle : \langle v, u \rangle \in E \text{, } f(v, u) > 0 \}. \tag{1} \]
이때, 원래 간선의 방향과 동일한 첫 번째 간선들은 전진 간선(forward edge), 방향이 반대인 두 번째는 후진 간선(backward edge)라고 불렀습니다. 또한, 잔여 용량 \(c_f\)는, 잔여 네트워크의 어떤 간선 \( \langle u, v \rangle \in E_f \)에 대해,
\[ c_f(u, v) = \left\{ \begin{array}{ll} c(u, v) - f(u, v), & \text{if } \langle u, v \rangle \text{ is a forward edge}, \\ f(v, u), & \text{if } \langle u, v \rangle \text{ is a backward edge} \end{array} \right. \tag{2} \]
와 같이 정의되었습니다. 더 자세한 정의는 이전 글을 참조하시면 되겠습니다.
\(G_f\)에서 \(s\)에서 \(t\)로 향하는 단순 경로(simple path)가 있다고 하고 이를 \(P\)라고 부르겠습니다. 그러면 우리는 이 경로를 따라 잔여 네트워크를 흐르는 흐름 \(f_P : E_f \rightarrow \mathbb{R}_+ \)를 만들 수 있습니다. 이때, 이 흐름의 양은 경로 상 가장 작은 용량, 다시 말해,
\[ |f_P| = \min_{e \in P} c_f(e) \tag{3} \]
로 정의 됩니다. 이를 현재 흐름 \(f\)에 적용하여 원래 네트워크에서 흐르는 새로운 흐름 \( f \uparrow f_P : E \rightarrow \mathbb{R}_+ \)를 다음과 같이 만들 수 있었습니다.
\[ f \uparrow f_P (u, v) = \left\{ \begin{array}{ll} f(u, v) + f_P(u, v), & \text{if } \langle u, v \rangle \in P, \\ f(u, v) - f_P(v, u), & \text{if } \langle v, u \rangle \in P, \\ f(u, v), & \text{otherwise.} \end{array} \right. \tag{4} \]
이 과정이 우리에게 도움이 되는 이유는 다음과 같습니다.
정리 4. 증가 경로의 적용
위의 방식으로 만들어진 \(f_P\)와 \(f \uparrow f_P\)에 대해, \(|f_P| > 0\)와 \( |f \uparrow f_P| = |f| + |f_P| \)를 만족한다.
따라서 우리는 \(P\)를 증가 경로(augmenting path)라고 불렀지요. 증명은 똑같이 이전 포스트를 찾아 보시면 됩니다.
이 작업을 \(G_f\)에서 더이상 \(s\)에서 \(t\)에 도달할 수 없을 때까지 반복하면 정리 2에 의해서 그때의 \(f\)가 곧 최대 흐름이 된다는 것을 알 수 있습니다. 이것이 바로 포드-풀커슨 방법(Ford-Fulkerson method)입니다.
Ford-Fulkerson method
입력: 흐름 네트워크 \(G, c\), 시점 \(s\), 종점 \(t\)
출력: 최대 흐름
- \(f \gets 0\)
- \(G_f\)에서 \(s\)에서 \(t\)에 도달할 수 없을 때까지 아래를 반복한다.
- \(G_f\) 위에서 \(s\)에서 \(t\)로 가는 어떤 단순 경로를 \(P\)라고 하자.
- \( f \gets f \uparrow f_P \)
- \(f\)를 반환한다.
이 방법이 어떤 흐름을 반환하면 그 흐름이 최대 흐름이라는 것은 정리 2를 통해서 쉽게 증명할 수 있습니다. 그렇다면 이 방법은 얼마큼의 시간이 필요할까요? 아니 그전에, 이 방법이 끝나기는 할까요?
수행 시간 분석
앞에서 우리는 네트워크의 모든 용량이 음이 아닌 유한의 정수라고 가정하였습니다. 이 경우에는 포드-풀커슨 방법이 언젠간 종료하여 최대 흐름 \(f\)를 반환하게 됩니다. 이 절에서는 이를 증명하도록 하겠습니다.
포드-풀커슨 방법이 시작할 때를 생각해 봅시다. 이때는 \(f = 0\)으로 네트워크에 아무것도 흘리고 있지 않은 상태입니다. 이를 식 2에 그대로 대입하면 원래 네트워크의 용량 \(c\)가 모두 정수라는 가정이 곧장 잔여 네트워크의 용량 \(c_f\)가 모두 정수라는 사실을 알려 줍니다. 만약 \(P\)가 존재하면, 식 3에서 알 수 있듯이 \( |f_P| \)도 정수가 됩니다. 정수들 중에서 가장 작은 값을 뽑아 봐야 정수일 테니까요. 그러면 정리 4를 통해서 다음 흐름의 양 \( |f \uparrow f_P| \)도 정수가 된다는 것을 알 수 있습니다.
그런데 사실은 그보다 더 강한 명제가 참입니다. 식 4를 보면 \( f \)에 \( f_P \)의 값을 더하거나 빼는데, \( P \)가 단순 경로이기 때문에 그 위의 간선은 모두 정확히 \( |f_P| \)의 값을 갖게 됩니다. 따라서 처음에 \(f = 0\)이라는 사실과 함께 \(f \uparrow f_P\)의 모든 값도 정수가 된다는 사실을 알 수 있습니다.
이를 확장하면 다음을 증명할 수 있습니다.
정리 5. 모든 흐름의 정수성
만약 네트워크의 모든 용량이 정수로 주어진다면 포드-풀커슨 방법에서 매번 유지하는 흐름 \(f\)의 모든 값도 정수이다. 따라서 \(|f|\)도 정수이다.
[증명] 수학적 귀납법을 쓰겠습니다. 처음 \(f\)는 모든 간선의 값이 \(0\)이므로 자명합니다. 이제, 단계 2를 시작할 때 \(f\)의 모든 값이 정수라고 가정하겠습니다. 식 2를 통해 \(c_f\)의 모든 값도 정수라는 사실을 알 수 있고 따라서 식 3을 통해 \( |f_P| \)도 정수가 됩니다. 마지막으로 식 4를 통해서 다음 흐름인 \(f \uparrow f_P\)의 모든 값도 정수가 된다는 것을 보일 수 있습니다. □
자, 이제 이 네트워크의 모든 간선의 용량을 더한 것을 \(C = \sum_{e \in E} c(e)\)라고 하겠습니다. 네트워크의 모든 용량이 유한한 값을 갖기 때문에 분명히 \(C\)도 유한한 값을 가집니다. 게다가 네트워크에 아무리 물이 많이 흐른다고 하더라도 간선마다 용량보다 많은 양의 물을 흘릴 수는 없으므로 최대 흐름의 양을 \(F^\star\)라고 했을 때, \(F^\star \leq C\)를 만족합니다. 그런데 정리 4에 의해서 매번 \(|f|\)의 크기는 증가하기만 하고, 정리 5를 통해서 \(|f|\)가 항상 정수라는 것을 보였습니다. 따라서 매 단계마다 최소한 \(1\)씩은 흐름의 양이 증가하게 됩니다. 따라서 우리는 포드-풀커슨 방법의 수행 시간을 다음과 같이 분석할 수 있습니다.
정리 6. 포드-풀커슨 방법의 수행 시간
만약 네트워크의 모든 용량이 정수라면, 포드-풀커슨 방법은 \( O(|E| F^\star) \leq O(|E| C) \) 시간에 동작한다.
[증명] 매 단계를 거칠 때마다 \( |f| \)의 값이 최소 \(1\) 씩은 증가하기 때문에 최대 \( F^\star \leq C \)번 단계 2를 수행합니다. \( |E| \geq |V| - 1 \)이므로 \(G_f\)를 만드는 데 \( O(|E|) \), \(s\)에서 \(t\)로 향하는 경로를 찾거나 도달할 수 없다고 판단하는 데 \( O(|E|) \) 시간이 걸립니다. □
이를 통해 네트워크의 모든 용량이 정수일 때 포드-풀커슨 방법은 언젠간 종료하여 최대 흐름을 출력하고, 그때까지 걸리는 시간은 \( O(|E| C) \)라는 사실을 알았습니다. 얼핏 보기에는 이 시간이 효율적인(efficient) 알고리즘의 기준인 다항 시간(polynomial time)으로 보일 수 있습니다. 하지만 어떤 알고리즘이 다항 시간에 동작한다고 말하려면 주어진 입력의 크기에 다항 배수 이내의 시간에 동작해야 합니다.
그렇다면 입력의 크기는 얼마나 될까요? 엄밀히 말하자면, 이를 메모리에 올린다고 생각했을 때, 몇 개의 비트(bit)면 충분할까요? 간략히 분석하면 다음과 같습니다.
- 간선의 머리(head)와 꼬리(tail)가 무엇인지에 대한 정보는 다 합해서 \(O(|E|)\) 비트면 충분합니다.
- 간선 하나의 용량은 \(C\)를 넘지 못하기에 각 간선의 용량을 이진법으로 표현하면 \( \log_2 C \) 비트면 충분합니다. 따라서 간선의 용량을 모두 표현하기 위해서는 \( O(|E| \log_2 C) \) 비트면 됩니다.
따라서 최대 흐름 문제의 입력의 크기는 \( O(|E| \log_2 C) \) 비트 정도로 표현할 수 있습니다. 그런데 포드-풀커슨 방법의 수행 시간은 \( O(|E| C) \)라고 하였습니다. \( C = 2^{\log_2 C} \)이기 때문에 \( O(|E| C) = O(|E| 2^{\log_2 C}) \)로 쓸 수 있고, 따라서 우리는 포드-풀커슨 방법이 입력 크기의 지수 시간(exponential time)에 동작한다고 말할 수 밖에 없습니다.
이렇게 얼핏 보기에는 다항 시간처럼 보이나 실지로는 지수 시간에 동작하는 알고리즘을 의사 다항 시간 알고리즘(pseudopolynomial-time algorithm)이라고 부릅니다. 따라서 포드-풀커슨 방법은 일종의 의사 다항 시간 알고리즘인 셈이죠. 이에 대한 좀더 엄밀한 정의는 다음 글에서 찾으실 수 있습니다.
2020/06/19 - [근사 알고리즘/Knapsack] - [배낭문제 / Knapsack Problem] 다항 시간 근사 해법 (PTAS)
[배낭문제 / Knapsack Problem] 다항 시간 근사 해법 (PTAS)
지난 포스트에서는 유명한 NP-난해(NP-hard) 문제 중 하나인 배낭 문제(knapsack problem)에 대해서 공부하였습니다. 어떤 문제인지 다시 정의하자면, 우리에게는 물건의 집합 \(I = \{1, \cdots, n\}\)와 배낭�
gazelle-and-cs.tistory.com
그렇다면 과연 이 방법이 진짜로 최악의 경우에는 그 정도의 수행 시간을 필요로 할까요? 만약 위 분석이 매우 허술하다면 더 좋은 분석을 찾아야 할지도 모릅니다. 하지만 안타깝게도, 단계 2-a에서 \(P\)를 매번 "멍청하게" 고른다면 정리 6의 수행 시간이 필요하다는 사실이 잘 알려져 있습니다.
위 그림은 포드-풀커슨 방법이 \( \Omega(|E| C) \) 시간 동작하는 경우를 나타낸 것입니다. 위 그림의 네트워크의 중간에 있는 \( \langle a, b \rangle \) 빼고 나머지 간선의 용량을 모두 어떤 큰 상수 \(x\)로 대체한다면, \(C = 4x + 1\)이 되고, 대신 위 시나리오는 총 \( 2x \approx C/2\) 번 수행될 것입니다.
용량이 무한한 간선
문제를 정의할 때 네트워크에 여러 가정이 붙어 있었습니다. 그중 가장 눈엣가시는 모든 간선의 용량이 유한한 음이 아닌 정수라는 점이었습니다. 이제부터 이 가정을 하나씩 풀어 주면서 어떤 상황이 발생하는지 알아보도록 하겠습니다.
가장 먼저 풀어 줄 가정은 '유한한 용량'입니다. 어떤 간선은 무한히 많은 양의 물이 한번에 흐를 수도 있습니다. 이 정보를 나타내는 것도 간선마다 불리언 플래그(boolean flag) 하나면 충분하니 무한한 용량을 갖는 간선이 있다고 하더라도 입력의 크기는 그렇게 커지지도 않습니다.
하지만 용량이 무한한 간선이 존재한다면 \( C = \sum_{e \in E} c(e) = \infty \)가 되어 정리 6에 의해 포드-풀커슨 방법이 끝나지 않을 수도 있습니다. 당장에 그림 1에서 바깥의 네 간선의 용량이 \( \infty \)일 때 동일한 시나리오를 거치면 포드-풀커슨 방법은 끝나지 않는다는 것을 쉽게 확인할 수 있습니다. 그렇다면 용량이 무한한 간선이 있을 때는 전혀 방도가 없는 것일까요?
다행히도 네트워크에 물이 무한히 흐를 수 있는지 여부를 우리는 쉽게 판단할 수 있습니다.
정리 7. 네트워크에 무한한 양의 흐름이 있을 조건
어떤 흐름 네트워크에 무한히 많은 양의 물이 흐를 필요충분조건은 시점에서 종점까지 무한한 용량의 간선만으로 도달할 수 있는 것이다.
[증명] (\(\Leftarrow\)) 만약 시점에서 종점까지 무한한 용량의 간선만으로 도달할 수 있다면, 그 간선들만으로 이루어진 경로를 찾고, 그 경로를 따라 물을 무한히 많이 흘려주면 됩니다.
(\(\Rightarrow\)) 대우 명제는 다음과 같습니다.
만약 시점에서 종점까지 무한한 용량의 간선만으로 도달할 수 없다면, 이 네트워크에는 무한히 많은 양의 물이 흐를 수 없다.
이를 대신 증명해 보도록 하겠습니다. 위 명제의 조건이 참이라면, 분명 유한한 절단 용량(cut capacity)을 갖는 절단(cut)이 네트워크에 반드시 존재하게 됩니다. 어떤 네트워크든 임의의 흐름의 양은 모든 절단 용량을 넘지 못하기 때문에 이 네트워크의 최대 흐름도 유한한 양이 흐를 수 밖에 없습니다. □
따라서 무한한 용량의 간선이 있다면, 맨 처음에 무한한 용량의 간선들만 가지고 BFS나 DFS를 수행하여 \(s\)에서 \(t\)에 도달할 수 있는지를 따져주면 되겠습니다. 만약 도달이 가능하다면 그 네트워크에는 무한히 많은 물이 흐를 수 있다고 알려주고, 반대로 도달이 불가능하다면 \( |F^\star| \)의 값이 유한하므로 정리 6에 의해 언젠간 포드-풀커슨 방법이 종료하게 됩니다.
정리 8. 무한한 용량의 간선이 있는 네트워크가 입력되었을 때
흐름 네트워크의 모든 간선의 용량이 무한하거나 음이 아닌 정수를 가질 때, 무한히 많은 양의 물이 흐를지 선형 시간에 판단할 수 있고 최대 흐름의 양이 유한하면 포드-풀커슨 방법을 활용하여 최대 흐름을 구할 수 있다.
용량이 유리수인 간선
이번에는 용량이 유리수인 간선이 있다고 가정해 봅시다. 유리수를 소수(小數)로 표현할 수도 있겠지만 엄밀히 유리수는 적당한 정수 \( p, q \in \mathbb{Z} \)에 대해 \( \frac{p}{q}\)로 나타낼 수 있는 수를 의미합니다. 따라서 유리수의 용량을 갖는 간선이 있는 경우에는 일반성을 잃지 않고 그 값들이 모두 분수꼴로 표현되어 있다고 가정해도 괜찮습니다.
따라서 입력된 용량의 분모들의 최소 공배수를 각 용량마다 곱한다면 모든 간선의 용량이 정수면서 원래 네트워크와 동치인 새로운 네트워크를 만들 수 있습니다. 따라서 이렇게 만들어진 네트워크에 대해 포드-풀커슨 방법을 수행하면 되겠습니다.
정리 9. 유리수 용량의 간선이 있는 네트워크가 입력되었을 때
흐름 네트워크의 모든 간선의 용량이 유리수일 때도 포드-풀커슨 방법은 최대 흐름을 반환하며 종료된다.
용량이 무리수인 간선
마지막으로 이번에는 간선이 무리수의 용량을 가질 수 있다고 가정해 보겠습니다. 안타깝지만 이 경우에는 최대 흐름이 유한하지만 포드-풀커슨 방법이 무한 루프에 빠지는 경우가 있습니다. 이번 절에서는 이를 분석해 보겠습니다.
임의의 음이 아닌 정수 \(n \geq 0\)에 대해 다음을 만족하는 어떤 무리수 \(r \geq 0\)을 가지고 옵시다.
\[ r^{n + 2} = r^n - r^{n + 1} \tag{5} \]
정확히는 \( r = \frac{ \sqrt{5} - 1 }{2} > 0 \)이면 위 식을 만족시킵니다. \(r < 1\)이기 때문에 수열 \( \{r^n\} \)의 무한 급수는
\[ \sum_{n = 0}^\infty r^n = \frac{2}{3 - \sqrt{5}} =: S \]
가 됩니다. 이 값을 \(S\)라고 하겠습니다.
이제 다음과 같은 흐름 네트워크 \(G = (V, E)\)와 \(c\)를 정의하겠습니다.
- \( V := \{ s, t, u_1, v_1, u_2, v_2, u_3, v_3, u_4, v_4 \} \)
- \(E\)는 다음과 같다: \( s \)는 \( u_1, \cdots, u_4 \)로 가는 간선만 있고, \( t \)는 \( v_1, \cdots, v_4 \)에서 오는 간선만 있다. 각 \( u_i \)는 \( v_1, \cdots, v_4 \)로 향하는 간선이 있다. 반대로 \( v_i \)는 \( u_i \)를 제외한 나머지 \(u_j\)로 향하는 간선이 있다. 모든 \(v_i\)는 서로 양방향으로 연결되어 있다.
- 정확히 \( c(u_1, v_1) = r^0 \), \( c(u_2, v_2) = r^1 \), \( c(u_3, v_3) = r^2 \), \( c(u_4, v_4) = r^2 \)이며, 나머지 간선은 모두 \(2S\)의 용량을 갖는다.
이 네트워크에는 역평행한 간선이 존재하지만 우리는 쉽게 역평행한 간선이 없는 동치의 네트워크를 만들 수 있습니다. 이는 이전 포스트에서 자세히 설명하였으니 참조하시기 바랍니다.
이 네트워크에서 최대로 흐를 수 있는 양은 \(8S\)입니다. 증명은 따로 하지 않겠습니다만, 어떤 방식으로 절단해도 그것의 절단 용량이 \(8S\)를 넘는다는 것을 쉽게 확인할 수 있습니다. (경우의 수도 그렇게 많지 않으니 직접 해보시는 것도 좋겠죠. 하하. 그냥 믿으세요.)
이제 포드-풀커슨 방법이 "멍청하게" 동작하는 시나리오를 보여드리겠습니다.
순번 1. 처음에는 \( P = \langle s, u_1, v_1, t \rangle \)를 취합니다. \( |f_P| = r^0 \)이며, 따라서 다음 \( f \)의 흐름양도 \(r^0\)입니다.
순번 2. 이제부터 귀납적으로 이 순번이 \( t \) 번째 (단, \(t = 1, 2, \cdots\)) 수행되기 시작할 때, \(G_f\)는
\[ \{ c_f(u_1, v_1), \cdots, c_f(u_4, v_4) \} = \{ 0, r^t, r^{t+1}, r^{t+1} \} \]
을 만족한다고 가정하겠습니다. 순번 1이 끝난 후 처음 이 순번이 시작할 때 위 조건을 만족한다는 것을 쉽게 확인할 수 있습니다. 편하게 표기하기 위해 정점들의 순서를
\[ c_f(u_1, v_1) = 0, \quad c_f(u_2, v_2) = r^t, \quad c_f(u_3, v_3) = c_f(u_4, v_4) = r^{t+1} \]
을 만족하도록 바꿔주겠습니다.
순번 3. 이때 \( P = \langle s, u_2, v_2, u_3, v_3, t \rangle \)를 취하겠습니다. 그러면 \(P\) 위에서 가장 작은 용량은 \( c_f(u_3, v_3) = r^{t + 1} \)이 되며, 따라서 \( |f_P| = r^{t + 1} \)이고, 현재 흐름의 양도 그만큼 증가하게 됩니다.
\(f_P\)를 따라 증가시킨 후에는 \(G_f\)가 다음을 만족하게 됩니다.
\[ c_f(u_1, v_1) = c_f(u_3, v_3) = 0, \quad c_f(u_2, v_2) = r^t - r^{t + 1} = r^{t + 2}, \quad c_f(u_4, v_4) = r^{t + 1} \]
특히 \( c_f(u_2, v_2) \)가 \( r^{t + 2} \)인 이유는 \(r\)이 식 5를 만족하기 때문입니다.
순번 4. 이제 다음과 같이 좀 긴 \(P\)를 잡겠습니다.
\[ P = \langle s, u_2, v_2, v_1, u_1, v_3, u_3, v_4, t \rangle \]
이 경로의 병목은 \( c_f(u_2, v_2) = r^{t + 2} \)이며 따라서 흐름의 양은 \( r^{t + 2} \)만큼 증가하게 됩니다.
그러면 \(G_f\)에서 중요한 간선들은 다음과 같은 잔여 용량을 갖게 됩니다.
\[ c_f(u_1, v_1) = c_f(u_3, v_3) = r^{t + 2}, \quad c_f(u_2, v_2) = 0, \quad c_f(u_4, v_4) = r^{t + 1} \]
이는 순번 2에 들어가게 될 조건을 만족하게 됩니다.
따라서, 순번 2가 \(t\) 번째 수행될 때마다 포드-풀커슨 방법은 \( r^{t + 1} + r^{t + 2} \)씩 증가시키게 되고, 따라서 아무리 노력해도 이 방법이 유지하는 흐름의 양은
\[ r^0 + \sum_{t = 1}^\infty [ r^{t + 1} + r^{t + 2} ] < 2S \]
를 넘지 못하게 됩니다. 이는 최대 흐름의 양인 \(8S\)에 한참 미치지 못하는 양이죠. 게다가 포드-풀커슨 방법 자체가 끝나지도 않는다는 더 큰 문제도 함께 가지고 있습니다.
정리 10. 무리수 용량의 간선을 갖는 네트워크가 입력되었을 때
흐름 네트워크의 간선에 무리수가 있을 때, 포드-풀커슨 방법은 끝나지 않을 수도 있으며, 아무리 시간을 투자해도 최대 흐름에 한참 미치지 못하는 흐름만 유지할 수도 있다.
마치며
이것으로 흐름 네트워크에서 최대 흐름을 찾는 방법인 포드-풀커슨 방법에 대해서 알아 보았습니다. 정리하자면, 포드-풀커슨 방법은 무한한 용량을 갖는 간선이나 유리수 용량 갖는 간선이 있을 때까지는 문제 없이 최대 흐름을 찾아줄 수 있지만, 간선의 용량에 무리수를 허용하는 경우에는 제대로 동작하지 않을 수 있습니다.
사실, 무리수의 용량을 가정하는 것은 약간 무리가 따르기도 합니다. 왜냐하면 컴퓨터는 결국 셀 수 있는(countable) 것들만 제대로 표현할 수 있기 때문입니다. 실례로 컴퓨터가 \(0\)과 \(1\) 사이의 모든 실수를 절대로 표현할 수 없다는 것은 잘 알려진 사실입니다. 때문에 많은 경우 우리는 입력을 유리수로 한정하는 경우가 많습니다. 그럼에도 혹여나 무리수를 제대로 다룰 수 있는 컴퓨터가 있다고 가정했을 때 여전히 최대 흐름 문제를 잘 해결하는 방법이 있는지 궁금하실 겁니다.
수행 시간도 큰 문제입니다. 이 방법은 유한의 정수만 입력받은 때에도 최악의 경우 입력의 지수 시간동안 동작했습니다. 이와 같은 상황들이 발생하게 된 가장 큰 이유는 증가 경로 \(P\)를 아무거나 고를 수 있었기 때문입니다. 이 때문에 많은 사람들이 (그리고 이 글에서도) 포드-풀커슨 방법을 '알고리즘(algorithm)' 대신 '방법(method)'이라고 부릅니다. (물론 포드-풀커슨 알고리즘이라고 부르기도 합니다. 당장에 위키피디아에는 알고리즘으로 적혀 있더군요.)
따라서 "좋은" \(P\)를 찾는다면 이 방법을 획기적으로 개선시킬 수 있을 겁니다. 다음에는 이에 대해서 알아 보도록 하겠습니다.
궁금하신 점이 있으시거나, 글에 오류가 있는 경우에는 알려주시기 바랍니다. 긴 글 읽어 주셔서 감사합니다. :)
참조
[1] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to algorithms. MIT press, 2009. (a.k.a. CLRS)
[2] Lester R. Ford Jr and Delbert R. Fulkerson. Flows in networks. Princeton university press, 2015.
[3] http://www.cs.cornell.edu/courses/cs6820/2016fa/handouts/flows.pdf
'조합론적 최적화 > Flow & Circulation' 카테고리의 다른 글
| 서큘레이션 (Circulation) (0) | 2023.12.23 |
|---|---|
| 디니츠의 알고리즘 (Dinitz' Algorithm) (6) | 2021.02.27 |
| 에드몬즈-카프 알고리즘 (Edmonds-Karp Algorithm) (6) | 2021.02.21 |
| 최대 흐름 최소 절단 정리 (Max-Flow Min-Cut Theorem) (7) | 2020.08.29 |
| 최대 흐름 문제 이해하기 (Maximum Flow Problem) (13) | 2020.08.29 |
