최소 절단

1 개요

minimum cut

최소 컷, 최소 절단

• 그래프의 엣지를 두 개의 분리된 하위집합으로 분할할 때 비용을 최소화하는 분할
• 양수·음수 가중치를 모두 허용하는 가중 최소 절단 문제는 모든 가중치의 부호를 뒤집어 가중 최대 절단 문제로 간단히 변환할 수 있다.

2 같이 보기

• 최대 컷
• vertex separator

3 참고

• 영어 위키백과 "Minimum cut"
• 다음백과 "최소 절단"
• 네이버백과 "최소 절단"
• https://m.blog.naver.com/kks227/220808685331