최대 유통(Max Flow) 문제가 다음과 같이 주어졌을 때, 경로 1… | [서울시 연구사 경영과학] 14년 1회차 기출문제 상세 페이지
1[서울시 연구사 경영과학] 14년 1회차
최대 유통(Max Flow) 문제가 다음과 같이 주어졌을 때, 경로 1-3-4-6-7을 통해 보낼 수 있는 제품의 양은 얼마인가? (단, 각 노드(node) 위의 숫자는 연결되어 있는 노드로 제품을 보낼 수 있는 최대 수송 용량을 나타낸다)
1
0
2
3
3
4
4
8
5
19
해설
경로 1-3-4-6-7로 보낼 수 있는 양은 경로상 호의 최소 용량인 3이다.
경로의 유량은 가장 작은 용량의 호(병목)가 결정한다. 각 호의 출발 노드 쪽 용량은 1→3이 4, 3→4가 3, 4→6이 4, 6→7이 8이다.
- 0은 경로상 모든 호의 정방향 용량이 양수이므로 해당하지 않는다.
- 4는 1→3, 4→6의 용량일 뿐이며 3→4 호의 용량 3을 넘을 수 없다.
- 8은 마지막 6→7 호의 용량으로, 앞쪽 병목을 무시한 값이다.
- 19는 용량을 모두 더한 값으로, 경로 유량은 합이 아니라 최솟값으로 정해진다.
오류나 개정된 내용이 보이면 알려주세요
