최근 유량 알고리즘들을 공부해 봤는데, 정리와 증명이 명확하게 정리된 블로그가 잘 없는 것 같아서 정리한다.
* 모바일 환경에서 레이텍이 깨지는 현상이 있는 것 같다. 구글 크롬의 경우, 우측 상단의 점 세 개를 눌러 메뉴를 열고 "데스크톱 보기"를 활성화하는 것으로 해결할 수 있다.
0. 용어 정의
다음과 같이 그래프, 소스 정점, 싱크 정점, 용량 함수가 주어졌다고 하자.
graph $G=(V, E)$, source $s \in V$, sink $t \in V (s \ne e)$, 용량 함수 $c : V \times V \longmapsto \mathbb{R}^{+}$
(수학에서는 이 네 요소 $(G, c, s, t)$를 flow network라 한다.)
이때, $G$의 소스에서 싱크로 물건을 옮기는 상황을 생각해 보자. 각 간선으로 옮겨질 수 있는 물건의 갯수는 용량 함수(capacity function)를 초과할 수 없다. 이 조건을 만족하며 물건을 옮길 때, 각 간선을 통해 옮겨지는 물건의 수가 유량 함수(flow function)이다.
flow 함수 $f : V \times V \longmapsto \mathbb{R}$는 다음 조건을 만족하는 함수이다.
1. 모든 $(u, v) \in E$에 대하여, $f(u, v) \le c(u, v)$ (용량 제한) : 모든 간선에서 유량은 용량 제한을 초과할 수 없다.
2. 모든 $(u, v) \in E$에 대하여, $f(u, v) = -f(v, u)$ (skew symmetry) : 역방향으로 나가는 유량은 원래 flow의 -1배이다.
3. $s$나 $t$가 아닌 모든 $v \in V$ 에 대하여 $\sum_{(v, u) \in E}{f(v, u)} = 0$ : 소스, 싱크를 제외하면 들어오는 flow(부호가 +)와 나가는 flow(부호가 -)의 합은 같다.
2번 조건은 $u$에서 $v$로 양의 flow가 흐를때, $v$에서 $u$로는 절댓값은 같고 부호가 반대인 flow가 흐른다는 식으로 이해하면 좋다. 전자기학에서 두 지점의 위치를 바꾸면 전압이 부호만 바뀌는 것과 유사하다.
이때, flow의 value는 소스에서 나가는 유량의 총합, $\sum_{(s, u) \in E}{f(s, u)}$로 정의된다. 또한 $|f|$로 쓴다.
Maximum flow 문제는 그래프, 소스, 싱크, 용량 함수가 주어졌을 때 flow의 값이 최대인 flow를 찾는 문제이다.
1. Ford-Fulkerson 알고리즘
위의 유량 정의를 생각하면, 다음과 같은 그리디 알고리즘을 생각할 수 있을 것이다.
Algorithm 1. Ford-Fulkerson's Maximum Flow Algorithm
입력 : 그래프, 소스 정점, 싱크 정점, 용량 함수
초깃값 : flow function $f$, $f(u, v)=0$ for all $(u, v) \in E$
1. residual flow $r : V \times V \longmapsto \mathbb{R}$를 $r(u, v)=c(u, v)-f(u, v)$를 만든다. 이 함수는 수식에서도 볼 수 있듯이 $u$에서 $v$로 더 흐를 수 있는 flow를 나타내는 함수이다.
2. 다음 조건을 만족하는 경로 $v_1, \cdots v_k$를 찾는다. $v_1=s, v_k=t$, 모든 $1\le i < k-1$인 $i$에 대해 $r(v_i, v_{i+1})>0$.
flow를 흐르게 할 수 있는 경로를 찾는다. 이를 augmenting path라 하자. 즉, augmenting path가 있다면 augmenting path에 있는 간선들의 flow를 증가시켜 전체 flow의 값을 증가시킬 수 있을 것이다.
3. augmenting path를 이루는 모든 간선 $(v_i, v_{i+1})$에 대하여, $f(v_i, v_{i+1})$을 $min(r_(v_i, v_{i+1}))$만큼 증가시킨다.
4. augmenting path를 찾을 수 없을 때까지 1-3을 반복한다.
위 알고리즘의 정당성 증명은 뒤로 미루고, 시간 복잡도부터 구해 보자. 우선, 계산의 편의성을 위해 $c$ 함수의 공역이 양의 정수라고 가정하자. augmenting path를 한 번 찾으면, 즉 1-3과정이 한 번 반복되면 전체 flow의 값은 증가한다. 따라서 최악의 경우, 1-3 과정은 그래프의 최대 유량을 $X$라 하면 $X$번 반복된다. 1번 과정에서 residual flow를 구하는 과정은 $O(|E(G)|)$의 시간 복잡도가 소요된다. 또한 2번 과정의 augmenting path는 각 간선에 대해 residual flow를 구해주면 DFS로 찾을 수 있다. 이 과정에서는 $O(|E(G)|)$의 시간 복잡도가 소요된다. 마지막으로 3번 과정에서 augmenting path의 flow를 증가시키는 것은 augmenting path의 크기보다 작으므로, $O(E(G))$의 시간 복잡도가 소요된다. 따라서 전체 알고리즘의 시간 복잡도는 $O(X|E(G)|)$라 할 수 있다.
maximal flow를 augmenting path가 없는 모든 flow라고 정의하자. 실제로 쓰는 용어인지는 잘 모르겠다.
이제 정당성을 증명할 차례인데, 이는 약간 복잡하다. 우선 그래프의 cut과 minimum cut을 정의해야 한다.
2. Cut과 Minimum Cut
$s$-$t$cut과 그냥 cut은 의미하는 바가 약간 다르지만, 이 글에서만 "cut"이라는 표현을 $s$-$t$컷을 표현하는 뜻으로 사용하겠다.
Minimum cut 문제는 그래프에서 정의되는 또 다른 문제로, 간단히 말하면 가중치 있는 그래프와 두 정점이 주어질 때, 간선 여러 개(0개 이상)을 선택하여 그래프에서 제거한다. 이때 주어진 두 정점이 서로 끊어져야(서로 다른 컴포넌트에 있게 되어야) 한다. 이때 선택한 간선 가중치의 합을 최소화하는 문제이다. 수학적으로 정의하자면 다음과 같다.
flow network $(G, c, s, t)$에 대하여, $s$-$t$ cut : cut은 정점 집합을 두 개의 partition으로 나누는 것으로, $s$와 $t$가 같은 집합에 속하지 않아야 한다. $s$-$t$ cut은 $(S, T)$, ($s\in S$, $t \in T$)로 쓴다.
cut의 value는 두 컷을 잇는, 그러니까 한 정점은 $S$에 속하고 나머지 정점은 $T$에 속하는 두 정점을 잇는 간선의 가중치 합이다. 수식적으로 표현하면 $sum_{(u, v)\in E(G) s.t. u\in S, v\in T}{c(u, v)}$이다. value라고 쓰는 논문도 있는 것 같고, weight로 쓰는 경우도 있는 것 같다.
flow network에서 minimum cut 문제는, value가 최소인 cut을 구하는 문제이다. 이 문제는 직관적으로 maximum flow 문제와 큰 관련이 없을 것 처럼 보이지만, 특이하게도 Ford-Fulkerson 알고리즘의 정당성을 증명할 때 사용할 수 있다.
3. Max Flow Min Cut 정리
Minimum cut 문제와 maximum flow 문제는 모두 flow network에서 정의되는 문제인데, 여러 가지 경우의 flow network를 그려서 직접 풀어보면, 신기하게도 두 문제의 답(maximum flow에서의 value, minimum cut의 value)가 같음을 알 수 있다. 우연히 일어나는 일로 생각할 수 있겠지만, 수학적으로 증명할 수 있다.
증명 과정은 다음과 같다.
1. minimum cut $\ge$ maximum flow
2. maximal flow(포드 풀커슨 알고리즘의 결과값) $\ge$ minimum cut
즉, maximum flow는 아무리 커봐야 minimum cut을 넘을 수 없고, Ford-Fulkerson 알고리즘의 결과값은 maximum flow를 넘을 수 없고(이 사실은 자명하다), minimum cut은 아무리 커봐야 Ford-Fulkerson 알고리즘의 결과값을 넘을 수 없음을 보일 것이다.
1. minimum cut $\ge$ maximum flow
본격적인 증명에 앞서, 아래 증명은 수식적으로는 이해할 수 있어도, 직관적으로는 이해하기 힘들 수 있다. 이해를 돕기 위해 쓰자면, 그래프에서 $S$의 정점을 합쳐서 큰 하나의 정점으로 만들고, $T$도 마찬가지로 합쳐서 큰 하나의 정점으로 만들면, 두 정점으로 이루어진 그래프가 되는데, 이 그래프에서 최대 유량은 $S$와 $T$를 잇는 간선의 가중치의 총합을 넘을 수 없고, 이는 컷의 value와 일치한다. 나는 이렇게 생각하면 더 이해하기 쉬웠던 것 같다.
flow network $(G, c, s, t)$의 minimum cut을 $(S, T)$라 하자. ($s \in S, t \in T$) 모든 flow $f$에 대해, $f$의 value가 minimum cut의 value 이하임을 보일 것이다. 우선, 유량 함수의 3번 정의에 의해 모든 $v$에 대해 $\sum_{(v, u) \in E}{f(v, u)} = 0$가 성립한다. 이때, 이 식을 $v\in S$인 $v$에 대해서만 다 더해주면 아래와 같은 식을 얻을 수 있다.
$\sum_{v \in S}{\sum_{(v, u)\in E}{f(v, u)}}=\sum_{v \in S, (v, u)\in E}{f(v, u)}=|f|$
이때 오른쪽의 시그마 항에서 $v, u\in S$인 $(u, v)$ 쌍에 대해서는 $(v, u)$ 쌍 또한 시그마 안에 더해졌을 것이고, 유량 함수의 2번 정의에 의해 $f(u, v)=-f(v, u)$이므로 결과적으로 식을 다음과 같이 쓸 수 있다.
$\sum_{v \in S, u \in T, (v, u)\in E}{f(v, u)}=|f|$
또한,
$|f|=\sum_{v \in S, u \in T, (v, u)\in E}{f(v, u)} \le \sum_{v \in S, u \in T, (v, u) \in E}{c(v, u)}$
과 같이 식을 변형할 수 있는데, 이때 우변은 컷의 value에 해당함을 알 수 있고, 따라서 maximum flow는 minimum cut을 넘을 수 없다.
2. maximal flow $\ge$ minimum cut
간단하게 요약하자면, maximim flow에서 "꽉 찬", 그러니까 $f(u, v)=c(u, v)$인 간선들을 적당히 끊으면 끊은 간선의 가중치 합이 유량의 값 되고, 끊은 간선은 임의의 컷을 형성한다. 따라서 minimum cut은 maximal flow를 넘을 수 없다.
flow $f$의 residual flow(Ford-Fulkerson 알고리즘에서 정의했었던) $r$에 대해서 생각해보자. $r(u, v)=0$이거나 $r(v, u)=0$인 간선을 전부 모았을 때, 그 간선을 그래프에서 제거하면 $s$와 $t$는 반드시 서로 다른 컴포넌트에 속할 것이다. 이는 Ford-Fulkerson 알고리즘의 종료조건으로부터 증명할 수 있다. Ford-Fulkerson 알고리즘의 종료 조건은, 더 이상의 augmenting path가 발견되지 않는 것이다. 만약 $s$와 $t$가 같은 컴포넌트에 속한다면, $s$와 $t$로 가는 $r$값이 0 초과인 경로가 존재하고, 이는 augmenting path를 형성하고, 이는 포드 풀커슨 알고리즘이 종료되었다는 사실에 모순이기 때문이다.
간선을 전부 끊었을 때, $s$와 연결된 컴포넌트를 $S$, $S$에 속하지 않는 정점들을 $T$라 하자. 이때 $t\notin S$임이 확실하므로, $t \in T$이다. 이때, $(S, T)$는 $s$-$t$ cut임을 알 수 있다. 이때 다음과 같은 식이 성립한다.
$\sum_{v \in S}{\sum_{(v, u)\in E}{f(v, u)}}=\sum_{v \in S, (v, u)\in E}{f(v, u)}=|f|$
여기부터는 maximum flow가 minimum cut보다 같거나 작음을 보일 때와 유사하다. 마찬가지 이유로 아래 식 역시 성립한다.
$\sum_{v \in S, u \in T, (v, u)\in E}{f(v, u)}=|f|$
따라서, value가 $|f|$인 컷을 구할 수 있다. 따라서 최소 컷의 value는 $|f|$보다 같거나 작다.
위 일련의 정리들로 인해, maximum flow의 value와 minimum cut의 value와 Ford-Fulkerson 알고리즘의 결과값은 전부 동일하고, 따라서 Ford-Fulkerson 알고리즘은 올바른 maximum flow를 도출한다는 사실을 증명할 수 있다.