MST1 [MST] N개의 핀을 두개씩 연결하기 위해서는 N-1개의 선이 필요하다. 여기서 방향이 없는 그래프 G = (V, E)가 사용되며 V는 핀의 집합, E는 핀 쌍의 가능한 연결 집합이다. 그리고 각 edge(u,v)는 E에 포함된다. 가중치(w)s는 u와v를 연결하는 데 드는 비용을 나타낸다. MST의 목표는 모든 노드를 연결할 때(비순환) 총 비용이 가장 적은 순환을 찾는 것이다.그래프 T는 비순환적이고 모든 정점을 연결하므로, 이는 하나의 트리를 형성하게 된다. 이는 그래프 G를 "포괄(spans)"하기 때문에 스패닝 트리(spanning tree)라고 부른다. T를 결정하는 문제를 우리는 최소신장 트리 문제로 부르기로 하였다.다음 그림은 연결된 그래프와 최소신장 트리 문제의 예시를 보여준다.이 챕터에서 우리는.. 2024. 12. 15. 이전 1 다음
