최대 유량(네트워크 플로우) 계산기

남은 용량이 있는 길을 찾아 흘릴 수 있는 만큼 흘리는 것을 더 찾을 길이 없을 때까지 되풀이합니다. 한 번에 흘리는 양은 그 길에서 가장 좁은 곳의 남은 용량입니다. 이 도구는 길을 고를 때 간선 수가 가장 적은 것을 너비 우선으로 고르는 에드몬드–카프를 씁니다.

그래프를 출발점 쪽과 도착점 쪽으로 갈랐을 때 건너가는 간선들의 용량 합이 가장 작아지는 자름이 최소 컷이며, 그 값은 최대 유량과 정확히 같습니다. 다 흘리고 난 뒤 잔여 그래프에서 출발점으로부터 갈 수 있는 정점을 모으면 그것이 컷의 한쪽인데, 더 흘릴 길이 없다는 것은 그 경계를 건너는 간선이 모두 꽉 찼다는 뜻이라 그 용량 합이 곧 병목입니다.

앞서 흘린 배분을 되무를 수 있어야 최적에 닿기 때문입니다. 흘린 방향의 반대쪽에 같은 만큼 잔여 용량을 만들어 두면, 나중에 그 역방향을 타는 것이 곧 앞서 흘린 것을 그만큼 무르는 셈이 됩니다. 이 장치가 없으면 욕심껏 흘린 뒤 어중간한 답에서 멈춥니다.

반복 횟수를 용량의 크기와 무관하게 만들기 위해서입니다. 길을 아무렇게나 고르면 용량 1짜리 간선을 오가며 1씩 수백만 번 흘리는 일이 생길 수 있지만, 간선 수가 가장 적은 길을 고르면 반복이 정점·간선 수만으로 묶입니다. 이것이 포드–풀커슨과 에드몬드–카프의 차이입니다.

푸는 문제가 다릅니다. 최단경로는 「가장 짧은 길 하나」를 찾고, 최대 유량은 「여러 길로 나눠 보낼 수 있는 총량」을 구합니다. 최대 유량에서는 한 경로만으로는 답이 나오지 않고 여러 경로에 유량을 나눠 싣는 것이 보통입니다.

이 도구는 결과를 내고 나서 유량 규칙을 다시 검사합니다. 어떤 간선도 용량을 넘지 않을 것, 그리고 출발점과 도착점을 뺀 모든 정점에서 들어온 양과 나간 양이 같을 것(보존) 두 가지이며, 화면에 통과 여부를 표시합니다.

전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.