최소 컷

최소 컷(Minimum Cut)은 민 컷이라고도 불리며 네트워크에서 용량이 가장 작은 컷을 말합니다.

이 때 컷이란 소스와 싱크가 각각 다른 집합에 속하도록 그래프의 정점을 두 개의 집합으로 나눈 것으로

소스가 속한 집합을 S, 싱크가 속한 집합을 T라 할 때

S에서 T로 가는 간선들의 용량 합을 컷의 용량, 유량 합을 컷의 유량이라고 합니다.

컷은 아래와 같이 2가지의 속성은 만족합니다.

1. 컷의 유량은 소스에서 싱크로 가는 총 유량과 같다.

2. 컷의 유량은 용량과 같거나 더 작다.

이 때 최소 컷 최대 유량 정리(Max-Flow Min-Cut Theorem)에 의하여

최소 컷은 네트워크 유량 문제에서의 최대 유량과 동일하다는 것을 이용하여 문제를 풀 수 있습니다.

네트워크 그래프에서 최소 용량의 간선을 자르고 싶을 경우에는 최대 유량을,

최소 용량의 정점을 자르고 싶은 경우 정점을 2개의 정점으로 나눈 뒤 사이에 있는 간선의 용량을

정점의 비용으로 둔 뒤 최대 유량을 구하여 문제를 풀 수 있습니다.

기본 문제

1420번: 학교가지마!

5398번: 틀렸습니다