신장 트리

1 개요

spanning tree

신장 트리, 스패닝 트리, 생성나무, 걸침 나무

• 모든 꼭짓점을 포함하는 부분트리
• 연결 그래프의 부분 그래프로서, 모든 정점과 간선의 부분 집합으로 구성되는 트리
• 연결된 무향 그래프에서 그 그래프의 부분 그래프이면서 모든 꼭지점을 연결하는 트리
• 모든 노드는 1개 이상의 간선에 연결되어 있어야 함
• 한 그래프에 여러 개의 신장 트리가 있을 수 있음

 

 

2 같이 보기

• 최소 신장트리
• 트리 구조

3 참고

• https://en.wikipedia.org/wiki/Spanning_tree
• http://terms.naver.com/entry.nhn?docId=837730&cid=209&categoryId=209