나무 (그래프 이론)

위키백과, 우리 모두의 백과사전.
(트리 (그래프 이론)에서 넘어옴)
이동: 둘러보기, 검색
6개의 꼭짓점을 갖는 나무

그래프 이론에서, 나무(영어: tree 트리[*]순환을 갖지 않는 연결 그래프이다.

정의[편집]

(단순 무향) 그래프에 대하여 다음 조건들이 서로 동치이며, 이 조건을 만족시키는 그래프 T(영어: forest 포리스트[*])이라고 한다.

(단순 무향) 그래프에 대하여 다음 조건들이 서로 동치이며, 이 조건을 만족시키는 그래프 T나무라고 한다.

  • T는 연결 숲이다.
  • 임의의 두 꼭짓점 v_1,v_2\in V(T)에 대하여, v_1v_2 사이의 경로가 정확히 하나 존재한다.
  • T연결 단일연결공간이다.
  • 임의의 변 e\in E(T)을 지운 그래프 T-e는 연결 그래프가 아니다.

T(영어: leaf 리프[*])은 차수가 1 이하인 꼭짓점이며, 내부 꼭짓점(영어: internal vertex)은 차수가 2 이상인 꼭짓점이다.

성질[편집]

n개의 꼭짓점 및 c개의 연결 성분을 갖는 숲은 n-c개의 변을 갖는다. 특히, 공집합이 아닌 나무의 경우 c=1이므로 변의 수는 n-1이다.

모든 숲은 이분 그래프이자 평면 그래프이다. 경로 그래프는 나무이다.

케일리의 정리에 따르면, n개의 (이름 붙인) 꼭짓점 집합 위의 나무 구조의 수는 n^{n-2}이다. n개의 꼭짓점을 갖는 나무의 동형류의 수는 다음과 같다 (n=0,1,2,\dots).

1, 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159, … (OEIS의 수열 A000055)

n개의 꼭짓점을 갖는 숲의 동형류의 수는 다음과 같다 (n=0,1,2,\dots).

1, 1, 2, 3, 6, 10, 20, 37, 76, 153, 329, 710, 1601, 3658, … (OEIS의 수열 A005195)

바깥 고리[편집]