M - Fractal Tree Isomorphism 解説 by sotanishy
1. 同型である必要十分条件
本解説では，「木」と言った場合有限の根付き木を指します．木または fractal tree \(S,T\) が同型であることを \(S\cong T\) と表します．木 \(P,Q\) について， \(P_\infty \cong Q_\infty\) である必要十分条件を導出します．
定義
木 \(T\) の葉の集合を \(L(T)\) と置く．
木 \(T\) の サイズ \(s(T)\) を，\(s(T) = |T| - |L(T)|\) と定義する．
1 頂点からなる (唯一の) 木を \(I\) と置く．ただし，その唯一の頂点は根でも葉でもあるとする．
木 \(T_0\) が木 \(T\) の繰り返し単位であるとは，木 \(S := I\) に対して以下の操作を \(0\) 回以上適用することで \(S\) を \(T\) に一致させられることと定義する．
- \(S\) の葉を一つ選び，それを \(T_0\) で置き換えたものを改めて \(S\) と置く
特に，任意の木は \(I\) の繰り返し単位である．
木 \(S\) のすべての葉を木または fractal tree \(T\) で置き換えたものを \(S * T\) と置く．ただし， \(S * T\) における \(S\) 由来の頂点と， \(S\) の頂点そのものを断りなく同一視する．このとき，以下が成り立つ．
- 任意の木 \(S\) と問題文で定義した \(f(S)\) について \(f(S) = S * S\)
- 任意の木 \(T\) と \(T\) から誘導される fractal tree \(T_\infty\) について \(T_\infty \cong T * T_\infty\)
補題 1
2 つの木 \(S,T\) に対して， \(S * T_\infty \cong T_\infty \Leftrightarrow S_\infty \cong T_\infty\)
証明
($\Rightarrow$) 実際に同型射 $\varphi : S_\infty \to T_\infty$ を構成することで示す． $S$ について，問題文で定義した木の無限列 $(S_1,S_2,\dots)$ を考える．各 $n\in\mathbb{Z}^+$ に対して，以下を満たす同型射 $\varphi_n : S_n * T_\infty \to T_\infty$ が存在する．- $\varphi_n(S_n) = \varphi_{n+1}(S_n)$
- 仮定より存在する $S * T_\infty$ から $T_\infty$ への同型射を $\varphi_1$ とする．
- $\varphi_n$ から $\varphi_{n+1}$ を構成する．$T_\infty \cong S_n * T_\infty \cong S_n * (S_n * T_\infty) \cong (S_n * S_n) * T_\infty \cong S_{n+1} * T_\infty$ であるから，$S_{n+1} * T_\infty$ から $T_\infty$ への同型射 $\varphi_{n+1}$ が存在する．また，式変形から明らかに，$\varphi_{n+1}(S_n)=\varphi_n(S_n)$ となるように $\varphi_{n+1}$ を取れる．
- $v \in S_\infty$ に対し，$v \in S_n$ となる $n \in \mathbb{Z}^+$ を取り，$\varphi(v) := \varphi_n(v)$ とする
($\Leftarrow$) $S * T_\infty \cong S * S_\infty \cong S_\infty \cong T_\infty$
補題 2
Fractal tree \(T_\infty\) に対して，\((T')_\infty \cong T_\infty\) を満たす木 \(T'\) のうち頂点数が最小のもの \(T_0\) が一意的に存在して，次が成り立つ:
- \((T')_\infty \cong T_\infty\) を満たす任意の木 \(T'\) について， \(T_0\) は \(T'\) の繰り返し単位である．
証明
$(T')_\infty \cong T_\infty$ を満たす木 $T'$ のうち頂点数が最小のものを任意に 1 つ取り， $T_0$ と置く．背理法で示す．すなわち， $(T')_\infty \cong T_\infty$ となる木 $T'$ であって， $T_0$ を繰り返し単位として持たないものが存在すると仮定して矛盾を導く．
木 $S:=T'$ に対して， $|S|\geq |T_0|$ である間，以下の一連の操作を繰り返す:
-
$S$ と $T_0$ を根を合わせて重ねて，重なった部分を切り取ったものを $F$ とする．より形式的には，以下の操作を行う．
- $S * T_\infty \cong T_\infty$ となることが帰納的に示せる．補題 1 より $S_\infty \cong T_\infty$ だから，同型射 $\varphi: (T_0)_\infty \to S_\infty$ が取れる． $F := (S - \varphi(T_0-L(T_0))) \cup (\varphi(T_0) - (S - L(S)))$ とする．
- $F$ は $S$ と $\varphi(T_0)$ のいくつかの部分木からなる森である．そのうち， $T_0$ を繰り返し単位として持たないような部分木を任意に 1 つ取り (背理法の仮定より，そのような部分木は必ず存在する)，それを改めて $S$ とおく．
一意性は，条件を満たす木のうち頂点数が最小のものを 2 つ取ったとき，それらが互いの繰り返し単位となっていることからわかる．
定理
木 \(P,Q\) に対して， \(P_\infty \cong Q_\infty\) である必要十分条件は，\(P, Q\) の最小繰り返し単位を \(P_0, Q_0\) としたとき，\(P_0 \cong Q_0\) であることである．
証明
(必要性) $P_\infty \cong Q_\infty$ について，補題 2 の木 $T_0$ をとると，$T_0$ は $P,Q$ の最小繰り返し単位である．(十分性) $P_\infty \cong (P_0)_\infty,\,Q_\infty \cong (Q_0)_\infty$ からわかる．
よって，各 \(i=1,2,\dots,K\) に対し，木 \(T_i\) の最小繰り返し単位を求め，それらの同型性を判定することでこの問題を解くことができます．
2. 最小繰り返し単位の求め方
木 \(T\) の最小繰り返し単位を \(O(N d(N))\) または \(O(Nd(N)\log N)\) 時間で求めるアルゴリズムを構成します (ここで，\(d(N)\) は \(N\) の約数の個数です)．
まず，\(T\) の部分木を同値類に分類し，各同値類に一意的なラベルを付与します．これは，hash を用いれば \(O(N)\) 時間で確率的に，AHU algorithm を用いれば \(O(N\log N)\) 時間で決定的に求まります．
次に，最小繰り返し単位 \(T_0\) の候補となる木を \(O(d(N))\) 個に絞ります．まず，\(T_0\) は \(T\) のいずれかの部分木と一致します．さらに，\(T\) のすべてのサイズ \(s(T_0)\) の部分木は \(T_0\) と一致します．よって，正整数 \(M\) を固定したとき，\(T\) のサイズ \(M\) の部分木がすべて同型ならばそのうちの 1 つのみを調べればよく，そうでないならば \(s(T_0)=M\) となることはあり得ません．同型性の判定は，先に求めておいたラベルを利用すればよいです．また，\(M\) は \(s(T)\) の約数となるもののみ調べればよいです．
次に，木 \(T'\) を固定したとき，それが \(T\) の繰り返し単位となっているかを \(O(N)\) 時間または \(O(N\log N)\) 時間で判定します．再び \(T\) の部分木のラベルを hash や AHU algorithm を用いてボトムアップに求めて行き，ある部分木のラベルが \(T'\) のラベルに一致したとき，その部分木を \(I\) で置き換えることを繰り返します．最終的に残った木が \(I\) ならば，\(T'\) は \(T\) の繰り返し単位です．
3. 実装例
AHU algorithm による \(O(N d(N) \log N)\) 時間解法の実装例です．
#include <bits/stdc++.h>
using namespace std;
int find_smallest_repeat_unit(const vector<vector<int>>& G,
map<vector<int>, int>& mp) {
int n = G.size();
vector<int> label(n), sz(n);
auto calc_label = [&](int target = -1) {
for (int v = n - 1; v >= 0; --v) {
if (G[v].empty()) continue;
sz[v] = 1;
// v を根とする部分木のラベルを計算
vector<int> ch;
for (int c : G[v]) {
sz[v] += sz[c];
ch.push_back(label[c]);
}
sort(ch.begin(), ch.end());
if (!mp.count(ch)) {
mp[ch] = mp.size();
}
label[v] = mp[ch];
// v を根とする部分木が target と一致していたら I に置き換える
if (label[v] == target) {
label[v] = 0;
}
}
};
// 各部分木のラベルを計算
calc_label();
// 各サイズについて，最小繰り返し単位の候補となる部分木のラベルを求める
// -1: 未使用, -2: そのサイズの部分木が複数種類ある
vector<int> cand(n + 1, -1);
for (int i = 0; i < n; ++i) {
if (cand[sz[i]] == -1) {
cand[sz[i]] = label[i];
} else if (cand[sz[i]] != label[i]) {
cand[sz[i]] = -2;
}
}
for (int i = 1; i <= sz[0]; ++i) {
if (sz[0] % i == 0 && cand[i] >= 0) {
// サイズ i の候補を試す
calc_label(cand[i]);
if (label[0] == 0) {
return cand[i];
}
}
}
assert(false);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(15);
int K;
cin >> K;
vector<vector<vector<int>>> T(K); // 各木の各頂点の子のリスト
for (int i = 0; i < K; ++i) {
int N;
cin >> N;
T[i].resize(N);
for (int j = 1; j < N; ++j) {
int p;
cin >> p;
--p;
T[i][p].push_back(j);
}
}
map<vector<int>, int> mp;
mp[{}] = 0;
vector<int> label(K);
for (int i = 0; i < K; ++i) {
label[i] = find_smallest_repeat_unit(T[i], mp);
}
for (int i = 0; i < K; ++i) {
string s(K, '0');
for (int j = 0; j < K; ++j) {
if (label[i] == label[j]) s[j] = '1';
}
cout << s << "\n";
}
}
投稿日時:
最終更新: