나무 그래프

그래프 이론에서 **나무 그래프**(트리 그래프) 또는 단순히 **나무**(트리)는 순환을 갖지 않는 연결 그래프이다.
# 정의
그래프 T에 대하여 다음 조건들이 서로 동치이며, 이 조건을 만족시키는 그래프 T를 **숲 그래프**(포리스트 그래프)이라고 한다. * T는 (길이 3 이상의) 순환을 갖지 않는다. * 임의의 두 꼭짓점 v_1,v_2\in\operatorname V(T)에 대하여, v_1과 v_2 사이의 경로의 수는 1 이하이다. * T는 완전 그래프 K_3를 마이너로 갖지 않는다. * T는 단일 연결 공간이다. (즉, 임의의 밑점 v\in\operatorname V(T)에 대하여, 1차 세포 호몰로지 \operatorname H_1(T,v)가 자명군이다. 그러나 연결 공간이 아닐 수 있다.) 그래프 T에 대하여 다음 조건들이 서로 동치이며, 이 조건을 만족시키는 그래프 T를 **나무 그래프**라고 한다. * T는 숲 그래프이며, 연결 그래프이다 (즉, 정확히 1개의 연결 성분을 갖는다). * 임의의 두 꼭짓점 v_1,v_2\in V(T)에 대하여, v_1과 v_2 사이의 경로가 정확히 하나 존재한다. * T는 (1차원 세포 복합체로서) 연결 단일 연결 공간이다. (특히, 공집합이 아니다.) * 하나 이상의 꼭짓점을 가지며, 임의의 변 e\in\operatorname E(T)을 지운 그래프 T-e는 연결 그래프가 아니다. 나무 그래프 T의 **잎 꼭짓점**(리프 버텍스)은 차수가 1인 꼭짓점이며, **내부 꼭짓점**(internal vertex)은 차수가 2 이상인 꼭짓점이다.
# 성질
숲 그래프 T에 대하여 다음이 성립한다. * |\operatorname V(T)| = |\operatorname E(T)| + |\operatorname{Conn}(T)| 여기서 * |\operatorname V(T)|는 T의 꼭짓점의 수이다. * |\operatorname E(T)|는 T의 변의 수이다. * |\operatorname{Conn}(T)|는 T의 연결 성분의 수이다. 특히, 나무 그래프의 경우 하나의 연결 성분을 가지므로, |\operatorname V(T)|=|\operatorname E(T)|+1이다. 반대로 |\operatorname V(T)|=|\operatorname E(T)|+1인 유한 연결 그래프는 항상 나무 그래프이다. 모든 숲 그래프는 이분 그래프이자 평면 그래프이다.
## 나무 그래프의 수
n개의 꼭짓점을 갖는 나무 그래프의 동형류의 수는 다음과 같다 (n=0,1,2,\dots). :1, 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159, … A000055 n개의 꼭짓점을 갖는 숲 그래프의 동형류의 수는 다음과 같다 (n=0,1,2,\dots). :1, 1, 2, 3, 6, 10, 20, 37, 76, 153, 329, 710, 1601, 3658, … A005195
## 프뤼퍼 열
유한 나무 그래프 T의 꼭짓점 집합 :\operatorname V(T) 에 임의의 정렬 순서를 주고, 그 순서형을 n\in\operatorname{Ord}이라고 하자. T에 대하여, 꼭짓점 열 :x_0,x_1,\dotsc 을 다음과 같이 재귀적으로 정의하자. :x_i = \min\\{v\in \operatorname V(T)\setminus\\{x_j\\}_{j 즉, 다음과 같다. * 임의의 순서수 i < |\operatorname V(T)|에 대하여, x_i\in\operatorname V(T)은 T\setminus\\{x_j\\}_{j의 잎 꼭짓점 가운데, 정렬 순서에 대하여 최소 원소이다. 유한 나무 그래프의 경우, 이 열은 T의 모든 꼭짓점을 한 번씩 포함한다. 즉, T의 꼭짓점 집합 \operatorname V(T) 위의 또다른 정렬 순서를 정의한다. (반면, 무한 나무 그래프의 경우 이는 그렇지 못할 수 있다.) 또한, 다음과 같은 꼭짓점 열 :y_0,y_1,\dotsc 을 (x_i)_{i<|\operatorname V(T)|}로부터 정의할 수 있다. :(x_i,y_i) \in \operatorname E(T \setminus \\{x_j\\}_{j 즉, * y_i는 T\setminus\\{v_j\\}_{j에서 x_i와 인접한 유일한 내부 꼭짓점이다. (만약 이러한 꼭짓점이 존재하지 않는다면, 이 열은 끝나게 된다.) 유한 나무 그래프의 경우, 꼭짓점 열 y_i의 길이는 n-1인데, 이는 맨 “마지막”의 경우 꼭짓점이 하나 밖에 남지 않기 때문이다. (y_i)를 T의 **프뤼퍼 열**(Prüfer列, Prüfer sequence)이라고 한다. 또한, 프뤼퍼 열에 대하여 다음이 성립한다. {| class=wikitable ! 유한 나무 그래프 !! 프뤼퍼 열 |- | 꼭짓점의 수 || 프뤼퍼 열의 길이 + 2 |- | 변의 수 || 프뤼퍼 열의 길이 + 1 |- | 잎 꼭짓점 || 프뤼퍼 열에 등장하지 않는 꼭짓점 |- | 내부 꼭짓점 || 프뤼퍼 열에 등장하는 꼭짓점 |- | 꼭짓점의 차수 || 프뤼퍼 열에 등장하는 수 + 1 |} 모든 유한 나무 그래프는 그 프뤼퍼 열로부터 재구성될 수 있다. 이 알고리즘은 대략 다음과 같다. # 우선, 각 꼭짓점 v에 대하여 양의 정수 값의 변수 \mathtt{d}_v를, v_i가 프뤼퍼 열에 등장하는 수 + 1로 놓는다. # 프뤼퍼 열의 첫째 꼭짓점 y_0에 대하여, \mathsf d_v=1인 최소의 꼭짓점을 v라고 하면, ## 변 (v,a_v)를 그래프에 추가하며, ## \mathtt d_{y_0}과 \mathtt d_v를 각각 1만큼 감소시킨다. # 위 단계를 프뤼퍼 열의 둘째, 셋째 등등 꼭짓점에 대하여 반복한다. # 이 과정이 끝나면, \mathtt d_v=1인 꼭짓점이 두 개 남는다. 이들 사이에 변을 추가한다. # 알고리즘 종료. (반면, 무한 나무 그래프의 경우 이는 일반적으로 불가능하다. 예를 들어, 양쪽 무한 경로 그래프는 나무 그래프이지만, 잎 꼭짓점을 갖지 않아, 프뤼퍼 열이 자명하다.)
## 케일리 공식
임의의 크기 n의 유한 집합 V가 주어졌다고 하자. 그렇다면, V를 꼭짓점으로 하는 나무 그래프의 수를 T_n이라고 하자. (이 경우, 꼭짓점들이 서로 구별되므로, 이는 나무 그래프의 동형류의 수와 다르다.) **케일리 공식**(Cayley’s formula)에 따르면, 이는 다음과 같다.url-status= :T_n=n^{n-2}

**증명**:

꼭짓점 집합 V에 임의의 정렬 순서를 주자. 그렇다면, V 위의 임의의 나무 그래프는 프뤼퍼 열에 유일하게 대응하며, 반대로 모든 프뤼퍼 열은 나무 그래프에 유일하게 대응된다. 프뤼퍼 열의 수는 :n^{n-2} 이다.

크기 n의 유한 집합 위의 숲 그래프의 수는 다음과 같다. (n=0,1,2,\dotsc) :1, 1, 2, 7, 38, 291, 2932, 36961, 561948, 10026505, 205608536, 4767440679, 123373203208, 3525630110107, 110284283006640, 3748357699560961, 137557910094840848, 5421179050350334929, 228359487335194570528, 10239206473040881277575, 486909744862576654283616, … A1858 이 자연수열을 :c_i 라고 표기하면, 그 생성 함수는 :\sum_{i=0}^\infty \frac1{i!}c_ix^i = \exp\left(\sum_{n=1}^\infty n^{n-2} \frac1{n!}x^n\right)=1+x+\frac12(2x^2) + \frac16(7x^3)+\dotsb 이다.

**증명**:

크기 N의 집합의 분할에서, 크기 n의 성분의 수가 k_n이라고 하자. 즉, :\sum_{n=1}^\infty nk_n=N 이다. 이 경우, 주어진 분할을 연결 성분 분할로 갖는 숲 그래프의 수는 :\prod_{n=1}^\infty (T_n)^{k_n} 이다. 크기 N의 집합의 경우, 이러한 분할의 수는 :\binom{N!}{\prod_{n=1}^\infty (n!)^{k_n} k_n!} 이다. 따라서, 생성 함수 f(x)는 다음과 같은 유한 중복집합에 대한 합으로 나타내어진다. : \begin{aligned} f(x)&=\sum_{k\in M} \frac{x^{|k|{|k|!} \frac{|k|!}{\prod_{n=1}^\infty (n!)^{k_n} k_n!} \prod_{n=1}^\infty (T_n)^{k_n}\\\ &= \sum_{k\in M} \prod_{n=1}^\infty\left(\frac{T_nx_n}{n!}\right)^{k_n} \frac1{k_n!} \\\ & =\prod_{n=1}^\infty\sum_{k_n=0}^\infty\left(\frac{T_nx_n}{n!}\right)^{k_n} \frac1{k_n!} \\\ & =\prod_{n=1}^\infty\exp(T_nx^n/n!) \\\ & =\exp\left(\sum_{n=1}^\infty T_nx^n/n!\right) \end{aligned} 여기서 M는 유한 중복집합들, 즉 함수 :k\colon\mathbb Z^+\to\mathbb N :k\colon n\mapsto k_n 가운데 :\sum_{n=1}^\infty nk_n<\infty 인 것들의 족이며, :|k| = \sum_{n=1}^\infty nk_n 이다.

# 예
정의에 따라, 모든 무변 그래프는 숲 그래프이며, 특히 한원소 그래프 K_1은 나무 그래프이다. 임의의 양의 정수 n에 대하여, 경로 그래프 P_n은 나무 그래프이다. 또한, 양쪽 무한 경로 그래프 :P_\infty 및 한쪽 무한 경로 그래프 :P_\infty^+ 역시 둘 다 나무 그래프이다.
## 프뤼퍼 열의 예
다음과 같은 유한 나무 그래프 T를 생각하자. :파일:Tree 이 경우, # 잎 꼭짓점들은 \\{1,2,3,6\\}이며, 이 가운데 최솟값은 1이다. 이는 꼭짓점 4에 연결되어 있다. 즉, x_0=1이며 y_0=4이다. 이제, 꼭짓점 1을 제거하자. # T\setminus\\{1\\}에서, 잎 꼭짓점들은 \\{2,3,6\\}이며, 이 가운데 최솟값은 2이다. 이는 꼭짓점 4에 연결되어 있다. 즉, x_1=2이며 y_1=4이다. 이제, 꼭짓점 2를 제거하자. # T\setminus\\{1,2\\}에서, 잎 꼭짓점들은 \\{3,6\\}이며, 이 가운데 최솟값은 3이다. 이는 꼭짓점 4에 연결되어 있다. 즉, x_2=3이며 y_2=4이다. 이제, 꼭짓점 3을 제거하자. # T\setminus\\{1,2,3\\}에서, 잎 꼭짓점들은 \\{4,6\\}이며, 이 가운데 최솟값은 4이다. 이는 꼭짓점 5에 연결되어 있다. 즉, x_3=4이며 y_2=5이다. 이제, 꼭짓점 4를 제거하자. # T\setminus\\{1,2,3,4\\}에서, 잎 꼭짓점들은 \\{5,6\\}이며, 이 가운데 최솟값은 5이다. 즉, x_4=5이다. 이는 꼭짓점 6에 연결되어 있으나, 이 역시 잎 꼭짓점이므로, 프뤼퍼 열은 끝난다. 즉, :(y_0,\dotsc,y_4) = (4,4,4,5) 이다.
# 역사
케일리 공식은 1860년에 카를 빌헬름 보르하르트(Carl Wilhelm Borchardt, 1817~1880)가 최초로 증명하였다.언어=de 이후 1889년에 아서 케일리가 같은 정리의 새 증명을 발표하였다.언어=en 케일리는 보르하르트의 논문을 인용하였지만, 이 공식은 더 유명한 케일리의 이름을 따 불리게 되었다. 에른스트 파울 하인츠 프뤼퍼(Ernst Paul Heinz Prüfer, 1896~1934)는 1918년에 프뤼퍼 열을 도입하였으며, 이를 사용하여 이에 대한 다른 증명을 제시하였다.언어=en