최대 흐름과 최소 컷 간의 강한 이중성의 의미

Question

제 질문은 max-flow 및 min-cut 알고리즘에 관한 것입니다. 왜 최대 유량과 최소 유량 사이에 강한 이중성이 있는지 알고 싶습니다.

Answer 1

this에서 설명했듯이 Max-Flow 문제와 Min-Cut 문제는 ​​이중 선형 프로그램으로 공식화 할 수 있습니다. 두 선형 프로그램 모두 가능하기 때문에 이중성은 duality of linear programs의 특별한 경우로 볼 수 있습니다.