생성나무

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

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

정의[편집]

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

최소 비용 생성 나무(minimum cost spanning tree)는 그래프의 각 변에 비용이 주어질 경우 생성 나무들 중에 비용이 최소인 것을 말한다.

성질[편집]

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

알고리즘[편집]

그래프의 최소 비용 생성 나무는 프림 알고리즘이나 크러스컬 알고리즘을 사용하여 다항 시간 안에 찾을 수 있다.

바깥 고리[편집]