요즘 트리(tree, connected acyclic graph)에 관한 문제를 고민하고 있는데, 오늘 그에 관한 간단하지만 흥미로운 성질들을 알게 되어 정리합니다. 너무 간단해서 학부 수준의 조합론에서 분명 다루었을 내용으로 보입니다만, 저는 전공이 컴퓨터과학이니까요. 채워야할 것들이 아직도 너무 많은 것 같습니다.
차수열(degree sequence)에 관한 필요충분조건
첫 번째는 tree의 degree sequence에 관한 내용입니다. 먼저 degree sequence가 무엇이냐면, 그냥 정점의 차수를 내림차순으로 나열한 것입니다.
Degree sequence는 그래프의 모양을 가늠할 수 있는 좋은 도구입니다. 다만, 하나의 degree sequence가 유일한 그래프를 결정하는 것은 아닌데요. 다음의 예시를 보시기 바랍니다.
일단 이 글의 주제가 tree이므로 그에 집중해 보도록 하죠. 과연 tree의 degree sequence는 어떤 성질을 갖고 있을까요? 한 가지 쉽게 볼 수 있는 사실은 정점의 개수를 \(n\)이라고 할 때 tree 위의 모든 정점의 degree의 합을 구하면 정확히 \( 2n - 2 \)가 된다는 것입니다. 이는 유명한 악수 정리(handshaking lemma)를 통해 얻을 수 있습니다.
정리 1. 악수 정리(Handshaking lemma)
어떤 그래프 \(G = (V, E)\)에 대해 임의의 정점 \(v\)의 차수를 \( \mathsf{deg}_G(v)\)라고 할 때, \[ \sum_{v \in V} \mathsf{deg}_G(v) = 2|E| \]를 만족한다.
어떤 tree든 정점의 개수가 \(n\)이면 간선의 개수는 정확히 \(n - 1\)이므로 우리가 원하는 사실을 쉽게 보일 수 있습니다.
그렇다면 반대 방향은 어떨까요? 놀랍게도 그러한 수열이 주어지면 그것을 degree sequence로 갖는 tree를 하나 찾을 수 있습니다. 즉, 필요충분조건의 관계를 만족하게 됩니다.
정리 2. Tree와 degree sequence의 관계
\(2\)보다 크거나 같은 어떤 양의 정수 \(n\)에 대해, 양의 정수로만 이루어진 내림차순 수열 \(d_1, \cdots, d_n\)이 \[ \sum_{i = 1}^n d_i = 2n - 2 \]를 만족할 때, \( \{d_1, \cdots, d_n\} \)을 degree sequence로 하는 tree가 존재한다.
[증명] 수학적 귀납법을 사용합니다. 만약 \(n = 2\)인 경우, \(d_1 + d_2 = 2\)를 만족하는 \(d_1, d_2 > 0\)은 \(d_1 = d_2 = 1\)밖에 없습니다. 정점 두 개와 둘을 잇는 간선 하나로 만들어지는 tree의 degree sequence가 곧 \( \{1, 1 \} \)이므로 정리가 성립합니다.
이제 \(n = k \geq 2\)인 경우 정리가 만족한다고 가정하겠습니다. 만약 \[\sum_{i = 1}^{k + 1} d_i = 2k \tag{1}\]를 만족하는 양의 정수로만 이루어진 내림차순 수열 \( d_1, \cdots, d_{k + 1} \)을 degree sequence로 갖는 tree \(T\)를 만들 수 있다면 증명이 완료됩니다.
식 1을 잘 관찰하면 몇 가지 흥미로운 사실을 알 수 있습니다. 첫 번째는 \(d_1 \geq 2 \)라는 점입니다. 만약 그렇지 않다면 수열의 모든 값이 \(1\)이라는 뜻이 됩니다. 이때 이를 모두 더해 보아도 \(k \geq 2\)에 대해 \(\sum_{i = 1}^{k + 1}d_i = k + 1 < 2k\)이 되어 모순이 발생하게 되죠. 반대로 \( d_{k + 1} = 1 \) 이라는 사실을 알 수 있습니다. 위와 비슷하게 보일 수 있는데, 그렇지 않다면 수열의 모든 값이 \(2\)보다 크거나 같게 되고, 이를 모두 더하면 \( \sum_{i = 1}^{k + 1}d_i \geq 2k + 2 > 2k \)가 되어 모순이 발생합니다.
길이가 \(k\)인 다음의 수열 \(d^\prime\)을 생각해 보겠습니다. \[ d^\prime_i = \left\{ \begin{array}{ll} d_1 - 1, & \text{if } i = 1,\\ d_i, & \text{if } i = 2, \cdots, k. \end{array} \right. \] 이 수열의 합은 식 1에서 정확히 \(2\)의 값이 차감되었으니 \( \sum_{i = 1}^k d_i^\prime = 2k - 2 \)를 만족합니다. 또한, \(d_1 - 1 \geq 1\)이므로 \(d^\prime\)은 양의 정수로만 이루어진 수열이 된다는 것도 알 수 있습니다. 따라서 가정에 의해 이 수열(을 내림차순으로 정렬한 수열)을 degree sequence로 하는 tree가 존재하게 됩니다. 그 tree를 \(T^\prime\)이라고 하겠습니다.
눈치를 채셨겠지만 \(T^\prime\)에서 \(T\)를 만들 수 있습니다. 먼저 \(T^\prime\)에 새로운 정점을 추가한 후 이 정점과 거기서 \(d_1 - 1\)에 해당하는 정점을 잇는 간선을 만들어 주면 됩니다. 이렇게 만든 tree가 정확히 우리가 원하는 tree라는 것은 쉽게 알 수 있습니다. ■
리프(Leaf)의 개수
어떤 tree에서 leaf는 차수가 1인 정점을 의미합니다. 즉 tree의 가장 꼬랑지에 매달린 정점들이죠. 이번에 알아 볼 것은 이들의 개수에 관한 것입니다.
정리 3. Leaf의 개수
어떤 tree가 주어졌을 때, 거기서 가장 큰 차수의 값은 \(k\), 차수가 \(i \leq k\)인 정점의 개수를 \(n_i\)라고 하자. 그러면 \[ n_1 = n_3 + 2 n_4 + \cdots + (k - 2) n_k + 2 \]를 만족한다.
[증명] 해당 tree의 정점의 개수를 \(n\)이라고 하겠습니다. 악수 정리에 의해 \[ \sum_{i = 1}^k i n_i = 2n - 2 \]를 만족하게 됩니다. 이때 \(n = \sum_{i = 1}^k n_i\)이므로, 이를 위 식에 대입하면 \[ \sum_{i = 1}^k i n_i = \sum_{i = 1}^k 2n_i - 2 \]가 됩니다. 이를 정리하면 정리의 식을 얻을 수 있습니다. ■
마치며
이번에는 tree가 만족하는 간단한 성질들에 대해 알아 보았습니다. 너무 기초적인 내용들이라 분류도 그냥 연습 노트에 해버렸습니다. 서두에도 언급했듯이 요즘 tree와 관련된 문제를 고민하고 있는데, 이래저래 구글링을 하다가 예전에 구독한 유튜브 채널에서 tree에 관련된 재밌어 보이는 주제로 비디오를 찍어놓은게 있어서 그것을 보고 정리하였습니다. 참조를 확인해 주세요. 해당 유튜브 채널은 조합론에 관해서 꽤 다양한 주제를 다루고 있는데, 개인적으로 선생님이 설명을 잘하신다고 생각합니다.
고맙습니다.
참조
[1] 첫 번째 증명 : https://youtu.be/cCG4_mj9TgM
[2] 두 번째 증명 : https://youtu.be/SzPyRwZJLso
[3] Degree sequence의 유일성 반례 : https://en.wikipedia.org/wiki/Degree_(graph_theory)
'수학적 도구 > Graph theory' 카테고리의 다른 글
| 하벨-하키미 알고리즘 (Havel-Hakimi Algorithm) (0) | 2022.06.17 |
|---|---|
| 거리의 트리 실현 가능성 (Tree Realizability of Distance) (2) | 2022.05.15 |
