나무 그래프 문서 원본 보기

{{위키데이터 속성 추적}}
[[그래프 이론]]에서 '''나무 그래프'''({{llang|en|tree graph|트리 그래프}}) 또는 단순히 '''나무'''는 [[순환 (그래프 이론)|순환]]을 갖지 않는 [[연결 그래프]]이다.

== 정의 ==
[[그래프]] <math>T</math>에 대하여 다음 조건들이 서로 [[동치]]이며, 이 조건을 만족시키는 그래프 <math>T</math>를 '''숲 그래프'''({{llang|en|forest graph|포리스트 그래프}})이라고 한다.

* <math>T</math>는 (길이 3 이상의) [[순환 (그래프 이론)|순환]]을 갖지 않는다.
* 임의의 두 꼭짓점 <math>v_1,v_2\in\operatorname V(T)</math>에 대하여, <math>v_1</math>과 <math>v_2</math> 사이의 [[경로 (그래프 이론)|경로]]의 수는 1 이하이다.
* <math>T</math>는 [[완전 그래프]] <math>K_3</math>를 [[마이너 (그래프 이론)|마이너]]로 갖지 않는다.
* <math>T</math>는 [[단일 연결 공간]]이다. (즉, 임의의 밑점 <math>v\in\operatorname V(T)</math>에 대하여, 1차 [[세포 호몰로지]] <math>\operatorname H_1(T,v)</math>가 [[자명군]]이다. 그러나 [[연결 공간]]이 아닐 수 있다.)

[[그래프]] <math>T</math>에 대하여 다음 조건들이 서로 [[동치]]이며, 이 조건을 만족시키는 그래프 <math>T</math>를 '''나무 그래프'''라고 한다.
* <math>T</math>는 숲 그래프이며, [[연결 그래프]]이다 (즉, 정확히 1개의 [[연결 성분]]을 갖는다).
* 임의의 두 꼭짓점 <math>v_1,v_2\in V(T)</math>에 대하여, <math>v_1</math>과 <math>v_2</math> 사이의 [[경로 (그래프 이론)|경로]]가 정확히 하나 존재한다.
* <math>T</math>는 (1차원 [[세포 복합체]]로서) [[연결 공간|연결]] [[단일 연결 공간]]이다. (특히, [[공집합]]이 아니다.)
* 하나 이상의 꼭짓점을 가지며, 임의의 변 <math>e\in\operatorname E(T)</math>을 지운 그래프 <math>T-e</math>는 [[연결 그래프]]가 아니다.

나무 그래프 <math>T</math>의 '''잎 꼭짓점'''({{llang|en|leaf vertex|리프 버텍스}})은 차수가 1인 꼭짓점이며, '''내부 꼭짓점'''({{llang|en|internal vertex}})은 차수가 2 이상인 꼭짓점이다.

== 성질 ==
숲 그래프 <math>T</math>에 대하여 다음이 성립한다.
* <math>|\operatorname V(T)| = |\operatorname E(T)| + |\operatorname{Conn}(T)|</math>
여기서
* <math>|\operatorname V(T)|</math>는 <math>T</math>의 꼭짓점의 수이다.
* <math>|\operatorname E(T)|</math>는 <math>T</math>의 변의 수이다.
* <math>|\operatorname Conn(T)|</math>는 <math>T</math>의 연결 성분의 수이다.

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

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

=== 나무 그래프의 수 ===
<math>n</math>개의 꼭짓점을 갖는 나무 그래프의 [[동형|동형류]]의 수는 다음과 같다 (<math>n=0,1,2,\dots</math>).
:1, 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159, … {{OEIS|A000055}}

<math>n</math>개의 꼭짓점을 갖는 숲 그래프의 [[동형|동형류]]의 수는 다음과 같다 (<math>n=0,1,2,\dots</math>).
:1, 1, 2, 3, 6, 10, 20, 37, 76, 153, 329, 710, 1601, 3658, … {{OEIS|A005195}}

