다음 그림에서 숫자는 인접한 노드 간의 용량을 의미한다. 현재 노드 간… | [물류관리사] 18년 1회차 기출문제 상세 페이지
1[물류관리사] 18년 1회차
다음 그림에서 숫자는 인접한 노드 간의 용량을 의미한다. 현재 노드 간(c → d)의 용량은 7이다. 만약, 노드 간(c → d)의 용량이 7에서 2로 감소한다고 가정할 때, S에서 F까지의 최대 유량의 감소분은?
1
1
2
2
3
3
4
4
5
5
해설
c→d 용량이 7에서 2로 줄면 최대유량이 10에서 8로 떨어지므로 감소분은 2다.
그림의 용량은 S→a 6, S→c 7, a→b 3, c→b 4, c→d 7, b→F 6, d→F 5이다. 변경 전 최대유량은 S-a-b-F에 3(a→b 용량 3에 제한), S-c-b-F에 3(b→F 잔여 3), S-c-d-F에 4(S→c 잔여 4)를 흘려 10이 된다.
c→d가 2로 줄면 S-c-d-F 경로로는 2만 흘릴 수 있고 나머지 경로의 용량은 그대로이므로 최대유량은 3+3+2 = 8이 된다.
감소분 = 10 − 8 = 2
내용에 오류가 있거나 최신 법령·기준과 다른 부분이 보이면 알려주세요. 확인 후 반영하겠습니다.