최소 s-t 커트에서 최대 흐름 찾기

Question

잔여 그래프의 소스에서 BFS를 사용하여 최대 흐름 f가 주어지면 최소 용량으로 s-t 커팅을 얻는 것이 쉽습니다. 최소 용량 s-t가 주어진다면 최대 흐름 f를 얻기위한 알고리즘이 있습니까?

Answer 1

아니요, 기본적으로. 문제는 일반적으로 min cut은 거의 알려주지 않는다는 것입니다. 주어진 네트워크에서 싱크의 새로운 호를 이전의 최대 흐름과 동일한 용량을 가진 새로운 싱크가되는 새로운 정점에 연결하여 새로운 네트워크를 형성하십시오. 이제 min cut은 그 호입니다. 나머지 네트워크에 대한 정보는 없습니다.