트리 (그래프 이론)

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색
꼭지점이 6개, 변이 5개인 트리. 트리는 꼭지점이 n개이면 변은 항상 n-1개이다.

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

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

성질[편집]

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