최대 유량 최소 컷 정리

컴퓨터 과학 및 최적화 이론 에서 최대 유량 최소 컷 정리는 네트워크 흐름 에서 소스에서 싱크로 전달되는 유량의 최대 값과 최소 컷에서 간선의 총 가중치가 같음을 의미한다.

이는 선형 계획법의 쌍대성 정리의 특별한 경우이며 Menger의 정리 와 König–Egerváry 정리를 유도하는 데 사용될 수 있다.

정의 및 설명

최대 유량 최소 컷 정리는 네트워크의 최대 흐름과 네트워크 컷의 최소 용량이 동일함을 보인다.

네트워크

네트워크는 다음으로 구성된다.

• 유한 방향성 그래프 N = (V, E) . 여기서 V는 정점의 유한 집합을 나타내고 E ⊆ V×V 는 방향성 가장자리의 집합을 나타낸다;
• 소스 s ∈ V 및 싱크 t ∈ V ;
• 용량 함수 c_uv 또는 c(u, v) 는 $c:E\to \mathbb {R} ^{+}$ ( (u,v) ∈ E 에 대해)로 표현되는 매핑이다. 용량 함수는 간선을 통과하는 유량의 최대값을 의미한다.

유량

흐름 $f_{uv}$ 또는 $f(u,v)$ 은 $f:E\to \mathbb {R} ^{+}$로 표현되는 매핑이다. 흐름에는 다음 두 가지 제약 조건이 적용된다.

1. 용량 제약 : 모든 에지 $(u,v)\in E$ 에 대해, $f_{uv}\leq c_{uv}.$
2. 흐름 보존 : 소스 $s$와 싱크 $t$가 아닌 각 정점 $v$ 에 대해,
   $\sum \nolimits _{\{u:(u,v)\in E\}}f_{uv}=\sum \nolimits _{\{w:(v,w)\in E\}}f_{vw}.$

흐름은 각 간선의 방향을 따라 네트워크를 통과하는 유체의 물리적 흐름으로 시각화할 수 있다. 용량 제약 조건은 단위 시간당 각 간선을 통해 흐르는 유체의 부피가 간선의 최대 용량보다 작거나 같다는 것을 의미한다. 보존 제약 조건은 소스와 싱크를 제외한 각 정점으로 흐르는 양이 각 정점에서 나가는 양과 같다는 것을 의미한다.

컷

s-t 컷 C = (S, T)은 s ∈ S, t ∈ T 를 만족하는 정점 V 의 분할이다. 즉, s-t 컷은 네트워크의 정점을 소스 s 를 포함하는 집합 S 와 싱크 t 를 포함하는 집합 T, 두 집합으로 분할하는 것이다.

컷 집합 $X_{C}$ 는 소스 집합 S 와 싱크 집합 T 를 연결하는 간선의 집합이다.

$X_{C}:=\{(u,v)\in E\ :\ u\in S,v\in T\}=(S\times T)\cap E.$

s-t 컷 C 의 용량은 $X_{C}$의 모든 간선의 용량의 합이다.

주요 정리

네트워크를 통과하는 모든 흐름의 값은 모든 s-t 컷의 용량보다 작거나 같고, 더 나아가 최대 값을 갖는 흐름과 최소 용량을 갖는 s-t 컷이 존재한다는 것을 증명할 수 있다.

최대 흐름 최소 컷 정리 : s와 t 를 잇는 흐름의 최대값은 s-t 컷에 대한 최소 용량과 같다.

• Eugene Lawler (2001). 〈4.5. Combinatorial Implications of Max-Flow Min-Cut Theorem, 4.6. Linear Programming Interpretation of Max-Flow Min-Cut Theorem〉. 《Combinatorial Optimization: Networks and Matroids》. Dover. 117–120쪽. ISBN 0-486-41453-1. 
• Christos H. Papadimitriou, Kenneth Steiglitz (1998). 〈6.1 The Max-Flow, Min-Cut Theorem〉. 《Combinatorial Optimization: Algorithms and Complexity》. Dover. 120–128쪽. ISBN 0-486-40258-4. 
• Vijay V. Vazirani (2004). 〈12. Introduction to LP-Duality〉. 《Approximation Algorithms》. Springer. 93–100쪽. ISBN 3-540-65367-8. 

같이 보기

• 네트워크 흐름
• 선형 계획법
• 멩거의 정리