나무 그래프: 두 판 사이의 차이

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

* 꼭지점이 n개이면<math>n</math>개이면 변은 <math>n-1개이다1</math>개이다.

* 어떤 두 꼭지점을 택하여도 그 둘 사이를 잇는 [[그래프 이론 용어사전|경로]]는경로는 하나밖에 없다.

* 꼭지점의 집합이 <math>\{1,2,3,...,n\}</math>인 트리는 n<supmath>n^{n-2}</supmath>개가 존재한다. ([[아서 케일리|케일리]]의 정리)