12강. 트리

회로가 없는 연결 그래프를 트리라 합니다. 폴더 구조, 가계도, 토너먼트 대진표, 결정 과정이 모두 트리입니다. 이 강에서는 트리의 성질, 이진 트리, 그리고 가장 싸게 모든 점을 잇는 최소 신장 트리를 찾는 알고리즘을 다룹니다.

트리는 회로가 없는 연결 그래프입니다. 가장 단순한 연결 구조라서 파일 시스템, 가계도, 결정 과정, 자료구조, 통신망 설계 등 곳곳에 나옵니다.

12.1 트리의 정의와 동치 조건

정의 12.1 (트리). 회로가 없는 연결 그래프를 트리(tree)라 합니다. 회로가 없는(연결되지 않아도 되는) 그래프를 숲(forest)이라 합니다. 트리에서 차수가 1인 꼭짓점을 잎(leaf)이라 합니다.

정리 12.2. 꼭짓점이 2개 이상인 트리에는 잎이 적어도 2개 있습니다.

증명. 트리에서 가장 긴 경로 $v_0, \dots, v_k$를 잡습니다. $v_0$에 경로 밖의 이웃이 있으면 경로를 늘일 수 있고, 경로 안의 다른 이웃 $v_i$($i \ge 2$)가 있으면 회로가 생기므로, $v_0$의 이웃은 $v_1$뿐입니다. $v_k$도 마찬가지입니다. □

정리 12.3. 꼭짓점이 $n$개인 그래프 $G$에 대해 다음은 모두 동치입니다.

1. $G$는 트리입니다(연결, 회로 없음).
2. 임의의 두 꼭짓점 사이에 경로가 정확히 하나 있습니다.
3. $G$는 연결이고 변이 $n - 1$개입니다.
4. $G$는 회로가 없고 변이 $n - 1$개입니다.
5. $G$는 연결이지만, 어떤 변을 지워도 연결이 끊깁니다.

증명 (1 ⇒ 3). $n$에 대한 귀납법. 잎 하나와 그 변을 지우면 꼭짓점 $n - 1$개인 트리가 남고, 귀납 가정으로 변이 $n - 2$개입니다. 지운 변을 더하면 $n - 1$개입니다. □

나머지도 비슷하게 보입니다. 핵심은 “트리는 연결을 유지하는 가장 적은 변($n-1$개)이면서 회로 없이 넣을 수 있는 가장 많은 변”이라는 것입니다.

따름정리 12.4. 성분이 $c$개인 숲은 변이 $n - c$개입니다.

12.2 뿌리 트리와 이진 트리

정의 12.5. 꼭짓점 하나를 뿌리로 정한 트리를 뿌리 트리(rooted tree)라 합니다. 뿌리에서 $v$로 가는 경로에서 $v$ 바로 앞의 꼭짓점이 $v$의 부모, $v$가 부모인 꼭짓점이 $v$의 자식입니다. 뿌리에서 가장 먼 꼭짓점까지의 거리를 높이라 합니다.

정의 12.6. 모든 꼭짓점의 자식이 2개 이하인 뿌리 트리를 이진 트리(binary tree), 잎이 아닌 모든 꼭짓점의 자식이 정확히 2개인 것을 완전 이진 트리(full)라 합니다.

정리 12.7. 높이 $h$인 이진 트리의 잎은 $2^h$개 이하입니다. 그러므로 잎이 $\ell$개이면 높이는 $\lceil \log_2 \ell \rceil$ 이상입니다.

증명. 깊이 $d$의 꼭짓점은 $2^d$개 이하입니다(깊이마다 많아야 두 배). 잎은 깊이 $h$ 이하에 있고, 깊이 $h$의 꼭짓점 하나가 차지할 수 있는 잎 수를 세면 $2^h$개 이하입니다. □

이 정리는 “비교로 정렬하는 알고리즘은 최악에 약 $\log_2 n!$번 비교해야 한다”는 하한의 근거입니다. 가능한 순서 $n!$가지가 결정 트리의 잎이기 때문입니다.

