출발지에서 도착지까지 유류를 운송하는 파이프라인에서 c → b 구간의 … | [물류관리사] 25년 1회차 기출문제 상세 페이지

c → b 구간이 살아 있는 (ㄱ)의 최대유량은 30, 그 구간을 폐쇄한 (ㄴ)의 최대유량은 28이다.
파이프라인 용량은 출발→a 12, 출발→c 8, 출발→d 15, a→b 7, c→b 5, d→c 7, d→e 13, b→도착 10, c→도착 12, e→도착 9이다.
(ㄱ)에서는 출발→a→b→도착 7, 출발→c→도착 8, 출발→d→c→도착 4, 출발→d→c→b→도착 3, 출발→d→e→도착 8을 흘려 $7+8+4+3+8=30$이 된다. 이때 a→b(7) + 출발→c(8) + 출발→d(15) = 30이 최소절단이 되어 30을 넘길 수 없다.
(ㄴ)에서는 c→b가 막혀 b로 가는 경로가 a→b 하나뿐이므로 출발→a→b→도착 7, 출발→c→도착 8, 출발→d→c→도착 4, 출발→d→e→도착 9만 가능해 $7+8+4+9=28$이 된다. 여기서는 a→b(7) + c→도착(12) + e→도착(9) = 28이 최소절단이다.