트리

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

수학의 그래프 이론에서 트리(영어: tree), 나무, 혹은 수형도(樹形圖)란 회로가 없으면서 연결된 그래프를 뜻한다. 회로가 없기 때문에 그래프 중에서도 다루기가 가장 간단하다. 나무의 잎이란, 차수가 1인 꼭지점을 뜻한다.

[편집] 나무의 성질

• 꼭지점이 n개이면 변은 n-1개이다.
• 꼭지점이 두 개 이상인 나무는 항상 잎이 두 개 이상 있다.
• 나무는 이분 그래프이다.
• 나무는 평면 그래프이다.
• 나무는 포레스트이다.
• 어떤 두 꼭지점을 택하여도 그 둘 사이를 잇는 경로는 하나밖에 없다.
• 변을 하나라도 지우면 그래프가 더 이상 연결되어 있지 않다.
• 꼭지점의 집합이 {1,2,3,...,n}인 나무는 n^n-2개가 존재한다. (케일리의 정리)