나무 그래프

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

정의

그래프 ${\displaystyle T}$에 대하여 다음 조건들이 서로 동치이며, 이 조건을 만족시키는 그래프 ${\displaystyle T}$를 숲 그래프(영어: forest graph 포리스트 그래프^[*])이라고 한다.

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

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

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

나무 그래프 ${\displaystyle T}$의 잎 꼭짓점(영어: leaf vertex 리프 버텍스^[*])은 차수가 1인 꼭짓점이며, 내부 꼭짓점(영어: internal vertex)은 차수가 2 이상인 꼭짓점이다.

성질

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

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

여기서

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

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

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

나무 그래프의 수

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

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

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

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

프뤼퍼 열

유한 나무 그래프 ${\displaystyle T}$의 꼭짓점 집합

${\displaystyle \operatorname {V} (T)}$

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

${\displaystyle T}$에 대하여, 꼭짓점 열

${\displaystyle x_{0},x_{1},\dotsc }$

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

${\displaystyle x_{i}=\min\{v\in \operatorname {V} (T)\setminus \{x_{j}\}_{j<i}\colon \deg _{T\setminus \{x_{j}\}_{j<i}}v=1\}}$

즉, 다음과 같다.

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

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

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

${\displaystyle y_{0},y_{1},\dotsc }$

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

${\displaystyle (x_{i},y_{i})\in \operatorname {E} (T\setminus \{x_{j}\}_{j<i})}$

즉,

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

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

${\displaystyle (y_{i})}$를 ${\displaystyle T}$의 프뤼퍼 열(Prüfer列, 영어: Prüfer sequence)이라고 한다.

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

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

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

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

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

케일리 공식

임의의 크기 ${\displaystyle n}$의 유한 집합 ${\displaystyle V}$가 주어졌다고 하자. 그렇다면, ${\displaystyle V}$를 꼭짓점으로 하는 나무 그래프의 수를 ${\displaystyle T_{n}}$이라고 하자. (이 경우, 꼭짓점들이 서로 구별되므로, 이는 나무 그래프의 동형류의 수와 다르다.) 케일리 공식(영어: Cayley’s formula)에 따르면, 이는 다음과 같다.^[1]

${\displaystyle T_{n}=n^{n-2}}$

증명:

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

${\displaystyle n^{n-2}}$

이다.

