최소 컷 (Min Cut) / 최대유량-최소컷 정리

최소 컷 (Min Cut) / 최대유량-최소컷 정리

네트워크에서 소스와 싱크를 분리하는 간선 집합 중 용량 합이 최소인 컷(분할)으로, 최대 유량과 동치임을 증명한 정리

최대유량-최소컷 정리(Max-Flow Min-Cut Theorem): 네트워크의 최대 유량 = 최소 컷의 용량, Ford & Fulkerson(1956) 증명

컷(Cut): 정점 집합을 S(소스 포함)와 T(싱크 포함)로 분할, 컷 용량 = S→T 간선 용량 합

최소 컷 구하기: 최대 유량 알고리즘 실행 후, 잔여 그래프에서 소스로부터 도달 가능한 정점 = S, 나머지 = T

특징: 최대 유량 문제의 쌍대(Dual) 문제, LP 쌍대성과 연결

응용

• •네트워크 신뢰성: 최소 컷 = 네트워크 단절에 필요한 최소 간선/노드 수
• •이미지 세그멘테이션: 전경/배경 분리를 최소 컷으로 모델링
• •네트워크 분할: 그래프를 두 그룹으로 최소 비용 분할
• •프로젝트 선택: 이익 최대화 = 최소 컷 문제로 환원

비교: 최소 컷(분할/용량합) vs 최대 유량(흐름/동치) vs 최소 정점 컷(정점 제거/Menger 정리)

연관: 최대 유량, Ford-Fulkerson, 잔여 그래프, 네트워크 플로우, LP 쌍대성