Minimum cut

http://kks227.blog.me/220796029558 에서 핵심만 가져와 정리해왔습니다.

이 그래프에서 a와 e를 분리시키고 싶다고 합시다.

자르는 방법은 여러가지가 될 수 있지만 아래처럼 자를수 있습니다.

이처럼 자르면 A,B,C와 D,E로 분리됩니다. 이렇게 그래프를 자르는걸 컷이라고 한답니다.

컷에는 비용이 있는데 위처럼 자르면 선이 3개가 잘리므로 비용이 3입니다. A바로 오른쪽에서

자르면 비용이 2로 A와 E를 분리시킬수 있겠네요. 이렇게 임의의 두 정점을 정하고, 두 정점을

다른 컴포넌트로 분리시키는 비용을 최소화하는걸 미니멈 컷이라고 한답니다.

이처럼 가중치가 있는 그래프라면 단순히 선을 조금 자르는것보다 비용을 생각해서 자르는게 

효율적입니다.

이렇게 자르면 비용이 9로 A와 E를 자르는 미니멈 컷이 됩니다.

이러한 방향 그래프가 있다고 할때 이를 유량 그래프로 생각하고 유량을 흘리면 아래처럼 됩니다.

그리고 컷을 한다고 했을때 컷에 포함된 간선들에 흐르는 유량은 항상 동일하다고 합니다.

(위에서는 11로 동일) 그리고 최대 유량을 흘리고 있을때가 최소 컷입니다.

아직 유량이 최대로 흐르지 않는 간선을 통과할수 있다고 할때, S에서 시작해서

도달 가능한 점들과 도달 불가능한 점들을 구분할수 있습니다. 

도달 가능 : S,A,B,C 도달 불가능 : D,T

이걸 구분짓는 중요한 역할을 하는 포화 간선들이 BD, BT, CD이고 이들이 최소 컷입니다.