Network Flow 2 - Min-Cut Max-Flow Theorem
1편 에서 이어집니다.
Min-Cut
그래프에서 절단(Cut)의 정의는 다음과 같다.
그래프 $G=(V, E)$에 대해 $e \in E$ 인 간선을 한 개 이상 끊어서 $V_1 \subset V$과 $V_2 \subset V$ 두 정점 집합으로 나누며 $V_1 \cup V_2=V ~\&~ V_1 \cap V_2 = \varnothing \Longleftrightarrow V_2=V \setminus V_1$
여기서 네트워크 그래프의 관점에서 보자면 $source \in V_1$ 이고 $sink \in V_2$ 라고 할 수 있다.
네트워크 그래프에서 최소 컷(Minimum Cut)문제는 간선들을 절단해서 그래프를 정확히 두 개로 나누면서 간선을 자를 때마다 그 간선의 용량만큼 비용이 든다고 할 때, 그 최소 절단 용량합을 구하는 문제이다.
Min-Cut Max-Flow Theorem
결론적으로 최소 컷의 값은 최대 유량과 동치이다.
그래서 최소컷 문제도 그냥 Edmonds-Karp 알고리즘을 써서 최대 유량을 구하면 그것이 정답이다.
엄밀한 증명에 관련된 내용은 이 글을 추천한다.
0. Notation
- 절단 용량 $c(S)$: 유량 그래프에서 임의의 절단 $S$를 이용해 그래프가 $V_1, V_2$ 로 나뉠 때, $V_1$ 에서 $V_2$ 로 이어진 간선의 용량의 합
- 이것을 최소화 하는 것이 Min-Cut 문제이다.
- 순 흐름양 $f(S)$: 유량 그래프에서 임의의 절단 $S$를 이용해 그래프가 $V_1, V_2$로 나뉠 때, $\overrightarrow {V_1V_2}$ 혹은 $\overleftarrow {V_1V_2}$ 로 이어진 절단된 간선들에 흐르고 있는 유량의 총량
- $\overrightarrow {V_1V_2}$ 방향은 이 값이 양수 $(+)$ 이고, $\overleftarrow {V_1V_2}$ 방향은 이 값이 음수 $(-)$ 이다.
1. 순 흐름양은 절단 용량 이하이다.
어떤 간선에서 유량은 용량보다 많이 흐르고 있을 수 없기 때문에 쉽게 보여진다.
$\overleftarrow {V_1V_2}$ 는 음수로 더해지기 때문에 $\overrightarrow {V_1V_2}$ 간선들의 총 용량이 $\overrightarrow {V_1V_2}$ 간선들의 총 유량보다 작을 순 없다.
즉, $f(S)$가 $c(S)$보다 커질 순 없다.
2. 모든 절단의 순 흐름양은 동일하다.
$source \to sink$ 로 가는 유량의 흐름에서 어떤 절단을 취하든 항상 절단에 포함된 간선에서 $\overrightarrow {V_1V_2}$ 로 흐르고 있는 유량의 합은 동일하다는 의미이다.
Theorem
정리 1에 의해 $f(S) \le c(S)$ 이므로 존재하는 $S$중, $c(S)$ 가 가장 작은 것을 찾는다면 그건 결국 $f(S)$ 의 최대값을 찾는데 도움이 된다.
$S$ 중, 절단 용량 $c(S)$가 가장 작은 절단을 $S^*$ 라 하자. 역시나 유량 $\lvert f \rvert$ 에 대해 $\lvert f \rvert \le c(S^*)$ 이다.
어떤 유량이 $\lvert f \rvert = c(S)$ 라고 한다면, 그 때의 흐름양 $\lvert f \rvert$ 가 최대 흐름(유량)이 되고, 그 때의 절단 $S$가 $S^*$ 이다.
위 성질을 볼 때, 결국 $S^*$ 가 존재를 하면 최대 유량도 찾고 할 수 있는데, $S^*$ 는 항상 존재한다는 보장이 없다는 것이 문제이다.
하지만, $S^*$ 가 항상 존재하는 경우가 있는데, 그건 바로 $source \to sink$ 의 증가 경로 $P$가 존재하지 않는 상황이다.
따라서 $source \to sink$의 증가 경로 $P$가 존재하지 않는다면 $S^*$가 존재하여 그 때의 절단 용량이 곧 최대 유량이다.
증명
$source \to sink$ 로 증가 경로가 없을 때, $source$ 로부터 잔여 네트워크를 이용해 도달할 수 있는 정점 집합을 $S \subset V$ 라고 하자.
$S \to V \setminus S$ 로 나가는 간선은 없다. 왜냐면 여기에 여유용량이 있는 간선이 있다는 것은 $S$의 정의에 위반되기 때문이다.
따라서 $V \setminus S \to S$ 로 들어오는 간선만 고려하자. 그걸 $\overrightarrow {vu} ~~ (v \in V \setminus S,~ u \in S)$ 라고 하자.
- $\overrightarrow {vu}$ 이 역간선이라면
원래 $\overrightarrow {uv}$ 는 그래프에 존재하는 정방향 간선이고 유량이 흐르고 있다는 것이 된다.
$S$의 정의에 의해 $\overrightarrow {uv}$ 는 여유 용량이 $0$이여야 한다. $\Rightarrow c(u, v)=f(u, v)$
- $\overrightarrow {vu}$ 이 정방향 간선이라면
원래 네트워크 그래프에는 $\overrightarrow {vu}$ 가 있을 것이고 $\overrightarrow {uv}$ 는 $S \to V \setminus S$ 로 가는 간선인데 이 간선은 포함되지 않았으므로 $\overrightarrow {vu}$ 의 유량은 $0$이다.
결론적으로 $V \setminus S \to S$ 로의 의 역간선들은 모두 $S \to V \setminus S$ 의 정방향 간선들에 대응되면서 모두 유량이 꽉차있는 상태이고, $V \setminus S \to S$ 로의 의 정방향 간선들은 모두 $S \to V \setminus S$ 의 역간선들에 대응 되면서 유량이 $0$ 인 상태이므로
이다. $\lvert f \rvert=f(S)$ 는 정리 2에 의해 보여지고, $source \to sink$ 로의 증가 경로가 없다면 이것이 결국 $\displaystyle \sum_{e \in (S \to V \setminus S)}f(e)$ 라는 것이 보여졌다.
그리고 이 간선들은 모두 여유용량 없이 $f(u,v)=c(u,v)$ 라는 것을 보였기 때문에 결국 절단 용량 $c(S)$ 의 정의와 동치가 되기 때문에
증가 경로가 없는 상태의 네트워크 그래프에서 유량은 어떤 절단 $S$의 절단 용량 $c(S)$ 와 동일한 절단 $S$이 항상 존재하고, $f(S) \le c(S)$ 이기 때문에 위에서 언급한대로 이 때가 최대 유량임이 보여진다. $\square$
Comments