나무 그래프

틀:위키데이터 속성 추적 그래프 이론에서 나무 그래프(틀:Llang) 또는 단순히 나무는 순환을 갖지 않는 연결 그래프이다.

정의

그래프 $T$에 대하여 다음 조건들이 서로 동치이며, 이 조건을 만족시키는 그래프 $T$를 숲 그래프(틀:Llang)이라고 한다.

• $T$는 (길이 3 이상의) 순환을 갖지 않는다.
• 임의의 두 꼭짓점 $v_1,v_2\in \mathrm{V}(T)$에 대하여, $v_1$과 $v_2$ 사이의 경로의 수는 1 이하이다.
• $T$는 완전 그래프 $K_3$를 마이너로 갖지 않는다.
• $T$는 단일 연결 공간이다. (즉, 임의의 밑점 $v\in \mathrm{V}(T)$에 대하여, 1차 세포 호몰로지 ${\mathrm{H}}_1(T,v)$가 자명군이다. 그러나 연결 공간이 아닐 수 있다.)

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

• $T$는 숲 그래프이며, 연결 그래프이다 (즉, 정확히 1개의 연결 성분을 갖는다).
• 임의의 두 꼭짓점 $v_1,v_2\in V(T)$에 대하여, $v_1$과 $v_2$ 사이의 경로가 정확히 하나 존재한다.
• $T$는 (1차원 세포 복합체로서) 연결 단일 연결 공간이다. (특히, 공집합이 아니다.)
• 하나 이상의 꼭짓점을 가지며, 임의의 변 $e\in \mathrm{E}(T)$을 지운 그래프 $T-e$는 연결 그래프가 아니다.

나무 그래프 $T$의 잎 꼭짓점(틀:Llang)은 차수가 1인 꼭짓점이며, 내부 꼭짓점(틀:Llang)은 차수가 2 이상인 꼭짓점이다.

성질

숲 그래프 $T$에 대하여 다음이 성립한다.

• $|\mathrm{V}(T)|=|\mathrm{E}(T)|+|\mathrm{Conn}(T)|$

여기서

• $|\mathrm{V}(T)|$는 $T$의 꼭짓점의 수이다.
• $|\mathrm{E}(T)|$는 $T$의 변의 수이다.
• $|\mathrm{C}onn(T)|$는 $T$의 연결 성분의 수이다.

특히, 나무 그래프의 경우 하나의 연결 성분을 가지므로, $|\mathrm{V}(T)|=|\mathrm{E}(T)|+1$이다.

모든 숲 그래프는 이분 그래프이자 평면 그래프이다.

나무 그래프의 수

$n$개의 꼭짓점을 갖는 나무 그래프의 동형류의 수는 다음과 같다 ($n=0,1,2,\dots$).

1, 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159, … 틀:OEIS

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

1, 1, 2, 3, 6, 10, 20, 37, 76, 153, 329, 710, 1601, 3658, … 틀:OEIS

프뤼퍼 열

유한 나무 그래프 $T$의 꼭짓점 집합

$\mathrm{V}(T)$

에 임의의 정렬 순서를 주고, 그 순서형을 $n\in \mathrm{Ord}$이라고 하자.

$T$에 대하여, 꼭짓점 열

$x_0,x_1,\dots$

을 다음과 같이 재귀적으로 정의하자.

$x_i=\min \{v\in \mathrm{V}(T)\setminus \{x_j{\}}_{j<i}:{\mathrm{deg}}_{T\setminus \{x_j{\}}_{j<i}}v=1\}$

즉, 다음과 같다.

• 임의의 순서수 $i<|\mathrm{V}(T)|$에 대하여, $x_i\in \mathrm{V}(T)$은 $T\setminus \{x_j{\}}_{j<i}$의 잎 꼭짓점 가운데, 정렬 순서에 대하여 최소 원소이다.

유한 나무 그래프의 경우, 이 열은 $T$의 모든 꼭짓점을 한 번씩 포함한다. 즉, $T$의 꼭짓점 집합 $\mathrm{V}(T)$ 위의 또다른 정렬 순서를 정의한다. (반면, 무한 나무 그래프의 경우 이는 그렇지 못할 수 있다.)

또한, 다음과 같은 꼭짓점 열

$y_0,y_1,\dots$

을 $(x_i{)}_{i<|\mathrm{V}(T)|}$로부터 정의할 수 있다.

$(x_i,y_i)\in \mathrm{E}(T\setminus \{x_j{\}}_{j<i})$

즉,

• $y_i$는 $T\setminus \{v_j{\}}_{j<i}$에서 $x_i$와 인접한 유일한 내부 꼭짓점이다. (만약 이러한 꼭짓점이 존재하지 않는다면, 이 열은 끝나게 된다.)

유한 나무 그래프의 경우, 꼭짓점 열 $y_i$의 길이는 $n-1$인데, 이는 맨 “마지막”의 경우 꼭짓점이 하나 밖에 남지 않기 때문이다.

