최소 신장 트리1 [그래프] 최소 신장 트리(Minimum spanning tree) 최소 신장 트리(Minimum Spanning Tree) 신장 트리(spanning)란? : 그래프 G를 구성하는 부그래프로서 G의 모든 정점을 포함하는 그래프. 최소 신장 트리란, 이러한 신장 트리들 중에서 에지의 가중치의 합이 최소인 신장트리를 말한다. 파란색으로 표시된 에지로 연결된 노드로 구성된 그래프가 위 그래프의 최소 신장 트리이다. 대표적인 응용 문제로는 각 도시를 연결하는 도로를 짓는데 드는 최소 비용 구하기 등이 있다. 최소 신장 트리의 성질 최소 신장 트리의 중요한 특징 세 가지. 1.트리성질 최소 신장 트리는 트리이기 때문에 당연히 트리가 가지는 성질을 똑같이 갖는다. 트리가 갖는 성질에는 다음과 같은 것이 있다. 노드의 수가 N개이면 에지의 수는 (N-1)개이다. 에지 하나를 삭제하.. 2021. 9. 15. 이전 1 다음