최소 비용 걸침 나무

위키백과 ― 우리 모두의 백과사전.

평면 그래프 상에서의 최소 비용 걸침 나무. 변에 비용이 주어진 평면 그래프 상에서 최소 비용 걸침 나무가 어떤 식으로 나타나는지를 간략히 볼 수 있다.
평면 그래프 상에서의 최소 비용 걸침 나무. 변에 비용이 주어진 평면 그래프 상에서 최소 비용 걸침 나무가 어떤 식으로 나타나는지를 간략히 볼 수 있다.

연결된 무향 그래프의 걸침 나무(혹은 신장트리. 영어: spanning tree)란 그 그래프의 부분 그래프이면서 모든 꼭지점을 연결하는 트리이다. 한 그래프에는 수많은 걸침 나무가 있을 수 있다. 만약 그래프의 각 변에 비용이 주어진 경우, 최소 비용 걸침 나무(영어: minimum cost spanning tree)란 걸침 나무 중에 비용이 최소인 것을 의미한다. 아래의 두 가지 알고리즘을 이용하면 최소 비용 걸침 나무를 다항식 시간 안에 찾을 수 있다.