:가장 효율적인 방법 때 그래프에서 최대 유동을 재 계산하는 가장 효율적인 방법은 무엇
가첫 번째 경우에는 Ford-Fulkerson 알고리즘의 한 반복을 실행하기에 충분합니까? 두 번째 경우에는 가장자리가 최대 흐름 가장자리 모서리의 일부인 경우에만 최대 흐름을 다시 계산해야합니다. Ford-Fulkerson을 한 번 반복하는 것만으로도 충분합니까?
첫 번째 경우 "예"입니다. 그것은 본질적으로 Ford-Fulkerson의 작동 방식입니다. 수정 된 그래프에서 처음부터 Ford-Fulkerson을 실행한다고 상상해보십시오. 원본 그래프에서와 똑같은 단계를 실행하여 시작할 수있었습니다. 을 이해하려면 왜이 작동하는지, 최대 흐름이 선형 프로그래밍과 어떻게 관련되는지 살펴 보는 것이 도움이 될 수 있습니다 (예 : http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/NetFlow/max-flow-lp.html 참조).
두 번째 경우 용량이 모두 정수 인 경우 대답은 기본적으로 "예"입니다. 가장 먼저해야 할 일은 기존의 최대 흐름을 수정하여 새로운 제약 조건을 충족시키는 것입니다. 근본적으로 감소 된 가장자리를 통과하는 흐름을 따라 소스에서 싱크까지의 경로를 찾는 것으로이 작업을 수행 할 수 있습니다 (이 작업은 어렵지 않습니다. 감소 된 가장자리에서 시작하여 흐름을 따르십시오). 그런 다음 해당 경로의 각 가장자리에 대해 흐름에서 1을 뺍니다. 이제 제약 조건을 만족하는 흐름이 있지만 차선책 일 수 있습니다. 그러나, 그것은 최적의 흐름보다 최대 1 분의 1에 불과하므로, 다시 한번 Ford-Fulkerson의 반복이 효과적입니다.
정수가 아닌 경우 상황이 더 복잡 할 수 있으며 최악의 경우 기본적으로 문제를 다시 해결해야합니다. 여기서는 최상의 알고리즘에 익숙하지 않지만 "동적 최대 흐름"을 검색 할 수 있습니다. https://cstheory.stackexchange.com/questions/9938/incremental-maximum-flow-in-dynamic-graphs도 참조하십시오.