다음과 같은 네트워크에서 노드 S로부터 G까지 모든 노드들에 원유를 공… | [물류관리사] 18년 1회차 기출문제 상세 페이지

모든 노드를 빠짐없이 연결하는 가장 짧은 네트워크는 최소신장나무(MST)이며, 그 총 길이는 20km다.
그림의 간선은 S-a 3, S-b 4, S-c 5, a-b 2, a-d 3, a-e 5, b-c 4, b-e 5, c-f 2, d-e 6, d-G 4, e-f 2, e-G 5, f-G 7(km)이다.
짧은 간선부터 순환이 생기지 않도록 고르면 a-b 2, c-f 2, e-f 2, S-a 3, a-d 3, b-c 4, d-G 4가 선택되어 8개 노드가 7개 간선으로 모두 이어진다.
송유관 총 길이 = 2+2+2+3+3+4+4 = 20km