=== 프뤼퍼 열 ===
유한 나무 그래프 <math>T</math>의 꼭짓점 집합
:<math>\operatorname V(T)</math>
에 임의의 [[정렬 순서]]를 주고, 그 [[순서형]]을 <math>n\in\operatorname{Ord}</math>이라고 하자.

<math>T</math>에 대하여, 꼭짓점 [[수열|열]]
:<math>x_0,x_1,\dotsc</math>
을 다음과 같이 재귀적으로 정의하자.
:<math>x_i = \min\{v\in \operatorname V(T)\setminus\{x_j\}_{j<i}
\colon \deg_{T\setminus\{x_j\}_{j<i}} v = 1\}</math>
즉, 다음과 같다.
* 임의의 순서수 <math>i < |\operatorname V(T)|</math>에 대하여, <math>x_i\in\operatorname V(T)</math>은 <math>T\setminus\{x_j\}_{j<i}</math>의 잎 꼭짓점 가운데, [[정렬 순서]]에 대하여 [[최소 원소]]이다.
유한 나무 그래프의 경우, 이 열은 <math>T</math>의 모든 꼭짓점을 한 번씩 포함한다. 즉, <math>T</math>의 꼭짓점 집합 <math>\operatorname V(T)</math> 위의 또다른 [[정렬 순서]]를 정의한다. (반면, 무한 나무 그래프의 경우 이는 그렇지 못할 수 있다.)

또한, 다음과 같은 꼭짓점 열
:<math>y_0,y_1,\dotsc</math>
을 <math>(x_i)_{i<|\operatorname V(T)|}</math>로부터 정의할 수 있다.
:<math>(x_i,y_i) \in \operatorname E(T \setminus \{x_j\}_{j<i})</math>
즉,
* <math>y_i</math>는 <math>T\setminus\{v_j\}_{j<i}</math>에서 <math>x_i</math>와 인접한 유일한 내부 꼭짓점이다. (만약 이러한 꼭짓점이 존재하지 않는다면, 이 열은 끝나게 된다.)

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

<math>(y_i)</math>를 <math>T</math>의 '''프뤼퍼 열'''(Prüfer列, {{llang|en|Prüfer sequence}})이라고 한다.

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

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

모든 유한 나무 그래프는 그 프뤼퍼 열로부터 재구성될 수 있다. 이 알고리즘은 대략 다음과 같다.
# 우선, 각 꼭짓점 <math>v</math>에 대하여 양의 정수 값의 변수 <math>\mathtt{d}_v</math>를, <math>v_i</math>가 프뤼퍼 열에 등장하는 수 + 1로 놓는다.
# 프뤼퍼 열의 첫째 꼭짓점 <math>y_0</math>에 대하여, <math>\mathsf d_v=1</math>인 최소의 꼭짓점을 <math>v</math>라고 하면,
## 변 <math>(v,a_v)</math>를 [[그래프]]에 추가하며,
## <math>\mathtt d_{y_0}</math>과 <math>\mathtt d_v</math>를 각각 1만큼 감소시킨다.
# 위 단계를 프뤼퍼 열의 둘째, 셋째 등등 꼭짓점에 대하여 반복한다.
# 이 과정이 끝나면, <math>\mathtt d_v=1</math>인 꼭짓점이 두 개 남는다. 이들 사이에 변을 추가한다.
# 알고리즘 종료.

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

