hellogaon

최소 컷(Minimum Cut)은 민 컷이라고도 불리며 네트워크에서 용량이 가장 작은 컷을 말합니다.이 때 컷이란 소스와 싱크가 각각 다른 집합에 속하도록 그래프의 정점을 두 개의 집합으로 나눈 것으로소스가 속한 집합을 S, 싱크가 속한 집합을 T라 할 때S에서 T로 가는 간선들의 용량 합을 컷의 용량, 유량 합을 컷의 유량이라고 합니다.컷은 아래와 같이 2가지의 속성은 만족합니다. 1. 컷의 유량은 소스에서 싱크로 가는 총 유량과 같다.2. 컷의 유량은 용량과 같거나 더 작다. 이 때 최소 컷 최대 유량 정리(Max-Flow Min-Cut Theorem)에 의하여최소 컷은 네트워크 유량 문제에서의 최대 유량과 동일하다는 것을 이용하여 문제를 풀 수 있습니다.네트워크 그래프에서 최소 용량의 간선을 자르고..