Prüfer 코드¶
이 글에서는 이른바 Prüfer 코드(또는 Prüfer 수열)를 살펴봅니다. Prüfer 코드는 레이블이 붙은 트리를 수열로 유일하게 인코딩하는 방법입니다.
Prüfer 코드를 이용하여 Cayley 공식(완전 그래프의 신장 트리 개수를 나타내는 공식)을 증명합니다. 또한 그래프에 간선을 추가하여 연결 그래프로 만드는 방법의 수를 세는 문제의 풀이도 소개합니다.
참고: 정점 하나로만 이루어진 트리는 다루지 않습니다. 이는 여러 명제가 서로 충돌하는 특수한 경우입니다.
Prüfer 코드¶
Prüfer 코드는 $n$개의 정점을 가진 레이블 트리를 구간 $[0; n-1]$에 속하는 $n - 2$개의 정수로 이루어진 수열로 인코딩하는 방법입니다. 또한 이 인코딩은 완전 그래프의 모든 신장 트리와 수열 사이의 전단사 함수 역할을 합니다.
표현 방식의 특성상 Prüfer 코드를 트리의 저장이나 연산에 사용하는 것은 실용적이지 않지만, Prüfer 코드는 주로 조합론 문제를 풀 때 자주 사용됩니다.
창안자인 Heinz Prüfer는 1918년에 Cayley 공식의 증명으로 이 코드를 제안했습니다.
주어진 트리의 Prüfer 코드 구하기¶
Prüfer 코드는 다음과 같이 구성합니다. 다음 과정을 $n - 2$번 반복합니다. 트리에서 번호가 가장 작은 리프를 골라 트리에서 제거하고, 그 리프와 연결되어 있던 정점의 번호를 기록합니다. $n - 2$번 반복하고 나면 정점이 $2$개만 남게 되며, 알고리즘이 종료됩니다.
따라서 주어진 트리의 Prüfer 코드는 $n - 2$개의 수로 이루어진 수열이며, 각 수는 연결되어 있던 정점의 번호, 즉 구간 $[0, n-1]$에 속하는 수입니다.
Prüfer 코드를 계산하는 알고리즘은 현재의 모든 리프 목록을 담고 최솟값을 꺼낼 수 있는 자료 구조(예를 들어 C++의 set이나 priority_queue)를 사용하기만 하면 $O(n \log n)$ 시간 복잡도로 쉽게 구현할 수 있습니다.
vector<vector<int>> adj;
vector<int> pruefer_code() {
int n = adj.size();
set<int> leafs;
vector<int> degree(n);
vector<bool> killed(n, false);
for (int i = 0; i < n; i++) {
degree[i] = adj[i].size();
if (degree[i] == 1)
leafs.insert(i);
}
vector<int> code(n - 2);
for (int i = 0; i < n - 2; i++) {
int leaf = *leafs.begin();
leafs.erase(leafs.begin());
killed[leaf] = true;
int v;
for (int u : adj[leaf]) {
if (!killed[u])
v = u;
}
code[i] = v;
if (--degree[v] == 1)
leafs.insert(v);
}
return code;
}
그러나 이 구성은 선형 시간에도 구현할 수 있습니다. 그러한 방법을 다음 절에서 설명합니다.
주어진 트리의 Prüfer 코드를 선형 시간에 구하기¶
이 알고리즘의 핵심은 이동 포인터를 사용하는 것입니다. 이 포인터는 항상 제거하려는 현재 리프 정점을 가리킵니다.
언뜻 보면 이는 불가능해 보입니다. Prüfer 코드를 구성하는 과정에서 리프 번호가 증가할 수도 있고 감소할 수도 있기 때문입니다. 그러나 자세히 살펴보면 실제로는 그렇지 않습니다. 리프의 개수는 증가하지 않습니다. 개수가 하나 줄어들거나(리프 정점 하나를 제거하고 새 리프가 생기지 않는 경우), 그대로 유지됩니다(리프 정점 하나를 제거하고 새 리프가 하나 생기는 경우). 첫 번째 경우에는 다음으로 작은 리프 정점을 찾는 것 외에 다른 방법이 없습니다. 그러나 두 번째 경우에는 새로 리프 정점이 된 정점을 계속 사용할 수 있는지, 아니면 다음으로 작은 리프 정점을 찾아야 하는지를 $O(1)$ 시간에 판단할 수 있습니다. 그리고 꽤 많은 경우에 새 리프 정점으로 계속 진행할 수 있습니다.
이를 위해 변수 $\text{ptr}$를 사용합니다. 이 변수는 $0$부터 $\text{ptr}$까지의 정점 집합에 리프 정점이 최대 하나, 즉 현재 리프만 있음을 나타냅니다. 이 범위의 다른 모든 정점은 이미 트리에서 제거되었거나, 여전히 인접한 정점이 둘 이상입니다. 동시에 $\text{ptr}$보다 큰 리프 정점은 아직 하나도 제거하지 않았다고 합시다.
이 변수는 첫 번째 경우에 이미 매우 유용합니다. 현재 리프 노드를 제거한 후에는 $0$과 $\text{ptr}$ 사이에 리프 노드가 있을 수 없다는 것을 알고 있으므로, 다음 리프 노드의 탐색을 곧바로 $\text{ptr} + 1$에서 시작할 수 있으며 정점 $0$부터 다시 탐색을 시작할 필요가 없습니다. 그리고 두 번째 경우는 다시 두 가지 경우로 나눌 수 있습니다. 새로 얻은 리프 정점이 $\text{ptr}$보다 작다면, $\text{ptr}$보다 작은 다른 정점이 없다는 것을 알고 있으므로 이 정점이 반드시 다음 리프 정점입니다. 그렇지 않다면 새로 얻은 리프 정점이 더 큽니다. 이 경우에는 그 정점이 $\text{ptr}$보다 커야 한다는 것도 알고 있으므로, $\text{ptr} + 1$에서 다시 탐색을 시작할 수 있습니다.
다음 리프 정점을 찾기 위해 선형 탐색을 여러 번 수행해야 할 수도 있지만, 포인터 $\text{ptr}$은 증가하기만 하므로 전체 시간 복잡도는 $O(n)$입니다.
vector<vector<int>> adj;
vector<int> parent;
void dfs(int v) {
for (int u : adj[v]) {
if (u != parent[v]) {
parent[u] = v;
dfs(u);
}
}
}
vector<int> pruefer_code() {
int n = adj.size();
parent.resize(n);
parent[n-1] = -1;
dfs(n-1);
int ptr = -1;
vector<int> degree(n);
for (int i = 0; i < n; i++) {
degree[i] = adj[i].size();
if (degree[i] == 1 && ptr == -1)
ptr = i;
}
vector<int> code(n - 2);
int leaf = ptr;
for (int i = 0; i < n - 2; i++) {
int next = parent[leaf];
code[i] = next;
if (--degree[next] == 1 && next < ptr) {
leaf = next;
} else {
ptr++;
while (degree[ptr] != 1)
ptr++;
leaf = ptr;
}
}
return code;
}
코드에서는 먼저 각 정점에 대해 그 조상 parent[i], 즉 이 정점을 트리에서 제거할 때 이 정점이 갖게 될 조상을 찾습니다. 이 조상은 정점 $n-1$을 루트로 삼아 트리를 구성하면 찾을 수 있습니다. 이것이 가능한 이유는 정점 $n-1$이 트리에서 절대 제거되지 않기 때문입니다. 또한 각 정점의 차수도 계산합니다. ptr은 (현재 리프 leaf를 제외한) 남은 리프 정점 중 최솟값을 가리키는 포인터입니다. next도 리프 정점이고 ptr보다 작다면 현재 리프 정점을 next로 지정하고, 그렇지 않다면 포인터를 증가시키며 가장 작은 리프 정점을 찾는 선형 탐색을 시작합니다.
이 코드의 복잡도가 $O(n)$임은 쉽게 알 수 있습니다.
Prüfer 코드의 몇 가지 성질¶
- Prüfer 코드를 구성하고 나면 두 개의 정점이 남습니다. 그중 하나는 가장 큰 정점 $n-1$이지만, 나머지 하나에 대해서는 달리 말할 수 있는 것이 없습니다.
- 각 정점은 Prüfer 코드에 정확히 정해진 횟수, 즉 차수에서 1을 뺀 횟수만큼 나타납니다. 이는 쉽게 확인할 수 있습니다. 코드에 정점의 레이블을 기록할 때마다 차수가 줄어들고, 차수가 $1$이 되면 그 정점을 제거하기 때문입니다. 남은 두 정점에 대해서도 이 사실은 성립합니다.
Prüfer 코드를 이용한 트리 복원¶
트리를 복원하려면 앞 절에서 다룬 성질에만 주목하면 충분합니다. 우리는 원하는 트리에 있는 모든 정점의 차수를 이미 알고 있습니다. 따라서 모든 리프 정점을 찾을 수 있으며, 첫 번째 단계에서 제거된 첫 리프(가장 작은 리프여야 합니다)도 찾을 수 있습니다. 이 리프 정점은 Prüfer 코드의 첫 번째 칸에 있는 수에 해당하는 정점과 연결되어 있었습니다.
이렇게 해서 Prüfer 코드가 생성될 때 처음으로 제거된 간선을 찾았습니다. 이 간선을 답에 추가하고 간선 양 끝의 차수를 줄일 수 있습니다.
Prüfer 코드의 모든 수를 사용할 때까지 이 작업을 반복합니다. 차수가 $1$인 가장 작은 정점을 찾아 Prüfer 코드의 다음 정점과 연결하고, 차수를 줄입니다.
마지막에는 차수가 $1$인 정점 두 개만 남습니다. 이들은 Prüfer 코드 과정에서 제거되지 않은 정점입니다. 이 둘을 연결하여 트리의 마지막 간선을 얻습니다. 그중 하나는 항상 정점 $n-1$입니다.
이 알고리즘은 $O(n \log n)$에 쉽게 구현할 수 있습니다. 최솟값 추출을 지원하는 자료 구조(예를 들어 C++의 set<> 또는 priority_queue<>)를 사용하여 모든 리프 정점을 저장합니다.
다음 구현은 트리에 해당하는 간선 목록을 반환합니다.
vector<pair<int, int>> pruefer_decode(vector<int> const& code) {
int n = code.size() + 2;
vector<int> degree(n, 1);
for (int i : code)
degree[i]++;
set<int> leaves;
for (int i = 0; i < n; i++) {
if (degree[i] == 1)
leaves.insert(i);
}
vector<pair<int, int>> edges;
for (int v : code) {
int leaf = *leaves.begin();
leaves.erase(leaves.begin());
edges.emplace_back(leaf, v);
if (--degree[v] == 1)
leaves.insert(v);
}
edges.emplace_back(*leaves.begin(), n-1);
return edges;
}
Prüfer 코드를 이용하여 선형 시간에 트리 복원하기¶
선형 시간에 트리를 얻으려면 Prüfer 코드를 선형 시간에 얻을 때 사용한 것과 같은 기법을 적용할 수 있습니다.
최솟값을 추출하기 위한 자료 구조는 필요하지 않습니다. 그 대신 현재 간선을 처리한 후에는 단 하나의 정점만이 리프가 된다는 점에 주목할 수 있습니다. 따라서 이 정점으로 계속 진행하거나, 포인터를 이동시키는 선형 탐색으로 더 작은 정점을 찾을 수 있습니다.
vector<pair<int, int>> pruefer_decode(vector<int> const& code) {
int n = code.size() + 2;
vector<int> degree(n, 1);
for (int i : code)
degree[i]++;
int ptr = 0;
while (degree[ptr] != 1)
ptr++;
int leaf = ptr;
vector<pair<int, int>> edges;
for (int v : code) {
edges.emplace_back(leaf, v);
if (--degree[v] == 1 && v < ptr) {
leaf = v;
} else {
ptr++;
while (degree[ptr] != 1)
ptr++;
leaf = ptr;
}
}
edges.emplace_back(leaf, n-1);
return edges;
}
트리와 Prüfer 코드 사이의 전단사¶
각 트리에는 그에 대응하는 Prüfer 코드가 존재합니다. 그리고 각 Prüfer 코드로부터 원래의 트리를 복원할 수 있습니다.
이로부터 모든 Prüfer 코드(즉, 범위 $[0; n - 1]$에 속하는 $n-2$개의 수로 이루어진 수열) 또한 하나의 트리에 대응한다는 것이 따라 나옵니다.
따라서 모든 트리와 모든 Prüfer 코드는 전단사(일대일 대응)를 이룹니다.
Cayley의 공식¶
Cayley의 공식에 따르면 정점이 $n$개인 완전 레이블 그래프의 신장 트리 개수는 다음과 같습니다.
이 공식에는 여러 가지 증명이 있습니다. Prüfer 코드 개념을 이용하면 이 명제는 전혀 놀랍지 않습니다.
실제로 구간 $[0; n-1]$에 속하는 $n-2$개의 수로 이루어진 모든 Prüfer 코드는 $n$개의 정점을 가진 어떤 트리에 대응합니다. 따라서 이러한 서로 다른 Prüfer 코드는 $n^{n-2}$개 있습니다. 이러한 각 트리는 $n$개의 정점을 가진 완전 그래프의 신장 트리이므로, 이러한 신장 트리의 개수 또한 $n^{n-2}$입니다.
그래프를 연결 그래프로 만드는 방법의 수¶
Prüfer 코드의 개념은 이보다 훨씬 더 강력합니다. 이를 이용하면 Cayley의 공식보다 훨씬 더 일반적인 공식을 만들 수 있습니다.
이 문제에서는 $n$개의 정점과 $m$개의 간선을 가진 그래프가 주어집니다. 이 그래프는 현재 $k$개의 연결 요소로 이루어져 있습니다. 그래프가 연결되도록 $k-1$개의 간선을 추가하는 방법의 수를 계산하고자 합니다(당연히 $k-1$은 그래프를 연결하는 데 필요한 최소 개수입니다).
이 문제를 풀기 위한 공식을 유도해 봅시다.
그래프의 연결 요소들의 크기를 $s_1, \dots, s_k$로 나타냅니다. 하나의 연결 요소 내부에는 간선을 추가할 수 없습니다. 따라서 이 문제는 $k$개의 정점을 가진 완전 그래프의 신장 트리 개수를 구하는 문제와 매우 비슷하다는 것을 알 수 있습니다. 유일한 차이점은 각 정점이 실제로는 크기 $s_i$를 가진다는 것입니다: 정점 $i$에 연결되는 각 간선은 실제로 답에 $s_i$를 곱합니다.
따라서 가능한 방법의 수를 계산하려면 연결 트리에서 $k$개의 정점 각각이 몇 번 사용되는지 세는 것이 중요합니다. 이 문제에 대한 공식을 얻으려면 가능한 모든 차수에 대해 답을 합해야 합니다.
정점들을 연결한 후 트리에서 각 정점의 차수를 $d_1, \dots, d_k$라고 합시다. 차수의 합은 간선 개수의 두 배입니다:
정점 $i$의 차수가 $d_i$이면, 그 정점은 Prüfer 코드에 $d_i - 1$번 나타납니다. 정점이 $k$개인 트리의 Prüfer 코드는 길이가 $k-2$입니다. 따라서 수 $i$가 정확히 $d_i - 1$번 나타나는, $k-2$개의 수로 이루어진 코드를 고르는 방법의 수는 다항 계수와 같습니다
정점 $i$에 인접한 각 간선이 답에 $s_i$를 곱한다는 사실로부터, 정점들의 차수가 $d_1, \dots, d_k$라고 가정할 때 다음과 같은 답을 얻습니다:
최종 답을 얻으려면 차수를 고르는 모든 가능한 방법에 대해 이를 합해야 합니다:
지금은 이것이 정말 끔찍한 답처럼 보이지만, 다음과 같은 다항 정리를 사용할 수 있습니다:
이미 꽤 비슷해 보입니다. 이를 사용하려면 $e_i = d_i - 1$로 치환하기만 하면 됩니다:
다항 정리를 적용하면 문제의 답을 얻습니다:
우연히도 이 공식은 $k = 1$일 때도 성립합니다.