트리
트리는 $ \forall v, w \in V $ 에 대해 $ v $ 에서 $ w $ 로의 유일한 단순 경로가 존재하는 그래프를 말한다. 루트 트리(rooted tree)는 특별한 정점이 루트(뿌리)로 지정된 트리이다. 근 트리라고도 한다.
어떤 정점 $ v $ 의 레벨(level)은 루트에서 $ v $ 로의 단순 경로의 길이가 되고, 루트 트리의 높이(height)는 최대 레벨 값이 된다.
$ T $ 가 루트 $ v_0 $ 를 가진 루트 트리이고, $ x, y, z \in V $ 이며 $ (v_0, v_1, \dots, v_n ) $ 을 $ T $ 에서의 단순 경로라 하면 기본적인 용어들은 다음과 같다.
- 부모 (parent): $ v_{n-1} $ 은 $ v_n $ 의 부모
- 조상 (ancestor): $ v_0, v_1, \dots, v_{n-1} $ 은 $ v_n $ 의 조상
- 자식 (child): $ v_n $ 은 $ v_{n-1} $ 의 자식
- 후손 (descendant): 만약 $ x $ 가 $ y $ 의 조상이라면 $ y $ 는 $ x $ 의 후손
- 형제 (sibling): 같은 부모를 가진 정점
- 말단 정점 (terminal vertex 혹은 leaf): 자식을 가지고 있지 않은 정점
- 내부 정점 (interminal vertex): 말단 정점이 아닌 정점
- 부분 트리 (sub tree): 임의의 노드 $ n $ 을 선택하여 그 노드의 후손과 후손들이 가지는 간선만 남기면 부분 트리
성질
$T $ 를 $ n $ 개의 정점을 가진 그래프라 하면 다음은 동치이다.
- $ T $ 는 트리이다.
- $ T $ 는 연결되어 있고, 비순환적이다.
- $ T $ 는 연결되고 $ n - 1 $ 개의 간선을 갖는다.
- $ T $ 는 비순환적이고 $ n - 1 $ 개의 간선을 갖는다.
$ T $ 가 트리이면 연결되어 있고, 비순환적이라는 것에 대한 증명은 다음과 같다.
트리에서는 임의의 정점에서 다른 모든 정점으로의 단순 경로가 있으므로 $ T $ 가 연결되어 있다. 만약 $ T $ 가 사이클 $ C^\prime $ 을 포함한다 가정하면 $ T $ 는 $ v_0 = v_n $ 인 단순 사이클 $ C = (v_0, \dots, v_n) $ 을 포함한다. $ T $ 가 단순 그래프이므로 $ C $ 는 루프가 될 수 없고, 그러므로 $ C $ 는 적어도 $ i < j $ 인 $2$개의 구별되는 정점 $ v_i $ 와 $ v_j $ 를 포함해야 한다. 즉 $ (v_i, v_{i+1}, \dots, v_j) $ 와 $ (v_i, v_{i-1}, \dots, v_0, v_{n-1}, \dots , v_j ) $ 는 $ v_i $ 에서 $ v_j $ 로의 서로 다른 단순 경로들이어야 한다. 그러나 이것은 트리의 정의에 모순되므로 트리는 사이클을 포함할 수 없다.
다음으로 $ T $ 가 연결되어 있고 비순환적이면 $ T $ 가 연결되고 $n -1 $ 개의 간선을 가진다는 것에 대한 증명은 다음과 같다.
$ n = 1 $ 일 때 $ T $ 는 단지 하나의 정점으로 구성되므로 간선이 없고, 따라서 가정이 성립한다. $ T $ 가 연결되어 있고 비순환적이며 $ n $ 개의 정점을 가진 그래프에서 가정이 성립한다 가정하자. 간선을 반복하지 않는 최대 길이의 경로 $ P $ 를 선택하면 $ T $ 는 비순환적이므로 사이클이 없다. 그러므로 $ P $ 는 차수가 $ 1 $인 정점 $ v $ 를 포함한다. 이때 $ T^\prime $ 을 $ T $ 에서 정점 $ v $ 와 $ v $ 에 결합된 간선을 제거한 것이라 하면 $T^\prime $ 은 연결되어 있고 비순환적이다. 또한 $ T^\prime $ 은 $ n $ 개의 정점을 가지고, 가정에 의해 $ T $ 는 $ n -1 $ 개의 간선을 가진다. 즉 $ T $ 는 $ n $ 개의 간선을 가진다. 초기 조건과 $ n $ 이 성립할 때 $ n+ 1 $ 이 성립함을 보였으므로 수학적 귀납법에 의해 가정은 참이다.
다음으로 $ T $ 가 연결되어 있고 $ n - 1 $ 개의 간선을 가질 때 $ T $ 가 비순환적이고 $ n - 1 $ 개의 간선을 가진다는 것에 대한 증명은 다음과 같다.
$ T $ 가 적어도 하나의 사이클을 가진다 가정하면 사이클에서 하나의 간선을 제거하더라도 그래프는 계속 연결되어 있으므로 간선을 제거한 그래프인 $ T^\prime $ 이 연결된 비순환 그래프가 될 때까지 $ T $ 에서 사이클을 구성하는 간선들을 정점들은 제거하지 안고 제거할 수 있다. $ T^\prime $ 을 $ n $ 개의 정점을 가진 연결된 비순환 그래프로 만들었다면 앞선 증명으로 인해 $ T^\prime $ 이 $n - 1 $ 개의 간선을 가져야 하지만, $ T $ 가 $ n - 1 $ 개 보다 많은 간선을 가져야 하므로 모순이고, 따라서 $ T $ 는 비순환적이다.
다음으로 $T $ 가 비순환적이고 $ n - 1 $ 개의 간선을 가질 때 $ T $ 가 트리라는 것에 대한 증명은 다음과 같다.
루프는 사이클인데 $ T $ 가 비순환적이라 가정했으므로 그래프 $ T $ 는 어떠한 루프도 포함할 수 없다. 마찬가지로 $T $ 는 $ v $ 와 $ w $ 에 결합된 서로 다른 간선 $ e_1 $ 과 $ e_2 $ 를 포함할 수 없다. 만약 포함한다면 사이클 $ (v, e_1, w, e_2, v) $ 를 가지기 때문이다. 그러므로 $T $ 는 단순 그래프이다.
$ T $ 가 연결되어 있지 않다고 가정할 때 $ T_1, T_2, \cdots , T_k $ 를 $ T $ 의 요소들이라 하자. $ T $ 가 연결되어 있지 않으므로 $ k > 1 $ 이다. $ T_i $ 가 $ n_i $ 개의 정점을 가진다 하자. 각각의 $ T_i $ 는 연결되어 있고 비순환적이므로 앞선 증명에 의해 $ T_i $ 는 $ n_i - 1 $ 개의 간선을 가진다. 즉 $ n - 1 = (n_1 - 1) + (n_2 - 1) + \cdots + (n_k - 1) = n_1 + n_2 + \cdots + n_k - k = n - k $ 여야 하는데, 이 식은 $ k > 1 $ 에 모순된다. 즉 $ T $ 는 연결되어 있다.
$ T $ 에서 $ a $ 에서 $ b $ 로의 서로 다른 단순 경로 $ P_1 $ 과 $ P_2 $ 가 존재한다고 가정할 때 $ c $ 는 $ a $ 다음에 있으면서 $ P_1 $ 상에는 있고, $ P_2 $ 상에는 없는 첫 번째 정점이고, $ d $ 는 $ P_1 $ 상에서 $ c $ 바로 앞의 정점이며, $ e $ 는 $ d $ 다음에 있으면서 $ P_1 $ 과 $P_2 $ 상에 모두 있는 첫 번째 정점이라 하자. 그렇다면 사이클이 생기고 비순환적이 아니게 된다. 따라서 $ T $ 는 임의의 정점에서 다른 정점으로의 유일한 단순 경로를 가진다.
종합하면 $ T $ 는 트리이다.
허프만 코드
문자를 가변 길의의 비트 문자열로 표현하는 방법인데, 문자열을 압축할 때 최적으로 사용할 수 있는 각 문자의 변환된 비트값이다. 많이 사용되는 문자를 표현할 때는 길이를 짧게, 적게 사용되는 문자를 표현할 때는 길이를 길게하는 방식으로 문자를 변환한다.
허프만 코드는 루트 트리에 의해 쉽게 정의되고, 디코딩하기 위해서는 루트에서 시작하여 문자를 만날 때까지 아래로 내려간다.
최적의 허프만 코드를 구성하는 알고리즘은 표현해야 하는 문자들의 발생 빈도를 기반으로 한다. 출력은 최하위 레벨에 빈도가 표시된 정점들이 있고, 비트들로 표기된 간선들이 있는 루트 트리이다. 코딩 트리는 각각의 발생 빈도를 그 발생 빈도를 갖는 문자들로 바꿈으로써 얻을 수 있다.
입력: $ f $ (빈도에 대한 수열), $ n $ (빈도에 대한 수열의 크기)
출력: $ T $ (최적의 허프만 코드를 정의한 근트리)
huffman(f, n) {
sort(f)
if (n == 2) {
T.left = f[1] // 빈도가 낮은 노드를 왼쪽 자식으로 연결
T.right = f[2] // 빈도가 높은 노드를 오른쪽 자식으로 연결
return T
}
merged = f[1] + f[2]
merged.left = f[1]
merged.right = f[2]
f = f - f[1] - f[2] + merged
sort(f)
return huffman(f, n-1)
}
