유량 관련 알고리즘 증명

유량 알고리즘과 테크닉들은 다른 분야에 비해서 자명하지 않고 어려운 증명들을 상당히 많이 사용한다고 느꼈다.

이러한 증명들을 알아둬야지만 상급 문제들을 풀 수 있다고 생각해서, 여러 중요한 정리들을 증명해 놓으려고 한다. 엄밀하게 잘 증명하려고 노력은 하고 있지만 잘 될지는 모르겠다. (지적 환영합니다)

 

정리 글하고 같이 보자. (정리에 없는 내용들도 있다.)

 

1) Edmonds-Karp Algorithm이 VE^2인 이유

Edmonds-Karp Algorithm이 VE^2인 이유를 증명하기 위해서는, 증가 경로를 많아야 VE번 찾는다는 것을 보이면 된다. BFS 한번이 O(E)이기 때문이다. 이 사실을 보이겠다.

정의 1. 간선의 capacity == 간선에 흐른 flow 인 간선을 포화 간선이라 정의한다. 그렇지 않은 간선을 비포화 간선이라고 정의한다.

정의 2. 비포화 간선들로 이루어진 그래프를 Residual Graph라고 정의한다. 

 

Lemma 1. Residual Graph에서 현재의 source - sink 최단경로가 D라고 했을 때, 최단 경로를 D로 유지하는 동안 E번만 증가 경로를 찾는다. 

증명. 한번 flow를 흘리면, Residual Graph의 간선 중 최소 하나가 포화 상태로 차 버리게 된다. 포화 상태로 차게 된다면, 최단 경로가 D인 한 다시 그 간선을 보게 될 일은 없다. (역변을 타게 되면 최단 경로가 D+2 이상이 되는 고로, 그러한 경로는 찾지 않는다) 역변을 탈 일이 없으니 간선은 비포화에서 포화로만 변하고, 모든 간선이 포화로 변하면 경로가 없게 된다. 고로 최단 경로를 고정했을 때 O(E) 개의 증가 경로만을 찾는다. 

 

최단 경로의 길이는 V 이하이니 이러한 과정이 V번 일어난다. 고로, 많아야 VE번 증가 경로를 찾는다. 

 

2) Maximum Flow가 Minimum Cut인 이유 (Max-Flow Min-Cut Theorem)

Lemma 2. s - t Maximum Flow의 크기 <= s-t Minimum Cut의 크기.

증명. 임의의 s - t Minimum Cut을 생각해보자. 이 컷을 따라서 그래프를 두 컴포넌트로 쪼개면, 두 컴포넌트 간에 흐를 수 있는 Flow의 크기는 그 컷의 크기와 동일하다. 고로, s - t간에 흐를 수 있는 Maximum Flow의 크기는, 그 컷의 크기보다 작거나 같다. 

 

Lemma 3. s - t Maximum Flow의 크기와 같은 크기의 Cut을 찾을 수 있다.

증명. s - t Maximum Flow의 Residual Graph를 구해보자. Maximum Flow를 구했으니, Residual Graph 내에서 s - t를 잇는 경로는 없다. Residual Graph 내에서 s로 도달가능한 정점들의 집합을 A, 그렇지 않은 집합을 B라고 할 때, 우리는 시작점이 A에 속하고 끝점이 B에 속한 모든 간선들의 집합 C를 생각할 것이다. 

C가 s - t의 Cut임은 자명하다. 이제, 이러한 간선의 가중치합이 s - t Maximum Flow과 같다는 것을 보인다. s - t Maximum Flow를 구성하는 모든 Augmenting Path를 고려하자. 각 Augmenting Path는 A에서 B로 K번, B에서 A로 K-1번 움직인다. 고로, (K - (K-1)) * 흘린 플로우 양 만큼 C에 속하는 간선의 flow 양을 증가시킨다. 결론적으로, C에 속하는 간선의 flow 합 == 모든 Augmenting Path가 흘린 플로우 양 == s - t Maximum Flow와 같다. 

한편, C에 속한 간선들은 모두 포화되어 있다. 그렇지 않다면 끝점이 A에 속하기 때문에, 가정에 모순이기 때문이다. 고로, C에 속하는 간선의 capacity 합 == C에 속하는 간선의 flow 합 == 모든 Augmenting Path가 흘린 플로우 양 == s - t Maximum Flow 이다. C라는 Cut의 크기는 s - t Maximum Flow의 크기와 같다. 

 

Theorem. s - t Maximum Flow의 크기 == s - t Minimum Cut의 크기.

증명. s - t Maximum Flow와 같은 s - t Cut을 Lemma 3에서 찾았다. 그보다 작은 컷은 Lemma 2에 의해 존재할 수 없으므로 그것이 s - t Minimum Cut이다.

 

