가중치 그래프(weighted graph)의 최소비용 신장트리(minimum cost spanning tree)에 대한 설명으로 옳은 것은?
- ①그래프에 존재하는 임의의 사이클을 구성하는 간선(edge)들 중 가중치가 가장 작은 간선은 항상 이 그래프의 최소비용 신장트리에 포함된다.
- ②Dijkstra의 최단경로 알고리즘 수행 결과 생성되는 신장트리는 항상 최소비용 신장트리이다.
- ③임의의 그래프에 대해 서로 다른 최소비용 신장트리가 항상 두 개 이상 존재한다.
- ④간선의 가중치 값들이 서로 다르고 최소비용 신장트리가 존재하는 경우, 가중치 값이 가장 작은 간선은 항상 최소비용 신장트리에 포함된다.
선지를 골라 바로 채점해 보세요.
정답 ④
출처: 인사혁신처 공개 기출(공공데이터포털, 이용허락 제한 없음)