최대 유량 알고리즘 1 (Ford-Fulkerson, Max Flow Minimum Cut Theorem)
최근 유량 알고리즘들을 공부해 봤는데, 정리와 증명이 명확하게 정리된 블로그가 잘 없는 것 같아서 정리한다. * 모바일 환경에서 레이텍이 깨지는 현상이 있는 것 같다. 구글 크롬의 경우, 우측 상단의 점 세 개를 눌러 메뉴를 열고 "데스크톱 보기"를 활성화하는 것으로 해결할 수 있다. 0. 용어 정의 다음과 같이 그래프, 소스 정점, 싱크 정점, 용량 함수가 주어졌다고 하자. graph $G=(V, E)$, source $s \in V$, sink $t \in V (s \ne e)$, 용량 함수 $c : V \times V \longmapsto \mathbb{R}^{+}$ (수학에서는 이 네 요소 $(G, c, s, t)$를 flow network라 한다.) 이때, $G$의 소스에서 싱크로 물건을 옮기는..
