다음 그림은 S에서 T까지의 최대유량을 구하는 문제이다. 가지의 수는 … | [물류관리사] 09년 1회차 기출문제 상세 페이지

1[물류관리사] 09년 1회차

다음 그림은 S에서 T까지의 최대유량을 구하는 문제이다. 가지의 수는 가지의 용량을 의미한다. 현재 가지(2,4)의 용량은 2이다. 만약 가지(2,4)의 용량이 2에서 6으로 변한다면 최대유량의 증가분은?

해설

가지(2,4)의 용량을 2에서 6으로 늘리면 최대유량은 1만큼 증가한다.

그림의 간선 용량은 S→1이 6, S→2가 6, 1→3이 3, 1→4가 4, 2→4가 2, 3→T가 6, 4→T가 6이다.

변경 전에는 아래쪽 경로가 2→4의 용량 2에 묶여 S→2로 2밖에 흘려보내지 못하고, 위쪽은 S→1의 용량 6이 한계이므로 최대유량은 $6 + 2 = 8$ 이다.

변경 후에는 T로 들어오는 3→T가 1→3의 용량 3 때문에 최대 3, 4→T가 최대 6으로 제한되므로 최대유량은 $3 + 6 = 9$ 가 된다.
따라서 증가분은 $9 - 8 = 1$ 이다.

내용에 오류가 있거나 최신 법령·기준과 다른 부분이 보이면 알려주세요. 확인 후 반영하겠습니다.