트리

다른 뜻에 대해서는 트리 (동음이의) 문서를 참조하십시오.

꼭지점이 6개, 변이 5개인 트리. 트리는 꼭지점이 n개이면 변은 항상 n-1개이다.

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

한 개 이상의 트리로 이루어진 집합은 포레스트(forest)라고 부른다.

성질

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