Network - 2. 최대흐름 최소절단면 정리

저번 글에서 최대흐름문제가 무엇인지 간단한 예시와 함께 살펴봤습니다. 이번 글에서는 최대흐름 최소절단면 정리에 대해 알아보도록 하겠습니다.

절단면이란, G=(N,A)의 N을, S와 여집합 T로 분할할 때, i ∈ S, j ∈ T인 호 ( i , j ) 의 집합을 의미합니다. δ(S)로 표기할 수 있습니다. 이때 속한 호들의 용량의 합을 u(δ(S)) 로 표기할 수 있습니다. S ∈ S, t ∈ T 이면 δ(S)를 s-t절단면이라고 부릅니다.

다음 그림에서 예시를 살펴보겠습니다. 점선은 s와 t를 두 부분으로 분할하고 있기 때문에 s-t절단면입니다. 이 절단면에 속한 호들의 용량은 u(δ(S)) = 8 입니다.

이 절단면을 활용해 최대흐름문제의 정리를 살펴볼 수 있습니다.

약쌍대 정리는 어떤 s-t 흐름 x의 크기도 어떤 s-t 절단면 δ(S)의 용량보다 같거나 작습니다. 이는 어떤 s-t흐름 경로도 s-t 절단면의 호를 최소한 한번은 통과해야 하기 때문입니다.

앞선 예시를 다시 한번 살펴보겠습니다. s-t 흐름은 8입니다. 절단면의 용량 u(δ(S)) = 8 보다 작음을 알 수 있습니다.

이번에는 최대흐름 최소절단면 정리를 살펴보겠습니다. 최대 s-t 흐름의 크기와 최소 s-t 절단면의 용량은 같습니다.

G(x)에서 s-I 흐름증가경로가 있는 마디 i의 집합을 S, 이외의 마디의 집합을 T라고 하겠습니다. 집합 S와 T는 모두 공집합이 아닙니다. 또, 집합 S에서 T로의 모든 호의 잔여용량은 0이어야 합니다.

S에서 T로의 모든 호의 잔여용량은 0이기 때문에 δ(S)의 모든 호는 용량과 같은 흐름을 가집니다. 반대방향의 δ(T)의 모든 호는 0의 흐름을 가집니다.

따라서 s에서 들어와 t로 나가는 모든 단위흐름은 δ(S)의 호를 단 한번만 흐르게 됩니다. 이때 δ(S)의 각 호의 흐름이 용량과 같기 때문에 전체 흐름의 크기는 u(δ(S))와 같게 됩니다. 즉, δ(S)는 흐름증가경로 알고리즘이 출력한 s-t흐름 x와 크기가 같은 용량을 가지는 s-t 절단면입니다.

참고자료 : 경영과학, 홍성필, 율곡출판사