최대 유량 최소 컷 정리 문서 원본 보기

{{위키데이터 속성 추적}}
[[컴퓨터 과학]] 및 [[수학적 최적화|최적화 이론]] 에서 '''최대 유량 최소 컷 정리'''는 [[네트워크 흐름]] 에서 [[그래프 이론 용어|''소스'']]에서 [[그래프 이론 용어|''싱크'']]로 전달되는 유량의 최대 값과 최소 컷에서 간선의 총 가중치가 같음을 의미한다.

이는 [[선형 계획법]]의  쌍대성 정리의 특별한 경우이며 [[멩거의 정리|Menger의 정리]] 와 [[쾨니그의 정리|König–Egerváry 정리를]] 유도하는 데 사용될 수 있다.<ref>{{저널 인용|제목=On the max-flow min-cut theorem of networks|저널=RAND Corporation|성=Dantzig|이름=G.B.|성2=Fulkerson|이름2=D.R.|url=http://www.dtic.mil/dtic/tr/fulltext/u2/605014.pdf|날짜=9 September 1964|쪽=13|보존url=https://web.archive.org/web/20180505093256/http://www.dtic.mil/dtic/tr/fulltext/u2/605014.pdf|보존날짜=5 May 2018|url-status=dead}}</ref>

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

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

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

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

# '''용량 제약''' : 모든 에지 <math>(u, v) \in E</math> 에 대해, <math>f_{uv} \le c_{uv}.</math>
# '''흐름 보존''' : '''소스''' <math>s</math>와 '''싱크''' <math>t</math>가 아닌 각 정점 <math>v</math> 에 대해,<br /><math>\sum\nolimits_{\{ u : (u,v)\in E\}} f_{uv} = \sum\nolimits_{\{w : (v,w)\in E\}} f_{vw}.</math>

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

:


<blockquote></blockquote>

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

'''컷 집합''' <math>X_C</math> 는 소스 집합 ''S'' 와 싱크 집합 ''T'' 를 연결하는 간선의 집합이다.

: <math>X_C := \{ (u, v) \in E \ : \ u \in S, v \in T \} = (S\times T) \cap E.</math>

s-t 컷 ''C'' 의 '''용량'''은 <math>X_C</math>의 모든 간선의 용량의 합이다.

:

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

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

* {{서적 인용|제목=Combinatorial Optimization: Networks and Matroids|성=Eugene Lawler|저자링크=Eugene Lawler|연도=2001|출판사=Dover|쪽=117–120|장=4.5. Combinatorial Implications of Max-Flow Min-Cut Theorem, 4.6. Linear Programming Interpretation of Max-Flow Min-Cut Theorem|isbn=0-486-41453-1}}
* {{서적 인용|제목=Combinatorial Optimization: Algorithms and Complexity|성=[[Christos H. Papadimitriou]], [[Kenneth Steiglitz]]|연도=1998|출판사=Dover|쪽=120–128|장=6.1 The Max-Flow, Min-Cut Theorem|isbn=0-486-40258-4}}
* {{서적 인용|제목=Approximation Algorithms|성=[[Vijay Vazirani|Vijay V. Vazirani]]|연도=2004|출판사=Springer|쪽=93–100|장=12. Introduction to LP-Duality|isbn=3-540-65367-8}}
== 같이 보기 ==
* [[네트워크 흐름]]
* [[선형 계획법]]
* [[멩거의 정리]]

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