최대 유량 최소 컷 정리

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

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

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

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

 유한 방향성 그래프  . 여기서 V는 정점의 유한 집합을 나타내고  는 방향성 가장자리의 집합을 나타낸다;
 소스  및 싱크  ;
 용량 함수  또는  는  (  에 대해)로 표현되는 매핑이다. 용량 함수는 간선을 통과하는 유량의 최대값을 의미한다.

 유량 
흐름  또는  은  로 표현되는 매핑이다. 흐름에는 다음 두 가지 제약 조건이 적용된다.

 용량 제약 : 모든 에지  에 대해, 
 흐름 보존 : 소스 와 싱크 가 아닌 각 정점  에 대해,

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

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

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



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

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

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





 같이 보기 
 네트워크 흐름
 선형 계획법
 멩거의 정리

분류:그래프 이론 정리
분류:조합 최적화