다음 가중치 그래프에서 최소 비용 신장 트리(minimum cost s… | [계리직 컴퓨터일반] 22년 1회차 기출문제 상세 페이지

최소 비용 신장 트리의 가중치 합은 6이다.
크루스칼 알고리즘으로 가중치가 작은 간선부터 사이클이 생기지 않게 고르면 가중치 1인 간선 두 개와 가중치 2인 간선 두 개가 차례로 선택되고, 정점 5개가 간선 4개로 모두 연결된다.
합계는 1 + 1 + 2 + 2 = 6이며, 가중치 3·4인 간선은 이미 연결된 정점 사이에 사이클을 만들어 제외된다.
4: 정점 5개를 잇는 데 간선 4개가 필요하고 가장 작은 네 간선(1, 1, 2, 2)의 합이 이미 6이므로 나올 수 없는 값이다.
13: 가중치가 큰 간선(4, 4, 3, 2)으로 만든 최대 비용 신장 트리의 합이다.
17: 모든 간선의 가중치를 더한 값으로, 사이클이 포함되어 트리가 아니다.