정리 12.8. 내부 꼭짓점이 $i$개인 완전 이진 트리는 잎이 $i + 1$개, 꼭짓점이 $2i + 1$개입니다.

증명. 뿌리를 뺀 모든 꼭짓점은 어떤 내부 꼭짓점의 자식이고, 내부 꼭짓점마다 자식이 2개이므로 꼭짓점은 $2i + 1$개입니다. 잎은 $2i + 1 - i = i + 1$개입니다. □

예를 들어 $n$팀의 토너먼트(완전 이진 트리, 잎이 팀)는 경기(내부 꼭짓점)가 $n - 1$번입니다.

12.3 신장 트리

정의 12.9. 연결 그래프 $G$의 모든 꼭짓점을 포함하는 부분그래프 가운데 트리인 것을 신장 트리(spanning tree)라 합니다.

정리 12.10. 모든 연결 그래프에는 신장 트리가 있습니다.

증명. 회로가 있으면 그 위의 변 하나를 지워도 연결이 유지됩니다(회로의 나머지가 대신 이어 줍니다). 회로가 없어질 때까지 되풀이하면 신장 트리가 남습니다. □

12.4 최소 신장 트리

변마다 비용(가중치)이 있을 때, 모든 꼭짓점을 잇는 비용이 가장 작은 신장 트리를 최소 신장 트리(minimum spanning tree)라 합니다. 마을들을 최소 비용의 도로망으로 잇는 문제입니다.

정리 12.11 (크루스칼 알고리즘). 변을 비용이 작은 것부터 보며, 이미 고른 변들과 회로를 만들지 않으면 고릅니다. $n - 1$개를 고르면 멈춥니다. 이렇게 얻은 트리는 최소 신장 트리입니다.

증명 개요. 매 단계에서 고른 변들이 어떤 최소 신장 트리 $T$에 들어 있다고 합시다(처음에는 빈 집합이므로 참). 다음에 고른 변 $e$가 $T$에 없으면, $T$에 $e$를 더하면 회로가 생기고, 그 회로에는 아직 고르지 않은 변 $e'$이 있으며 $e'$의 비용은 $e$ 이상입니다. $T$에서 $e'$을 $e$로 바꾸면 비용이 늘지 않는 신장 트리가 되므로 여전히 최소입니다. □

예제 12.12. 꼭짓점 $A, B, C, D$와 변의 비용 $AB = 1$, $BC = 2$, $AC = 3$, $CD = 4$, $BD = 5$, $AD = 6$.

최소 비용은 $1 + 2 + 4 = 7$입니다.

12.5 케일리 공식

정리 12.13 (케일리 공식). 꼭짓점에 $1, \dots, n$의 이름이 붙은 트리는 $n^{n-2}$개입니다. 곧 $K_n$의 신장 트리는 $n^{n-2}$개입니다.

$n = 3$이면 $3$개(가운데 꼭짓점을 고르는 방법), $n = 4$이면 $16$개입니다. 증명은 트리를 길이 $n - 2$인 수열(프뤼퍼 코드)과 일대일로 대응시켜 합니다. 잎 가운데 번호가 가장 작은 것을 지우며 그 이웃의 번호를 적는 것을 $n - 2$번 되풀이합니다.

쓰이는 곳. 결정 트리와 랜덤 포레스트(머신러닝), 이진 탐색 트리와 힙(자료구조), 파싱 트리(컴파일러), 계통수(생물학), 네트워크 설계(최소 신장 트리)가 이 강의 대상입니다.

12.6 이 장의 요약

• 트리 ⟺ 연결 + 회로 없음 ⟺ 연결 + 변 $n-1$개 ⟺ 경로가 유일.
• 높이 $h$ 이진 트리의 잎 $\le 2^h$. 완전 이진 트리: 잎 = 내부 + 1.
• 크루스칼: 싼 변부터, 회로를 만들면 버림. 이름 붙은 트리 $n^{n-2}$개.

문제

24

63

10

125

8530