3) 이분 그래프에서, Maximum Matching의 크기가 Minimum Vertex Cover의 크기인 이유 (Kőnig's theorem)

Lemma 4. 이분 그래프에서, Maximum Matching의 크기 <= Minimum Vertex Cover의 크기

증명. Maximum Matching보다 작은 Vertex Cover가 존재한다고 치자. 최소 1개 이상의 매칭은, 양 정점이 Vertex Cover에 속하지 않을 것이다. 고로 그럴 수 없다.

 

Lemma 5. 이분 그래프에서, Maximum Matching의 크기 만큼의 Vertex Cover를 구할 수 있다. 

증명. Max-Flow Min-Cut Theorem으로 쉽게 구할 수 있다. 맨날 해왔던 방법과 똑같이 이분 매칭을 플로우로 모델링해보자. 이분 그래프의 두 정점 집합을 L, R이라고 했을 때,

 * source 정점에서, L에 있는 모든 정점에 용량 1의 간선을

 * R에 있는 모든 정점에서, sink 정점으로 용량 1의 간선을

 * 이분 그래프에서 L의 정점 p, R의 정점 q를 잇는 간선이 있다면, p에서 q로 용량 무한의 간선을

source에서 sink로 Maximum Flow를 구하면, 이분 매칭의 크기 만큼의 Maximum Flow == Minimum Cut을 구할 수 있다. Minimum Cut에 속하는 간선은 source 정점에서 L을 잇는 용량 1의 간선이거나, R에서 sink 정점을 잇는 용량 1의 간선이다. 원래 그래프에 있던 간선은 무한한 용량을 가지니 불가능하다.

Residual Graph에서, source에서 도달 가능한 정점 집합을 S, 그의 여집합을 T라고 하자. 각각의 Min-Cut 간선에 붙어 있는 서로 다른 정점들을 모으면, (T & L) | (S & R) 꼴의 집합으로 나올 것이다. 이 집합의 크기는, Minimum Cut의 크기와 동일하다. 고로 Maximum Matching의 크기와도 동일하다.

이제 이 정점이 모든 정점을 덮는다는 것을 보인다. 원래 이분 그래프에 속했던, 용량 무한의 간선들을 생각했을 때, 이 중 어떠한 간선도 S -> T를 잇지 않는다. 잇게 된다면 컷이 아니기 때문이다. 만약에 S -> S거나 T -> S면, S & R 꼴의 집합에서 cover되고, 그것도 아니면 T -> T이니 T & L 꼴의 집합에서 cover된다. 고로 이분 그래프의 모든 간선을 덮는다. 원하는 것을 구했다.

 

Theorem. 이분 그래프에서, Maximum Matching의 크기 == Minimum Vertex Cover의 크기

증명. Maximum Matching와 같은 Vertex Cover을 Lemma 5에서 찾았다. 그보다 작은 커버는 Lemma 4에 의해 존재할 수 없으므로 그것이 Minimum Vertex Cover이다.

(사실 Konig's theorem은 Max-flow Min-cut theorem보다 먼저 나와서, 저게 오리지널한 증명은 아니다. 다만 말이 조금 길어질 뿐 큰 차이는 없다.)

 

 

4) 부분 순서 집합의 최대 반사슬의 크기가 최소 Path Cover의 크기와 같은 이유 (Dilworth's theorem)

정의 3. 부분 순서 집합은 사이클이 없는 방향성 그래프로, 임의의 정점 i, j, k에 대해서 i에서 j로 가는 에지와, j에서 k로 가는 에지가 있으면, i에서 k로 가는 에지가 항상 존재하는 성질을 가진다. 

정의 4. 부분 순서 집합의 반사슬은, 정점의 부분집합으로, 부분집합의 임의의 정점 i, j에 대해, i -> j로도, j -> i로도 에지가 없는 집합을 뜻한다.

쉽게 설명하자면, DAG에 플로이드 돌리면 부분 순서 집합이다. 대전 리저널에도 나왔었고 (2012 K) 그렇게 낯선 개념은 아니다. 예시 문제를 들면 "DAG가 주어졌을 때, 서로 경로가 없는 최대 정점 집합을 출력하라" 같은 문제가 있겠다. 플로이드를 돌려서 부분 순서 집합으로 만들어 주고 반사슬을 구하면 된다. 

부분 순서 집합의 최대 반사슬은 최소 Path Cover라는 내용이 Dilworth's Theorem이다. Path Cover는 대충 이렇게 구할 수 있다. 이제 이것의 크기와 최대 반사슬의 크기가 같음을 보인다.

 

Lemma 6. 부분 순서 집합의 최대 반사슬의 크기는, 최소 Path Cover의 크기 이하이다.

증명. 만약 부분 순서 집합의 최대 반사슬의 크기가 Path Cover의 크기보다 크다면, 최소 하나의 Path에는, 두개 이상의 정점이 반사슬에 속할 것이다. Path이기 때문에 에지가 존재할 것이고 고로 이는 모순이다.

 

Lemma 7. 부분 순서 집합에서, 최소 Path Cover 이상의 크기를 가지는 반사슬을 찾을 수 있다.

증명. Path Cover를 구한 방식대로 이분 그래프를 만들자. 다시 설명하자면, 

 * 부분 순서 집합의 한 정점 V를 Out(V) / In(V)로 나누고,

 * U -> V로 가는 간선이 있을 때 Out(U) - In(V) 에지를 이어줌.

최소 path cover의 크기는 N - (maximum matching) 이다. Konig's Theorem에 의해 (maximum matching) = (minimum vertex cover) 이니, N - (min path cover) = (minimum vertex cover) 이다. 이제 In(i) 와 Out(i)가 모두 vertex cover에 속하지 않은 정점들의 집합을 A라 하자. A의 크기는 N - (vertex cover)의 크기보다 크거나 같고, 고로 최소 path cover의 크기보다 크거나 같다. 

이제 A가 반사슬임을 보이면 된다. vertex cover의 여집합은 independent set을 이루니, A에 있는 모든 정점 i에 대해서, In(i)와 Out(i)는 independent set에 속함을 알 수 있다. 즉, A에 있는 임의의 정점 i, j에 대해, Out(i) - In(j)과 같이 에지가 이어진 경우가 없다는 것을 뜻한다. 고로, A는 반사슬을 이룬다.

 

Theorem. 부분 순서 집합에서, 최소 Path Cover의 크기 == 최대 반사슬의 크기

증명. Lemma 7에서 Path Cover보다 큰 반사슬을 찾았다면, Lemma 6에 의해 모순이니 그럴 수는 없다. 즉, Lemma 7에서는 항상 Path Cover와 같은 크기의 반사슬만을 찾을 것이며, 그보다 큰 반사슬은 Lemma 6에 의해 존재할 수 없으므로 그것이 최대 반사슬이다.

 

5) Dinic's Algorithm이 가중치가 1일 때 O(min(V^(2/3), E^(1/2))) 번만 Blocking Flow를 찾는 이유

먼저, Dinic's Algorithm에서 E^1/2번의 Blocking Flow를 찾았다면, Residual Graph에서 source와 sink 간의 거리가 E^1/2 이상이 될 것이다. 이제 다음과 같은 Lemma를 사용한다.

Lemma 8. source와 sink 간의 거리가 E^1/2 이상인 네트워크에서, E^1/2 이하의 크기의 Cut을 찾을 수 있다.

증명. source와의 거리가 D인 정점 -> source와의 거리가 D+1 인 정점을 잇는 간선들의 집합을 S(D) 라고 정의한다. 0 <= i < E^1/2일 때, 임의의 집합 S(i)를 지우면 source와 sink가 연결이 끊기니 각각의 S(i)는 cut을 이룸을 알 수 있다.

이제 귀류법을 사용해서 0 <= i < E^1/2일 때, S(i) > E^1/2 를 항상 만족한다고 하자. S(i)의 크기의 합은 E를 넘게 되는데, 각각이 교집합이 없는 부분집합이니 그럴 수는 없다. 고로, S(i) <= E^1/2 인 i가 적어도 하나 존재한다. E^1/2 이하 크기의 cut을 찾았다.

Max-Flow Min-Cut Thm에 의해, Maximum Flow의 값은 E^1/2 이하이다. Blocking Flow 한번은 1 이상의 플로우를 무조건 흘려주는 고로 이후 E^1/2번 이상 Blocking Flow를 찾지 않는다. E^1/2 + E^1/2 = O(E^1/2) 번만 Blocking Flow를 찾는다.

 

똑같은 방법으로 O(V^2/3)도 증명 가능하다. 

Lemma 9. source와 sink 간의 거리가 2 * V^2/3 이상인 네트워크에서, V^2/3 이하의 크기의 Cut을 찾을 수 있다.

증명. source와의 거리가 D인 정점의 집합을 S(D)라고 정의한다. 0 <= i < 2 * V^2/3 일 때, 임의의 집합 S(i)와 S(i+1)을 잇는 모든 간선을 지우면, |S(i)| * |S(i+1)| 이하의 cut을 찾을 수 있다.

이제 귀류법을 사용해서 0 <= i < 2 * V^2/3일 때, |S(i)| * |S(i+1)| > V^2/3을 항상 만족한다고 하자. a, b >= 0 일 때 (a + b) / 2 >= (ab)^1/2 이니, |S(i)| + |S(i+1)| > 2 * V^1/3이다. |S(i)| 의 크기의 합은 V를 넘게 되는데, 각각이 교집합이 없는 부분집합이니 그럴 수는 없다. 고로, |S(i)| * |S(i+1)| <= V^2/3인 i가 적어도 하나 존재한다. V^2/3 이하 크기의 cut을 찾았다.