최대 유량 최소 컷 정리

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

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

정의 및 설명

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

네트워크

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

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

유량

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

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

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

컷

s-t 컷 틀:수학은 틀:수학, 틀:수학 를 만족하는 정점 틀:수학 변수 의 분할이다. 즉, 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 컷에 대한 최소 용량과 같다.

• 틀:서적 인용
• 틀:서적 인용
• 틀:서적 인용

같이 보기

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