나무 (그래프 이론)

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

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

(영어: forest 포리스트[*])은 회로가 없는 그래프이다. 즉, 숲은 나무들의 분리합집합이다.

성질[편집]

모든 나무는 다음 성질들을 만족시킨다.

  • 꼭짓점이 n개이면 변은 n-1개이다.
  • 꼭짓점이 두 개 이상인 나무는 항상 잎이 두 개 이상 있다.
  • 이분 그래프이다.
  • 평면 그래프이다.
  • 숲이다.
  • 어떤 두 꼭지점을 택하여도 그 둘 사이를 잇는 경로는 하나밖에 없다.
  • 변을 하나라도 지우면 그래프가 더 이상 연결되어 있지 않다.

나무들의 수는 다음과 같이 주어진다.

  • 꼭지점의 집합이 \{1,2,3,\cdots ,n\}인 나무는 n^{n-2}개가 존재한다. (케일리의 정리)

바깥 고리[편집]