생성나무

위키백과, 우리 모두의 백과사전.
(신장 트리에서 넘어옴)
이동: 둘러보기, 검색
평면 그래프 상에서의 최소 비용 생성나무. 변에 비용이 주어진 평면 그래프 상에서 최소 비용 생성나무가 어떤 식으로 나타나는지를 간략히 볼 수 있다.

그래프 이론에서, 생성나무(生成나무, 영어: spanning tree 스패닝 트리[*])는 모든 꼭지점을 포함하는 부분나무이다.

정의[편집]

무향 그래프 G생성나무G의 모든 꼭지점을 포함하고, 나무를 이루는 G부분그래프이다.

한 그래프에는 수많은 생성나무가 있을 수 있다. 모든 유한 연결그래프는 적어도 하나의 생성나무가 존재하며, 선택 공리를 가정하면 모든 연결그래프에서는 적어도 하나의 생성나무가 존재한다. 비연결그래프의 경우 생성나무가 존재하지 않는다. (그러나 이 경우 생성숲이 존재한다.)

최소 비용 생성나무[편집]

최소 비용 생성나무(minimum cost spanning tree)는 그래프의 각 변에 비용이 주어질 경우 생성나무들 중에 비용이 최소인 것을 말한다. 아래의 알고리즘을 이용하면 최소 비용 생성나무를 다항식 시간 내에 찾을 수 있다.

같이 보기[편집]

바깥 고리[편집]