다음 네트워크에서 7지점의 물류 창고를 모두 연결하는 도로를 개설하려 … | [물류관리사] 17년 1회차 기출문제 상세 페이지

7개 지점을 모두 연결하는 데 필요한 최소 도로 연장은 최소신장트리(MST)로 구하며 130 km이다.
그림의 구간 거리는 1-2 30, 1-3 20, 1-4 40, 2-3 50, 2-4 40, 3-4 40, 3-5 10, 3-6 30, 4-5 30, 4-7 20, 5-6 40, 5-7 30, 6-7 20 km이다.
짧은 구간부터 순환이 생기지 않도록 고르면 3-5(10) → 1-3(20) → 6-7(20) → 4-7(20) → 1-2(30) → 3-6(30)이 선택되어, 6개 구간으로 7개 지점이 모두 이어진다.
합계는 $10+20+20+20+30+30=130\ \mathrm{km}$이다. 같은 30 km인 4-5·5-7은 이미 연결된 지점끼리를 잇는 순환이 되어 채택되지 않으며, 지점 수 7개에 대해 간선은 6개면 충분하다.