트리(Tree)

트리는 이어져 있으면서 순환(제자리로 돌아오는 고리)이 없는 그래프입니다. 겉보기에 다른 여러 조건이 모두 같은 뜻이라는 점이 트리를 특별하게 만듭니다. 꼭짓점이 n개인 그래프에 대해 다음은 서로 같습니다. 이어져 있고 순환이 없다. 이어져 있고 변이 n−1개다. 순환이 없고 변이 n−1개다. 어떤 두 점 사이에도 (같은 점을 두 번 지나지 않는) 길이 꼭 하나다. 이어져 있지만 변을 하나라도 빼면 끊어진다. 순환이 없지만 변을 하나라도 더하면 순환이 생긴다. 둘째와 셋째 조건이 보여 주듯, 변이 n−1개이기만 하면 '이어져 있다'와 '순환이 없다'는 한쪽이 다른 쪽을 부릅니다.

변이 n−1개인 이유는 잎⁠(leaf)⁠에 있습니다. 꼭짓점이 둘 이상인 트리에서 가장 긴 길을 잡으면 그 끝점은 이웃이 하나뿐인 잎입니다. 다른 이웃이 있다면 길을 더 늘이거나 순환이 생길 테니까요. 잎 하나와 그 변을 떼어 내면 꼭짓점이 하나 적은 트리가 남으니, 수학적 귀납법⁠(mathematical induction)⁠으로 변은 늘 꼭짓점보다 하나 적습니다.

보기: 새 무작위 트리. 꼭짓점 두 개를 차례로 누르면 그 사이의 변이 생기거나 없어집니다. 노란 점이 잎입니다. 점에 마우스를 올리거나 한 번 누르면 A에서 그 점까지의 길이 분홍으로 나타납니다.

이름 붙은 꼭짓점 n개 위의 트리는 몇 개일까요? 답은 $n^{n-2}$입니다. 독일의 수학자 카를 보르하르트가 1860년에 먼저 증명했지만, 1889년 영국의 수학자 케일리의 논문으로 널리 알려져 케일리 공식⁠(Cayley's formula)⁠이라 부릅니다. 예를 들어 점이 3개면 트리는 가운데 점을 고르는 3가지($3^1$)이고, 4개면 16가지입니다. 1918년 독일의 수학자 하인츠 프뤼퍼가 찾은 방법으로 깔끔하게 증명할 수 있습니다. 번호가 가장 작은 잎을 떼어 내고 그 이웃의 이름을 적기를 n−2번 되풀이하면 길이 n−2인 수열이 나오는데, 이 대응이 트리와 수열 사이의 일대일대응입니다. 그림 위의 트리를 이렇게 적은 것이 위의 '프뤼퍼 부호'이고, '새 무작위 트리'는 무작위 수열을 거꾸로 트리로 바꾼 것입니다. 꼭짓점 개면 트리는 개인데, 같은 점들 위의 그래프는 모두 $2^{\binom{n}{2}}$개(멱집합⁠(power set)⁠의 크기)로 개입니다. 이어진 그래프가 주어지면, 그 그래프의 변만 써서 모든 꼭짓점을 잇는 트리를 신장 트리⁠(spanning tree)⁠라고 합니다. 신장 트리의 개수는 행렬식⁠(determinant)⁠ 하나로 셀 수 있습니다. 대각선에는 각 점의 차수를, (i, j) 자리에는 i와 j가 이어져 있으면 −1을, 아니면 0을 적은 행렬⁠(matrix)⁠을 만들고, 아무 행 하나와 같은 번호의 열 하나를 지운 뒤 행렬식을 구하면 그것이 신장 트리의 개수입니다. 전기 회로의 법칙으로 유명한 독일의 물리학자 구스타프 키르히호프가 1847년에 찾은 행렬–트리 정리입니다. 삼각형이라면 지우고 남은 행렬이 $\begin{pmatrix} 2 & -1 \\ -1 & 2 \end{pmatrix}$이고 행렬식은 3인데, 실제로 변 셋 가운데 하나를 빼는 세 가지가 신장 트리입니다.

한 점을 뿌리로 정하면 트리는 가계도나 폴더 구조처럼 위아래가 생깁니다. 뿌리 있는 트리는 '뿌리 하나와 그 아래 매달린 더 작은 트리들'이라는 재귀⁠(recursion)⁠적인 정의를 가지고, 그래서 트리 위의 계산은 대개 재귀로 짭니다. 자식이 많아야 둘이고 왼쪽 자식과 오른쪽 자식을 구별하는 이진 트리⁠(binary tree)⁠는, 점이 n개일 때 n번째 카탈랑 수⁠(Catalan number)⁠만큼의 모양이 있습니다. 쓰임새도 많습니다. 각 점의 왼쪽 가지에는 그보다 작은 값만, 오른쪽 가지에는 큰 값만 두는 이진 탐색 트리⁠(binary search tree)⁠는 이진 탐색⁠(binary search)⁠을 자료 구조로 옮긴 것입니다. 부모가 늘 자식보다 작도록 쌓은 힙⁠(heap)⁠은 가장 작은 값을 늘 뿌리에 두어 우선순위 큐⁠(priority queue)⁠를 만듭니다. 잎마다 기호를 달고 뿌리에서 그 잎까지 왼쪽 가지는 0, 오른쪽 가지는 1로 적으면 부호가 정해집니다. 기호의 빈도에 맞춰 평균⁠(mean)⁠ 길이가 가장 짧도록 이런 트리를 만든 것이 허프만 부호⁠(Huffman coding)⁠입니다. 비교 정렬⁠(comparison sort)⁠이 할 수 있는 모든 비교를 가지로 펼친 결정 트리⁠(decision tree)⁠는 비교 정렬의 하한⁠(comparison sorting lower bound)⁠을 증명하는 도구이고, 예/아니오 질문으로 자료를 나누어 답을 내는 기계 학습⁠(machine learning)⁠의 결정 트리는 잎에 예측을 단 트리이며, 번갈아 두는 게임의 모든 수를 펼친 게임 트리⁠(game tree)⁠는 미니맥스⁠(minimax)⁠로 최선의 수를 고르는 데 쓰입니다. 또 문장의 짜임을 그린 구문 트리⁠(parse tree)⁠는 문맥 자유 문법⁠(context-free grammar)⁠에서 나옵니다.

이어지는 곳. 이어진 그래프는 모두 신장 트리를 품고 있고, 변마다 길이가 있을 때 길이의 합이 가장 작은 신장 트리가 최소 신장 트리⁠(minimum spanning tree)⁠입니다. 다익스트라 알고리즘⁠(Dijkstra's algorithm)⁠도 점마다 어느 이웃에서 왔는지를 기록하면 출발점을 뿌리로 하는 최단 경로⁠(shortest path)⁠ 트리를 남깁니다. 합집합-찾기⁠(union-find)⁠라는 자료 구조는 서로 겹치지 않는 무리 하나하나를 트리로 두고 그 뿌리를 무리의 대표로 삼습니다. 두 점이 같은 무리인지는 뿌리가 같은지로 확인하고, 두 무리를 합칠 때는 한 뿌리를 다른 뿌리 아래에 매답니다. 그래서 동치류⁠(equivalence class)⁠를 빠르게 합치고 확인할 수 있습니다. 공통 조상에서 갈라져 나온 언어나 생물의 계통수⁠(phylogenetic tree)⁠도 트리입니다. 옛 언어를 뿌리로, 그 후손 언어들을 가지로 그리는 비교 언어학⁠(comparative linguistics)⁠의 어족 나무가 그 예입니다.