8개의 지점을 연결하는 파이프라인을 설치하고자 한다. 모든 지점간의 운… | [물류관리사] 08년 1회차 기출문제 상세 페이지
1[물류관리사] 08년 1회차
8개의 지점을 연결하는 파이프라인을 설치하고자 한다. 모든 지점간의 운송이 가능한 최소 거리의 파이프라인망을 설치하였을 때 총 거리는 얼마인가? [단, 마디(Node)는 지점을 의미하고, 가지(Link)는 지점간의 연결 가능한 구간을 나타내며, 가지 위의 숫자는 두 지점간의 거리를 의미한다.]
1
112km
2
114km
3
116km
4
117km
5
118km
해설
모든 지점을 연결하는 최소신장나무(MST)를 구성하면 총 거리는 114km이다.
그림의 가지별 거리는 1–2 18, 1–3 24, 1–4 21, 2–3 12, 2–6 28, 3–4 17, 3–5 18, 3–6 26, 4–5 20, 4–7 33, 5–6 14, 5–7 16, 5–8 22, 6–8 25, 7–8 19km이다. 8개 마디를 모두 잇는 데 필요한 가지는 7개이다.
짧은 가지부터 고르되 회로가 생기면 건너뛰는 방식으로 선택하면 2–3(12), 5–6(14), 5–7(16), 3–4(17), 1–2(18), 3–5(18), 7–8(19)이 뽑힌다. 이 시점에 8개 지점이 모두 하나로 연결되므로 4–5(20)·1–4(21)·5–8(22)·1–3(24)·6–8(25)·3–6(26)·2–6(28)·4–7(33)은 이미 연결된 마디끼리를 다시 잇는 회로가 되어 모두 제외된다.
따라서 총 거리는 이다. 여기서 구하는 것은 두 지점 간 최단경로가 아니라 전체 연결비용의 최소화라는 점에 유의해야 한다.
내용에 오류가 있거나 최신 법령·기준과 다른 부분이 보이면 알려주세요. 확인 후 반영하겠습니다.