크기 ${\displaystyle n}$의 유한 집합 위의 숲 그래프의 수는 다음과 같다. (${\displaystyle 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, … (OEIS의 수열 A1858)

이 자연수열을

${\displaystyle c_{i}}$

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

${\displaystyle \sum _{i=0}^{\infty }{\frac {1}{i!}}c_{i}x^{i}=\exp \left(\sum _{n=1}^{\infty }n^{n-2}{\frac {1}{n!}}x^{n}\right)=1+x+{\frac {1}{2}}(2x^{2})+{\frac {1}{6}}(7x^{3})+\dotsb }$

이다.

증명:

크기 ${\displaystyle N}$의 집합의 분할에서, 크기 ${\displaystyle n}$의 성분의 수가 ${\displaystyle k_{n}}$이라고 하자. 즉,

${\displaystyle \sum _{n=1}^{\infty }nk_{n}=N}$

이다.

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

${\displaystyle \prod _{n=1}^{\infty }(T_{n})^{k_{n}}}$

이다.

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

${\displaystyle {\binom {N!}{\prod _{n=1}^{\infty }(n!)^{k_{n}}k_{n}!}}}$

이다.

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

${\displaystyle {\begin{aligned}f(x)&=\sum _{k\in M}{{x^{|k|}} \over {|k|!}}{{|k|!} \over {\prod _{n=1}^{\infty }(n!)^{k_{n}}k_{n}!}}\prod _{n=1}^{\infty }(T_{n})^{k_{n}}\\&=\sum _{k\in M}{{|k|!} \over {|k|!}}{{x^{|k|}{\prod _{n=1}^{\infty }(T_{n})^{k_{n}}}} \over {\prod _{n=1}^{\infty }(n!)^{k_{n}}{k_{n}!}}}\\&=\sum _{k\in M}{x^{|k|}}\prod _{n=1}^{\infty }\left({{T_{n}} \over {n!}}\right)^{k_{n}}{{1} \over {k_{n}!}}\\&=\sum _{k\in M}{x^{\sum _{n=1}^{\infty }nk_{n}}}\prod _{n=1}^{\infty }\left({{T_{n}} \over {n!}}\right)^{k_{n}}{{1} \over {k_{n}!}}\\&=\sum _{k\in M}\prod _{n=1}^{\infty }{x_{n}^{k_{n}}}\prod _{n=1}^{\infty }\left({{T_{n}} \over {n!}}\right)^{k_{n}}{{1} \over {k_{n}!}}\\&=\sum _{k\in M}\prod _{n=1}^{\infty }\left({{T_{n}x_{n}} \over {n!}}\right)^{k_{n}}{{1} \over {k_{n}!}}\\&=\prod _{n=1}^{\infty }\sum _{k_{n}=0}^{\infty }\left({{T_{n}x_{n}} \over {n!}}\right)^{k_{n}}{{1} \over {k_{n}!}}\\&=\prod _{n=1}^{\infty }\exp \left({{T_{n}x^{n}} \over {n!}}\right)\\&=\exp \left(\sum _{n=1}^{\infty }{{T_{n}x^{n}} \over {n!}}\right)\\&=\exp \left(\sum _{n=1}^{\infty }T_{n}{{1} \over {n!}}x^{n}\right)\end{aligned}}}$

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

${\displaystyle k\colon \mathbb {Z} ^{+}\to \mathbb {N} }$

${\displaystyle k\colon n\mapsto k_{n}}$

가운데

${\displaystyle \sum _{n=1}^{\infty }nk_{n}<\infty }$

인 것들의 족이며,

${\displaystyle |k|=\sum _{n=1}^{\infty }nk_{n}}$

이고,

${\displaystyle T_{n}=n^{n-2}}$이다.

예

정의에 따라, 모든 무변 그래프는 숲 그래프이며, 특히 한원소 그래프 ${\displaystyle K_{1}}$은 나무 그래프이다.

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

${\displaystyle P_{\infty }}$

및 한쪽 무한 경로 그래프

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

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

프뤼퍼 열의 예

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

이 경우,

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

즉,

${\displaystyle (y_{0},\dotsc ,y_{4})=(4,4,4,5)}$

이다.

역사

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

에른스트 파울 하인츠 프뤼퍼(독일어: Ernst Paul Heinz Prüfer, 1896~1934)는 1918년에 프뤼퍼 열을 도입하였으며, 이를 사용하여 이에 대한 다른 증명을 제시하였다.^[4]

같이 보기

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

각주

1. 서승현; 권석일; 홍진곤 (2008년 8월). “케일리 공식의 네 가지 증명”. 《한국수학사학회지》 21 (3): 127–142. 2021년 3월 8일에 원본 문서에서 보존된 문서. 2017년 7월 10일에 확인함.
2. Borchardt, Carl Wilhelm (1860). “Über eine Interpolationsformel für eine Art Symmetrischer Functionen und über Deren Anwendung”. 《Abhandlungen der Königlichen Akademie der Wissenschaften zu Berlin. Mathematische Klasse》 (독일어): 1–20.
3. Cayley, Arthur (1889). “A theorem on trees”. 《The Quarterly Journal of Pure and Applied Mathematics》 (영어) 23: 376–378. JFM 21.0687.01.
4. Prüfer, Heinz (1918). “Neuer Beweis eines Satzes über Permutationen”. 《Archiv der Mathematik und Physik》 (영어) 27: 742–744. JFM 46.0106.04.

외부 링크

• “Tree”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4.
• Weisstein, Eric Wolfgang. “Tree”. 《Wolfram MathWorld》 (영어). Wolfram Research.
• Weisstein, Eric Wolfgang. “Forest”. 《Wolfram MathWorld》 (영어). Wolfram Research.
• Weisstein, Eric Wolfgang. “Prüfer code”. 《Wolfram MathWorld》 (영어). Wolfram Research.