$(y_i)$를 $T$의 프뤼퍼 열(Prüfer列, 틀:Llang)이라고 한다.

또한, 프뤼퍼 열에 대하여 다음이 성립한다.

유한 나무 그래프	프뤼퍼 열
꼭짓점의 수	프뤼퍼 열의 길이 + 2
변의 수	프뤼퍼 열의 길이 + 1
잎 꼭짓점	프뤼퍼 열에 등장하지 않는 꼭짓점
내부 꼭짓점	프뤼퍼 열에 등장하는 꼭짓점
꼭짓점의 차수	프뤼퍼 열에 등장하는 수 + 1

모든 유한 나무 그래프는 그 프뤼퍼 열로부터 재구성될 수 있다. 이 알고리즘은 대략 다음과 같다.

1. 우선, 각 꼭짓점 $v$에 대하여 양의 정수 값의 변수 ${𝚍}_v$를, $v_i$가 프뤼퍼 열에 등장하는 수 + 1로 놓는다.
2. 프뤼퍼 열의 첫째 꼭짓점 $y_0$에 대하여, ${𝖽}_v=1$인 최소의 꼭짓점을 $v$라고 하면,
   1. 변 $(v,a_v)$를 그래프에 추가하며,
   2. ${𝚍}_{y_0}$과 ${𝚍}_v$를 각각 1만큼 감소시킨다.
3. 위 단계를 프뤼퍼 열의 둘째, 셋째 등등 꼭짓점에 대하여 반복한다.
4. 이 과정이 끝나면, ${𝚍}_v=1$인 꼭짓점이 두 개 남는다. 이들 사이에 변을 추가한다.
5. 알고리즘 종료.

(반면, 무한 나무 그래프의 경우 이는 일반적으로 불가능하다. 예를 들어, 양쪽 무한 경로 그래프는 나무 그래프이지만, 잎 꼭짓점을 갖지 않아, 프뤼퍼 열이 자명하다.)

케일리 공식

임의의 크기 $n$의 유한 집합 $V$가 주어졌다고 하자. 그렇다면, $V$를 꼭짓점으로 하는 나무 그래프의 수를 $T_n$이라고 하자. (이 경우, 꼭짓점들이 서로 구별되므로, 이는 나무 그래프의 동형류의 수와 다르다.) 케일리 공식(틀:Llang)에 따르면, 이는 다음과 같다.

$T_n=n^{n-2}$

증명:

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

$n^{n-2}$

이다.

크기 $n$의 유한 집합 위의 숲 그래프의 수는 다음과 같다. ($n=0,1,2,\dots$)

1, 1, 2, 7, 38, 291, 2932, 36961, 561948, 10026505, 205608536, 4767440679, 123373203208, 3525630110107, 110284283006640, 3748357699560961, 137557910094840848, 5421179050350334929, 228359487335194570528, 10239206473040881277575, 486909744862576654283616, … 틀:OEIS

이 자연수열을

$c_i$

라고 표기하면, 그 생성 함수는

$\sum _{i=0}^{\mathrm{\infty }}\frac{1}{i!}{c}_i{x}^i=\exp \left(\sum _{n=1}^{\mathrm{\infty }}{n}^{n-2}\frac{1}{n!}{x}^n\right)=1+x+\frac{1}{2}(2x^2)+\frac{1}{6}(7x^3)+\cdots$

이다.

증명:

크기 $N$의 집합의 분할에서, 크기 $n$의 성분의 수가 $k_n$이라고 하자. 즉,

$\sum _{n=1}^{\mathrm{\infty }}n{k}_n=N$

이다.

이 경우, 주어진 분할을 연결 성분 분할로 갖는 숲 그래프의 수는

$\prod _{n=1}^{\mathrm{\infty }}(T_n{)}^{k_n}$

이다.

크기 $N$의 집합의 경우, 이러한 분할의 수는

$(\genfrac{}{}{0ex}{}{N!}{\prod _{n=1}^{\mathrm{\infty }}(n!{)}^{k_n}{k}_n!})$

이다.

따라서, 생성 함수 $f(x)$는 다음과 같은 유한 중복집합에 대한 합으로 나타내어진다.