=== 케일리 공식 ===
임의의 크기 <math>n</math>의 [[유한 집합]] <math>V</math>가 주어졌다고 하자. 그렇다면, <math>V</math>를 꼭짓점으로 하는 나무 그래프의 수를 <math>T_n</math>이라고 하자. (이 경우, 꼭짓점들이 서로 구별되므로, 이는 나무 그래프의 동형류의 수와 다르다.) '''케일리 공식'''({{llang|en|Cayley’s formula}})에 따르면, 이는 다음과 같다.<ref>{{저널 인용|제목=케일리 공식의 네 가지 증명|저널=한국수학사학회지|권=21|호=3|날짜=2008-08|쪽=127–142|저자1=서승현|저자2=권석일|저자3=홍진곤|url=http://society.kisti.re.kr/sv/SV_svpsbs03V.do?method=download&cn1=JAKO200800557082835|언어=ko|access-date=2017-07-10|archive-date=2021-03-08|archive-url=https://web.archive.org/web/20210308061732/http://society.kisti.re.kr/sv/SV_svpsbs03V.do?method=download&cn1=JAKO200800557082835|url-status=}}</ref>
:<math>T_n=n^{n-2}</math>
<div class="mw-collapsible mw-collapsed toccolours">
'''증명''':
<div class="mw-collapsible-content">
꼭짓점 집합 <math>V</math>에 임의의 [[정렬 순서]]를 주자. 그렇다면, <math>V</math> 위의 임의의 나무 그래프는 프뤼퍼 열에 유일하게 대응하며, 반대로 모든 프뤼퍼 열은 나무 그래프에 유일하게 대응된다. 프뤼퍼 열의 수는
:<math>n^{n-2}</math>
이다.
</div></div>
크기 <math>n</math>의 [[유한 집합]] 위의 숲 그래프의 수는 다음과 같다. (<math>n=0,1,2,\dotsc</math>)
:1, 1, 2, 7, 38, 291, 2932, 36961, 561948, 10026505, 205608536, 4767440679, 123373203208, 3525630110107, 110284283006640, 3748357699560961, 137557910094840848, 5421179050350334929, 228359487335194570528, 10239206473040881277575, 486909744862576654283616, … {{OEIS|A1858}}
이 자연수열을
:<math>c_i</math>
라고 표기하면, 그 [[생성 함수 (수학)|생성 함수]]는
:<math>\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</math>
이다.
<div class="mw-collapsible mw-collapsed toccolours">
'''증명''':
<div class="mw-collapsible-content">
크기 <math>N</math>의 집합의 [[집합의 분할|분할]]에서, 크기 <math>n</math>의 성분의 수가 <math>k_n</math>이라고 하자. 즉,
:<math>\sum_{n=1}^\infty nk_n=N</math>
이다.

이 경우, 주어진 분할을 [[연결 성분]] 분할로 갖는 숲 그래프의 수는
:<math>\prod_{n=1}^\infty (T_n)^{k_n} </math>
이다.

크기 <math>N</math>의 집합의 경우, 이러한 [[집합의 분할|분할]]의 수는
:<math>\binom{N!}{\prod_{n=1}^\infty (n!)^{k_n} k_n!}</math>
이다.

따라서, [[생성 함수 (수학)|생성 함수]] <math>f(x)</math>는 다음과 같은 유한 [[중복집합]]에 대한 합으로 나타내어진다.
:<math>
\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_nx_n}\over{n!}}\right)^{k_n} {{1}\over{k_n!}} \\
& =\prod_{n=1}^\infty\sum_{k_n=0}^\infty\left({{T_nx_n}\over{n!}}\right)^{k_n} {{1}\over{k_n!}} \\
& =\prod_{n=1}^\infty\exp \left({{T_nx^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}
</math>
여기서 <math>M</math>는 유한 [[중복집합]]들, 즉 함수
:<math>k\colon\mathbb Z^+\to\mathbb N</math>
:<math>k\colon n\mapsto k_n</math>
가운데
:<math>\sum_{n=1}^\infty nk_n<\infty</math>
인 것들의 족이며,
:<math>|k| = \sum_{n=1}^\infty nk_n</math>
이고,
:<math>T_n=n^{n-2}</math>이다.
</div></div>

== 예 ==
정의에 따라, 모든 [[무변 그래프]]는 숲 그래프이며, 특히 한원소 그래프 <math>K_1</math>은 나무 그래프이다.

임의의 양의 정수 <math>n</math>에 대하여, [[경로 그래프]] <math>P_n</math>은 나무 그래프이다. 또한, 양쪽 무한 [[경로 그래프]]
:<math>P_\infty</math>
및 한쪽 무한 [[경로 그래프]]
:<math>P_\infty^+</math>
역시 둘 다 나무 그래프이다.

=== 프뤼퍼 열의 예 ===
다음과 같은 유한 나무 그래프 <math>T</math>를 생각하자.
:[[파일:Tree graph.svg]]
이 경우,
# 잎 꼭짓점들은 <math>\{1,2,3,6\}</math>이며, 이 가운데 최솟값은 1이다. 이는 꼭짓점 4에 연결되어 있다. 즉, <math>x_0=1</math>이며 <math>y_0=4</math>이다. 이제, 꼭짓점 1을 제거하자.
# <math>T\setminus\{1\}</math>에서, 잎 꼭짓점들은 <math>\{2,3,6\}</math>이며, 이 가운데 최솟값은 2이다. 이는 꼭짓점 4에 연결되어 있다. 즉, <math>x_1=2</math>이며 <math>y_1=4</math>이다. 이제, 꼭짓점 2를 제거하자.
# <math>T\setminus\{1,2\}</math>에서, 잎 꼭짓점들은 <math>\{3,6\}</math>이며, 이 가운데 최솟값은 3이다. 이는 꼭짓점 4에 연결되어 있다. 즉, <math>x_2=3</math>이며 <math>y_2=4</math>이다. 이제, 꼭짓점 3을 제거하자.
# <math>T\setminus\{1,2,3\}</math>에서, 잎 꼭짓점들은 <math>\{4,6\}</math>이며, 이 가운데 최솟값은 4이다. 이는 꼭짓점 5에 연결되어 있다. 즉, <math>x_3=4</math>이며 <math>y_2=5</math>이다. 이제, 꼭짓점 4를 제거하자.
# <math>T\setminus\{1,2,3,4\}</math>에서, 잎 꼭짓점들은 <math>\{5,6\}</math>이며, 이 가운데 최솟값은 5이다. 즉, <math>x_4=5</math>이다. 이는 꼭짓점 6에 연결되어 있으나, 이 역시 잎 꼭짓점이므로, 프뤼퍼 열은 끝난다.

즉,
:<math>(y_0,\dotsc,y_4) = (4,4,4,5)</math>
이다.

== 역사 ==
케일리 공식은 1860년에 카를 빌헬름 보르하르트({{llang|de|Carl Wilhelm Borchardt}}, 1817~1880)가 최초로 증명하였다.<ref>{{저널 인용|성=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|url=https://archive.org/stream/abhandlungenderk1860deut#page/n246/|언어=de}}</ref> 이후 1889년에 [[아서 케일리]]가 같은 정리의 새 증명을 발표하였다.<ref>{{저널 인용|성=Cayley|이름=Arthur|저자링크=아서 케일리|날짜=1889|제목=A theorem on trees|저널=The Quarterly Journal of Pure and Applied Mathematics|권=23|쪽=376–378|jfm=21.0687.01|언어=en}}</ref> 케일리는 보르하르트의 논문을 인용하였지만, 이 공식은 더 유명한 케일리의 이름을 따 불리게 되었다.

에른스트 파울 하인츠 프뤼퍼({{llang|de|Ernst Paul Heinz Prüfer}}, 1896~1934)는 1918년에 프뤼퍼 열을 도입하였으며, 이를 사용하여 이에 대한 다른 증명을 제시하였다.<ref>{{저널 인용|성=Prüfer|이름= Heinz|날짜=1918|제목=Neuer Beweis eines Satzes über Permutationen|저널=Archiv der Mathematik und Physik|권=27|쪽=742–744|jfm=46.0106.04|언어=en}}</ref>

== 같이 보기 ==
* [[결정 트리]]
* [[트리 구조 (모델)]]
* [[트리 구조]]

== 각주 ==
{{각주}}

== 외부 링크 ==
* {{eom|title=Tree}}
* {{매스월드|id=Tree|title=Tree}}
* {{매스월드|id=Forest|title=Forest}}
* {{매스월드|id=PrueferCode|title=Prüfer code}}

{{전거 통제}}

[[분류:그래프]]
[[분류:이분 그래프]]