포드-풀커슨 방법 (1) 썸네일형 리스트형 포드-풀커슨 방법 (Ford-Fulkerson Method) 최대 흐름 문제(maximum flow problem)는 어떤 흐름 네트워크(flow network)가 주어졌을 때, 시점에서 종점으로 흐르는 최대 흐름을 찾는 문제입니다. 지난 두 포스트를 통해 우리는 이 문제에서 최대 흐름이 다음과 같은 흥미로운 특징을 갖는다는 것을 알게 되었습니다. 정리 1. 최대 흐름의 잔여 네트워크의 특징 최대 흐름의 잔여 네트워크(residual network)에서는 시점에서 종점으로 도달할 수 없다. 정리 2. 잔여 네트워크의 종점 비도달성의 특징 어떤 흐름의 잔여 네트워크에서 종점이 시점으로부터 도달 불가능할 때, 그것의 흐름양과 동일한 값의 용량을 갖는 절단(cut)을 찾을 수 있다. 그러므로, 이 흐름은 최대 흐름이다. 정리 1의 증명이 궁금하면 아래 글을 참조하세요... 이전 1 다음
