<보기>의 네트워크에서 분지에 붙여진 값은 거리를 나타낸다.… | [서울시 연구사 경영과학] 25년 1회차 기출문제 상세 페이지

1[서울시 연구사 경영과학] 25년 1회차
<보기>의 네트워크에서 분지에 붙여진 값은 거리를 나타낸다. 여섯 마디를 모두 잇는 최소신장나무문제(minimum spanning tree problem)에서 총 거리의 합은?
<보기>

문제 이미지
1
16
2
17
3
18
4
19
해설

크러스컬 방법으로 짧은 분지부터 사이클 없이 고르면 최소신장나무의 총 거리는 17이다.

그림의 분지는 1-2(5), 1-3(5), 1-4(7), 2-5(6), 3-4(2), 4-5(3), 4-6(2), 5-6(4)이다. 짧은 순으로 4-6(2), 3-4(2), 4-5(3)을 채택하고, 5-6(4)은 5-4-6과 사이클을 이루므로 제외한다.

남은 마디 1과 2는 1-2(5)와 1-3(5)로 연결하면 여섯 마디가 모두 이어진다(분지 5개).
2+2+3+5+5=172+2+3+5+5=17

  • 16: 분지 5개로 여섯 마디를 잇는 가장 짧은 조합보다 작아 불가능하다.
  • 18: 1-3(5) 대신 2-5(6)를 쓰는 등 더 긴 분지를 포함한 경우의 합이다.
  • 19: 1-4(7)처럼 긴 분지를 포함해 최소가 아니다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[서울시 연구사 경영과학] 25년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요서울시 연구사 경영과학 기출문제 암기장 전체 보기