$\begin{array}{cc}f(x)& =\sum _{k\in M}\frac{x^{|k|}}{|k|!}\frac{|k|!}{\prod _{n=1}^{\mathrm{\infty }}(n!{)}^{k_n}{k}_n!}\prod _{n=1}^{\mathrm{\infty }}(T_n{)}^{k_n}\\ & =\sum _{k\in M}\frac{|k|!}{|k|!}\frac{x^{|k|}\prod _{n=1}^{\mathrm{\infty }}(T_n{)}^{k_n}}{\prod _{n=1}^{\mathrm{\infty }}(n!{)}^{k_n}{k}_n!}\\ & =\sum _{k\in M}{x}^{|k|}\prod _{n=1}^{\mathrm{\infty }}{\left(\frac{T_n}{n!}\right)}^{k_n}\frac{1}{k_n!}\\ & =\sum _{k\in M}{x}^{\sum _{n=1}^{\mathrm{\infty }}n{k}_n}\prod _{n=1}^{\mathrm{\infty }}{\left(\frac{T_n}{n!}\right)}^{k_n}\frac{1}{k_n!}\\ & =\sum _{k\in M}\prod _{n=1}^{\mathrm{\infty }}{x}_n^{k_n}\prod _{n=1}^{\mathrm{\infty }}{\left(\frac{T_n}{n!}\right)}^{k_n}\frac{1}{k_n!}\\ & =\sum _{k\in M}\prod _{n=1}^{\mathrm{\infty }}{\left(\frac{T_n{x}_n}{n!}\right)}^{k_n}\frac{1}{k_n!}\\ & =\prod _{n=1}^{\mathrm{\infty }}\sum _{k_n=0}^{\mathrm{\infty }}{\left(\frac{T_n{x}_n}{n!}\right)}^{k_n}\frac{1}{k_n!}\\ & =\prod _{n=1}^{\mathrm{\infty }}\exp \left(\frac{T_n{x}^n}{n!}\right)\\ & =\exp \left(\sum _{n=1}^{\mathrm{\infty }}\frac{T_n{x}^n}{n!}\right)\\ & =\exp \left(\sum _{n=1}^{\mathrm{\infty }}{T}_n\frac{1}{n!}{x}^n\right)\end{array}$

여기서 $M$는 유한 중복집합들, 즉 함수

$k:{\mathbb{Z}}^{+}\to \mathbb{N}$

$k:n\mapsto k_n$

가운데

$\sum _{n=1}^{\mathrm{\infty }}n{k}_n<\mathrm{\infty }$

인 것들의 족이며,

$|k|=\sum _{n=1}^{\mathrm{\infty }}n{k}_n$

이고,

$T_n=n^{n-2}$이다.

예

정의에 따라, 모든 무변 그래프는 숲 그래프이며, 특히 한원소 그래프 $K_1$은 나무 그래프이다.

임의의 양의 정수 $n$에 대하여, 경로 그래프 $P_n$은 나무 그래프이다. 또한, 양쪽 무한 경로 그래프

$P_{\mathrm{\infty }}$

및 한쪽 무한 경로 그래프

$P_{\mathrm{\infty }}^{+}$

역시 둘 다 나무 그래프이다.

프뤼퍼 열의 예

다음과 같은 유한 나무 그래프 $T$를 생각하자.

이 경우,

1. 잎 꼭짓점들은 $\{1,2,3,6\}$이며, 이 가운데 최솟값은 1이다. 이는 꼭짓점 4에 연결되어 있다. 즉, $x_0=1$이며 $y_0=4$이다. 이제, 꼭짓점 1을 제거하자.
2. $T\setminus \{1\}$에서, 잎 꼭짓점들은 $\{2,3,6\}$이며, 이 가운데 최솟값은 2이다. 이는 꼭짓점 4에 연결되어 있다. 즉, $x_1=2$이며 $y_1=4$이다. 이제, 꼭짓점 2를 제거하자.
3. $T\setminus \{1,2\}$에서, 잎 꼭짓점들은 $\{3,6\}$이며, 이 가운데 최솟값은 3이다. 이는 꼭짓점 4에 연결되어 있다. 즉, $x_2=3$이며 $y_2=4$이다. 이제, 꼭짓점 3을 제거하자.
4. $T\setminus \{1,2,3\}$에서, 잎 꼭짓점들은 $\{4,6\}$이며, 이 가운데 최솟값은 4이다. 이는 꼭짓점 5에 연결되어 있다. 즉, $x_3=4$이며 $y_2=5$이다. 이제, 꼭짓점 4를 제거하자.
5. $T\setminus \{1,2,3,4\}$에서, 잎 꼭짓점들은 $\{5,6\}$이며, 이 가운데 최솟값은 5이다. 즉, $x_4=5$이다. 이는 꼭짓점 6에 연결되어 있으나, 이 역시 잎 꼭짓점이므로, 프뤼퍼 열은 끝난다.

즉,

$(y_0,\dots ,y_4)=(4,4,4,5)$

이다.

역사

케일리 공식은 1860년에 카를 빌헬름 보르하르트(틀:Llang, 1817~1880)가 최초로 증명하였다. 이후 1889년에 아서 케일리가 같은 정리의 새 증명을 발표하였다. 케일리는 보르하르트의 논문을 인용하였지만, 이 공식은 더 유명한 케일리의 이름을 따 불리게 되었다.

에른스트 파울 하인츠 프뤼퍼(틀:Llang, 1896~1934)는 1918년에 프뤼퍼 열을 도입하였으며, 이를 사용하여 이에 대한 다른 증명을 제시하였다.

같이 보기

• 결정 트리
• 트리 구조 (모델)
• 트리 구조

외부 링크

• 틀:Eom
• 틀:매스월드
• 틀:매스월드
• 틀:매스월드