가중치 그래프(weighted graph)의 최소비용 신장트리(mini… | [7급 국가직 자료구조론] 09년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 09년 1회차
가중치 그래프(weighted graph)의 최소비용 신장트리(minimum cost spanning tree)에 대한 설명으로 옳은 것은?
1
그래프에 존재하는 임의의 사이클을 구성하는 간선(edge)들 중 가중치가 가장 작은 간선은 항상 이 그래프의 최소비용 신장트리에 포함된다.
2
Dijkstra의 최단경로 알고리즘 수행 결과 생성되는 신장트리는 항상 최소비용 신장트리이다.
3
임의의 그래프에 대해 서로 다른 최소비용 신장트리가 항상 두 개 이상 존재한다.
4
간선의 가중치 값들이 서로 다르고 최소비용 신장트리가 존재하는 경우, 가중치 값이 가장 작은 간선은 항상 최소비용 신장트리에 포함된다.
해설

간선 가중치가 모두 다를 때 가장 작은 간선은 항상 최소비용 신장트리에 포함된다.

최소 간선 e를 뺀 최소비용 신장트리가 있다고 하면, e를 추가해 생긴 사이클에서 e보다 무거운 간선 하나를 빼면 비용이 더 작은 신장트리가 되어 모순이다. 크루스칼 알고리즘이 가장 먼저 선택하는 간선도 이 간선이다.

  • 사이클의 최소 간선이 항상 포함된다는 설명: 사이클 성질은 사이클의 가장 무거운 간선이 제외됨을 보장할 뿐이며, 최소 간선이라도 두 끝점을 더 가벼운 간선들로만 이루어진 다른 경로가 잇고 있으면 빠진다.
  • Dijkstra 결과가 최소비용 신장트리라는 설명: Dijkstra는 시작점에서 각 정점까지의 거리를 최소화하는 최단경로 트리를 만들 뿐, 간선 가중치의 총합을 최소화하지 않는다.
  • 최소비용 신장트리가 항상 두 개 이상이라는 설명: 간선 가중치가 모두 다르면 최소비용 신장트리는 유일하다.

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

이어서 풀어보기

[7급 국가직 자료구조론] 09년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 국가직 자료구조론 기출문제 암기장 전체 보기