그래프 이론에서 나무 그래프(영어: tree graph 트리 그래프[*]) 또는 단순히 나무는 순환을 갖지 않는 연결 그래프이다.
그래프
에 대하여 다음 조건들이 서로 동치이며, 이 조건을 만족시키는 그래프
를 숲 그래프(영어: forest graph 포리스트 그래프[*])이라고 한다.
는 (길이 3 이상의) 순환을 갖지 않는다.
- 임의의 두 꼭짓점
에 대하여,
과
사이의 경로의 수는 1 이하이다.
는 완전 그래프
를 마이너로 갖지 않는다.
는 단일 연결 공간이다. (즉, 임의의 밑점
에 대하여, 1차 세포 호몰로지
가 자명군이다. 그러나 연결 공간이 아닐 수 있다.)
그래프
에 대하여 다음 조건들이 서로 동치이며, 이 조건을 만족시키는 그래프
를 나무 그래프라고 한다.
는 숲 그래프이며, 연결 그래프이다 (즉, 정확히 1개의 연결 성분을 갖는다).
- 임의의 두 꼭짓점
에 대하여,
과
사이의 경로가 정확히 하나 존재한다.
는 (1차원 세포 복합체로서) 연결 단일 연결 공간이다. (특히, 공집합이 아니다.)
- 하나 이상의 꼭짓점을 가지며, 임의의 변
을 지운 그래프
는 연결 그래프가 아니다.
나무 그래프
의 잎 꼭짓점(영어: leaf vertex 리프 버텍스[*])은 차수가 1인 꼭짓점이며, 내부 꼭짓점(영어: internal vertex)은 차수가 2 이상인 꼭짓점이다.
숲 그래프
에 대하여 다음이 성립한다.
![{\displaystyle |\operatorname {V} (T)|=|\operatorname {E} (T)|+|\operatorname {Conn} (T)|}](https://amansaja.com/index.php?q=Mfv0Kfa6bO93MqTXLqrCMqiSL3dZb2hQMu9Onpz0p3oPb21BngBFb21FJgGRKArSngrOb3z2nO8QzNC3atKPztC5agaQyjKPaNoPzjePageNyjFEzja2zqeQoAs1zgoQ)
여기서
는
의 꼭짓점의 수이다.
는
의 변의 수이다.
는
의 연결 성분의 수이다.
특히, 나무 그래프의 경우 하나의 연결 성분을 가지므로,
이다.
모든 숲 그래프는 이분 그래프이자 평면 그래프이다.
개의 꼭짓점을 갖는 나무 그래프의 동형류의 수는 다음과 같다 (
).
- 1, 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159, … (OEIS의 수열 A000055)
개의 꼭짓점을 갖는 숲 그래프의 동형류의 수는 다음과 같다 (
).
- 1, 1, 2, 3, 6, 10, 20, 37, 76, 153, 329, 710, 1601, 3658, … (OEIS의 수열 A005195)
유한 나무 그래프
의 꼭짓점 집합
![{\displaystyle \operatorname {V} (T)}](https://amansaja.com/index.php?q=Mfv0Kfa6bO93MqTXLqrCMqiSL3dZb2hQMu9Onpz0p3oPb21BngBFb21FJgGRKArSngrOb3z2nO9Daqe3yqzEytaPz2w2zAs3oqnBzNJCoqdEnAaPnDlAnAhBzqdCoqdF)
에 임의의 정렬 순서를 주고, 그 순서형을
이라고 하자.
에 대하여, 꼭짓점 열
![{\displaystyle x_{0},x_{1},\dotsc }](https://amansaja.com/index.php?q=Mfv0Kfa6bO93MqTXLqrCMqiSL3dZb2hQMu9Onpz0p3oPb21BngBFb21FJgGRKArSngrOb3z2nO8Pnja1yqoNntK5atzBztvEztlAngo3zDJDzqhCnDrCzge3a2o1yqs3)
을 다음과 같이 재귀적으로 정의하자.
![{\displaystyle x_{i}=\min\{v\in \operatorname {V} (T)\setminus \{x_{j}\}_{j<i}\colon \deg _{T\setminus \{x_{j}\}_{j<i}}v=1\}}](https://amansaja.com/index.php?q=Mfv0Kfa6bO93MqTXLqrCMqiSL3dZb2hQMu9Onpz0p3oPb21BngBFb21FJgGRKArSngrOb3z2nO84nDs0yjiNaNC5yjoQzNBEzNCNyji1o2vCaqeNztoOngrDyjo2zgiQ)
즉, 다음과 같다.
- 임의의 순서수
에 대하여,
은
의 잎 꼭짓점 가운데, 정렬 순서에 대하여 최소 원소이다.
유한 나무 그래프의 경우, 이 열은
의 모든 꼭짓점을 한 번씩 포함한다. 즉,
의 꼭짓점 집합
위의 또다른 정렬 순서를 정의한다. (반면, 무한 나무 그래프의 경우 이는 그렇지 못할 수 있다.)
또한, 다음과 같은 꼭짓점 열
![{\displaystyle y_{0},y_{1},\dotsc }](https://amansaja.com/index.php?q=Mfv0Kfa6bO93MqTXLqrCMqiSL3dZb2hQMu9Onpz0p3oPb21BngBFb21FJgGRKArSngrOb3z2nO8OzjhDz2wOntC1aqnBzqzAaAnEzgiPajiQygo2zghBaAhEzjvAzjC5)
을
로부터 정의할 수 있다.
![{\displaystyle (x_{i},y_{i})\in \operatorname {E} (T\setminus \{x_{j}\}_{j<i})}](https://amansaja.com/index.php?q=Mfv0Kfa6bO93MqTXLqrCMqiSL3dZb2hQMu9Onpz0p3oPb21BngBFb21FJgGRKArSngrOb3z2nO80ngiNaNhDzgiPzNGOyqoQntm5zjaNaNo4ytzDoNi2zjrBoDaNyjhD)
즉,
는
에서
와 인접한 유일한 내부 꼭짓점이다. (만약 이러한 꼭짓점이 존재하지 않는다면, 이 열은 끝나게 된다.)
유한 나무 그래프의 경우, 꼭짓점 열
의 길이는
인데, 이는 맨 “마지막”의 경우 꼭짓점이 하나 밖에 남지 않기 때문이다.
를
의 프뤼퍼 열(Prüfer列, 영어: Prüfer sequence)이라고 한다.
또한, 프뤼퍼 열에 대하여 다음이 성립한다.
유한 나무 그래프 |
프뤼퍼 열
|
꼭짓점의 수 |
프뤼퍼 열의 길이 + 2
|
변의 수 |
프뤼퍼 열의 길이 + 1
|
잎 꼭짓점 |
프뤼퍼 열에 등장하지 않는 꼭짓점
|
내부 꼭짓점 |
프뤼퍼 열에 등장하는 꼭짓점
|
꼭짓점의 차수 |
프뤼퍼 열에 등장하는 수 + 1
|
모든 유한 나무 그래프는 그 프뤼퍼 열로부터 재구성될 수 있다. 이 알고리즘은 대략 다음과 같다.
- 우선, 각 꼭짓점
에 대하여 양의 정수 값의 변수
를,
가 프뤼퍼 열에 등장하는 수 + 1로 놓는다.
- 프뤼퍼 열의 첫째 꼭짓점
에 대하여,
인 최소의 꼭짓점을
라고 하면,
- 변
를 그래프에 추가하며,
과
를 각각 1만큼 감소시킨다.
- 위 단계를 프뤼퍼 열의 둘째, 셋째 등등 꼭짓점에 대하여 반복한다.
- 이 과정이 끝나면,
인 꼭짓점이 두 개 남는다. 이들 사이에 변을 추가한다.
- 알고리즘 종료.
(반면, 무한 나무 그래프의 경우 이는 일반적으로 불가능하다. 예를 들어, 양쪽 무한 경로 그래프는 나무 그래프이지만, 잎 꼭짓점을 갖지 않아, 프뤼퍼 열이 자명하다.)
임의의 크기
의 유한 집합
가 주어졌다고 하자. 그렇다면,
를 꼭짓점으로 하는 나무 그래프의 수를
이라고 하자. (이 경우, 꼭짓점들이 서로 구별되므로, 이는 나무 그래프의 동형류의 수와 다르다.) 케일리 공식(영어: Cayley’s formula)에 따르면, 이는 다음과 같다.[1]
![{\displaystyle T_{n}=n^{n-2}}](https://amansaja.com/index.php?q=Mfv0Kfa6bO93MqTXLqrCMqiSL3dZb2hQMu9Onpz0p3oPb21BngBFb21FJgGRKArSngrOb3z2nO80ygvAzNrFzta5z2dFoNK1oAdAoAo1zDm1aNoNzgs1zts3ztiQzgw5)
증명:
꼭짓점 집합
에 임의의 정렬 순서를 주자. 그렇다면,
위의 임의의 나무 그래프는 프뤼퍼 열에 유일하게 대응하며, 반대로 모든 프뤼퍼 열은 나무 그래프에 유일하게 대응된다. 프뤼퍼 열의 수는
![{\displaystyle n^{n-2}}](https://amansaja.com/index.php?q=Mfv0Kfa6bO93MqTXLqrCMqiSL3dZb2hQMu9Onpz0p3oPb21BngBFb21FJgGRKArSngrOb3z2nO82zqi2ntK4zDo1aDzFatoNoNK3a2a1yqvAaqnDzNK5a2rAzta0oNs2)
이다.
크기
의 유한 집합 위의 숲 그래프의 수는 다음과 같다. (
)
- 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}}](https://amansaja.com/index.php?q=Mfv0Kfa6bO93MqTXLqrCMqiSL3dZb2hQMu9Onpz0p3oPb21BngBFb21FJgGRKArSngrOb3z2nO8QaqhDoDK5ztzEotsOoNdFotw0aDo0oDrCago4nAwOaDzFoti3ygiO)
라고 표기하면, 그 생성 함수는
![{\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 }](https://amansaja.com/index.php?q=Mfv0Kfa6bO93MqTXLqrCMqiSL3dZb2hQMu9Onpz0p3oPb21BngBFb21FJgGRKArSngrOb3z2nO9BnjmQntG5athCztmPajKPztrDaNrEnghFotCQoNiOnjK2z2o2zNdE)
이다.
증명:
크기
의 집합의 분할에서, 크기
의 성분의 수가
이라고 하자. 즉,
![{\displaystyle \sum _{n=1}^{\infty }nk_{n}=N}](https://amansaja.com/index.php?q=Mfv0Kfa6bO93MqTXLqrCMqiSL3dZb2hQMu9Onpz0p3oPb21BngBFb21FJgGRKArSngrOb3z2nO9DnqwPzqeOaqe1zgs4yjrCygiOyqzFaDG1a2aQnDs2oNJDoNeOygo1)
이다.
이 경우, 주어진 분할을 연결 성분 분할로 갖는 숲 그래프의 수는
![{\displaystyle \prod _{n=1}^{\infty }(T_{n})^{k_{n}}}](https://amansaja.com/index.php?q=Mfv0Kfa6bO93MqTXLqrCMqiSL3dZb2hQMu9Onpz0p3oPb21BngBFb21FJgGRKArSngrOb3z2nO82o2iPzqnBythEnAs4aNJDnjwOa2w2a2hCzgzDzjJBzgwPzNs4aDoP)
이다.
크기
의 집합의 경우, 이러한 분할의 수는
![{\displaystyle {\binom {N!}{\prod _{n=1}^{\infty }(n!)^{k_{n}}k_{n}!}}}](https://amansaja.com/index.php?q=Mfv0Kfa6bO93MqTXLqrCMqiSL3dZb2hQMu9Onpz0p3oPb21BngBFb21FJgGRKArSngrOb3z2nO8NzjJBnga5zga2otaNotiNnDi0zNaQatoQaDa5aNvAz2a3nqa5aArE)
이다.
따라서, 생성 함수
는 다음과 같은 유한 중복집합에 대한 합으로 나타내어진다.
![{\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}}}](https://amansaja.com/index.php?q=Mfv0Kfa6bO93MqTXLqrCMqiSL3dZb2hQMu9Onpz0p3oPb21BngBFb21FJgGRKArSngrOb3z2nO82a2i4ytoPzAdCoqvEaDCNzDhEzjC3oNzEygwQnDJFaNC3yja4aNzE)
여기서
는 유한 중복집합들, 즉 함수
![{\displaystyle k\colon \mathbb {Z} ^{+}\to \mathbb {N} }](https://amansaja.com/index.php?q=Mfv0Kfa6bO93MqTXLqrCMqiSL3dZb2hQMu9Onpz0p3oPb21BngBFb21FJgGRKArSngrOb3z2nO9CzjFByjhAyjs0ztdEzDGQoNC5z2hAatrDoAzFoDo2aqaNoqo1aDa3)
![{\displaystyle k\colon n\mapsto k_{n}}](https://amansaja.com/index.php?q=Mfv0Kfa6bO93MqTXLqrCMqiSL3dZb2hQMu9Onpz0p3oPb21BngBFb21FJgGRKArSngrOb3z2nO80zAo1zqe5oNJByji2nDCQnjFBnAiPaAoQyjCNaDm2atm4o2w3ngi3)
가운데
![{\displaystyle \sum _{n=1}^{\infty }nk_{n}<\infty }](https://amansaja.com/index.php?q=Mfv0Kfa6bO93MqTXLqrCMqiSL3dZb2hQMu9Onpz0p3oPb21BngBFb21FJgGRKArSngrOb3z2nO9FaqeOaNrEoNdAoDi5nAw2zjFAo2iNaqe0ztJCyqzDntJDnAdCathB)
인 것들의 족이며,
![{\displaystyle |k|=\sum _{n=1}^{\infty }nk_{n}}](https://amansaja.com/index.php?q=Mfv0Kfa6bO93MqTXLqrCMqiSL3dZb2hQMu9Onpz0p3oPb21BngBFb21FJgGRKArSngrOb3z2nO84otdFytnAaAaQaNoOa2a4ngvFntiNatK4zte1zDi3otvFnDmNaga0)
이고,
이다.
정의에 따라, 모든 무변 그래프는 숲 그래프이며, 특히 한원소 그래프
은 나무 그래프이다.
임의의 양의 정수
에 대하여, 경로 그래프
은 나무 그래프이다. 또한, 양쪽 무한 경로 그래프
![{\displaystyle P_{\infty }}](https://amansaja.com/index.php?q=Mfv0Kfa6bO93MqTXLqrCMqiSL3dZb2hQMu9Onpz0p3oPb21BngBFb21FJgGRKArSngrOb3z2nO9EoArFnjdEzNGPoAwQoDvEyji3ots0ztC0oAaQaqzBnqeQoDrEaDC0)
및 한쪽 무한 경로 그래프
![{\displaystyle P_{\infty }^{+}}](https://amansaja.com/index.php?q=Mfv0Kfa6bO93MqTXLqrCMqiSL3dZb2hQMu9Onpz0p3oPb21BngBFb21FJgGRKArSngrOb3z2nO85aqzFoNC1aNGQo2s5nDaPo2aOzNFFoqvDzDm2ztwNzthEyqe1ytJF)
역시 둘 다 나무 그래프이다.
다음과 같은 유한 나무 그래프
를 생각하자.
![](https://amansaja.com/index.php?q=Mfv0Kfa6bO91KgPRoqwSJ2BVMq1BngBFbA9OnO93MqTXKgrCMqiRo29TLq9SKO90MfrToE8ObNe0b1vOnqrHn3dFKgGSK3nZbNi2aZl4brvOnqrHn3dFKgGSK3nZbZlSnQ%3D%3D)
이 경우,
- 잎 꼭짓점들은
이며, 이 가운데 최솟값은 1이다. 이는 꼭짓점 4에 연결되어 있다. 즉,
이며
이다. 이제, 꼭짓점 1을 제거하자.
에서, 잎 꼭짓점들은
이며, 이 가운데 최솟값은 2이다. 이는 꼭짓점 4에 연결되어 있다. 즉,
이며
이다. 이제, 꼭짓점 2를 제거하자.
에서, 잎 꼭짓점들은
이며, 이 가운데 최솟값은 3이다. 이는 꼭짓점 4에 연결되어 있다. 즉,
이며
이다. 이제, 꼭짓점 3을 제거하자.
에서, 잎 꼭짓점들은
이며, 이 가운데 최솟값은 4이다. 이는 꼭짓점 5에 연결되어 있다. 즉,
이며
이다. 이제, 꼭짓점 4를 제거하자.
에서, 잎 꼭짓점들은
이며, 이 가운데 최솟값은 5이다. 즉,
이다. 이는 꼭짓점 6에 연결되어 있으나, 이 역시 잎 꼭짓점이므로, 프뤼퍼 열은 끝난다.
즉,
![{\displaystyle (y_{0},\dotsc ,y_{4})=(4,4,4,5)}](https://amansaja.com/index.php?q=Mfv0Kfa6bO93MqTXLqrCMqiSL3dZb2hQMu9Onpz0p3oPb21BngBFb21FJgGRKArSngrOb3z2nO9Eyqw4nAi2aqrEyjiPztFEzNCPzDFBo2vBoNCNoAw2nAi4zjaQyge0)
이다.
케일리 공식은 1860년에 카를 빌헬름 보르하르트(독일어: Carl Wilhelm Borchardt, 1817~1880)가 최초로 증명하였다.[2] 이후 1889년에 아서 케일리가 같은 정리의 새 증명을 발표하였다.[3] 케일리는 보르하르트의 논문을 인용하였지만, 이 공식은 더 유명한 케일리의 이름을 따 불리게 되었다.
에른스트 파울 하인츠 프뤼퍼(독일어: Ernst Paul Heinz Prüfer, 1896~1934)는 1918년에 프뤼퍼 열을 도입하였으며, 이를 사용하여 이에 대한 다른 증명을 제시하였다.[4]