2-1 根付き木と探索木
前提知識：距離・直径・中心
同じ木でも根をどこに置くかで物語が変わる
木は、任意の二頂点の間にただ一つのpathをもつ連結グラフです。ここまではどの頂点も対等でした。一つの頂点を根として選ぶと、各頂点には根へ向かう「親」が一意に定まり、木全体を小さな部分木へ分けられます。
例えば組織図では上司、file systemでは親directory、式では外側の演算が親になります。根付き木の価値は図を上下に描けることだけではありません。有限集合上の大きな問題を、子を根とする小さな同型の問題へ分解できることにあります。
根・親・子・深さ
根付き木|rooted treeとは、木 $T$ と指定された頂点 $r\in V(T)$ の組 $(T,r)$ である。$r$ を根という。
頂点 $v\ne r$ に対し、$r$ から $v$ への唯一のpath上で $v$ の直前にある頂点を $v$ の親といい $p(v)$ と書く。$p(v)=u$ のとき $v$ を $u$ の子という。
根から $v$ までの距離
$$
d(v)=d_T(r,v)
$$
を $v$ の深さという。木の高さを $h(T,r)=\max_{v\in V(T)}d(v)$ と定める。
根の深さは0です。根以外の各頂点には親が一つだけありますが、子は0個でも複数でも構いません。子をもたない頂点をleaf、子をもつ頂点をinternal vertexと呼びます。頂点が一つだけのrooted treeでは、根はleafです。
rooted tree $(T,r)$ の任意の $v\ne r$ に対して
$$
d(p(v))=d(v)-1
$$
である。また、各辺は親と子を結ぶ。
$r$ から $v$ への唯一のpathを
$$
r=v_0,v_1,\ldots,v_k=v
$$
とすると、定義により $p(v)=v_{k-1}$ です。従って $d(v)=k$、$d(p(v))=k-1$ です。
任意の辺 $xy$ を取ります。根から $x,y$ へのpathを比べます。もしどちらも他方を含まなければ、二つのpathが最後に共有する頂点から $x$ と $y$ へ分かれる二本のpathと辺 $xy$ がcycleを作り、木であることに反します。従って一方、例えば $x$ が根から $y$ へのpath上にあります。辺 $xy$ があるので $x$ は $y$ の直前でなければなりません。途中に別頂点があれば、そのpathと辺 $xy$ でcycleができます。ゆえに $x=p(y)$ です。□
この命題から、根以外の各頂点をその親へ結ぶ辺は全部で $|V(T)|-1$ 本あり、木の全辺をちょうど一度ずつ数えます。
祖先・子孫・部分木
頂点 $u$ が根 $r$ から頂点 $v$ へのpath上にあるとき、$u$ を $v$ の祖先 (根付き木)|祖先、$v$ を $u$ の子孫 (根付き木)|子孫という。頂点自身も自分の祖先・子孫に含める。
頂点 $u$ の子孫全体が誘導する部分グラフを $T_u$ と書き、根を $u$ とする根付き部分木|rooted subtreeとみなす。
$T_u$ は連結な木である。$u$ の相異なる子 $x,y$ に対し、$T_x$ と $T_y$ の頂点集合は交わらず、その間を結ぶ辺もない。
$u$ の子孫 $v$ を取ると、$u$ から $v$ へのpathは根から $v$ へのpathの後半です。その各頂点も $u$ の子孫なので、このpathは $T_u$ 内にあります。従って $T_u$ は連結です。木の部分グラフはcycleをもたないので $T_u$ は木です。
$T_x,T_y$ が頂点 $z$ を共有すると、根から $z$ への唯一のpath上で $u$ の直後に $x$ と $y$ の両方が現れることになり、$x=y$ に反します。
さらに $T_x$ の頂点 $a$ と $T_y$ の頂点 $b$ を結ぶ辺があると仮定します。$a$ から祖先をたどって $u$ へ行き、$u$ から $b$ へ下るpathと辺 $ab$ はcycleを作ります。これは $T$ が木であることに反します。□
従って根 $r$ の子を $c_1,\ldots,c_k$ とすれば、木全体は
$$
\{r\},T_{c_1},\ldots,T_{c_k}
$$
へ重なりなく分解されます。これが再帰の入口です。
親写像から木を復元する
rooted treeを描かなくても、「各頂点の親は誰か」という表だけで全体を指定できます。ただし、親を勝手に選ぶとcycleができたり、根へ到達できない頂点が生じたりします。
有限集合 $V$、指定元 $r\in V$、写像
$$
p:V\setminus\{r\}\longrightarrow V
$$
が与えられたとする。各 $v\ne r$ について反復
$$
v,p(v),p^2(v),\ldots
$$
が有限回で $r$ に到達するなら、辺集合
$$
E=\{\{v,p(v)\}\mid v\in V\setminus\{r\}\}
$$
は $V$ 上の木を定め、$r$ を根としたとき $p$ はその親写像になる。
逆に、任意の有限rooted treeの親写像はこの到達条件を満たす。
まず到達条件を仮定します。各 $v$ から親を反復すれば $r$ へ至るwalkが得られるので、グラフ $(V,E)$ は連結です。
辺を集合として書いたとき、異なる $v,w\ne r$ が同じ無向辺を与える可能性を除きます。もし
$$
\{v,p(v)\}=\{w,p(w)\}
$$
で $v\ne w$ なら、$p(v)=w$ かつ $p(w)=v$ です。この二頂点は親反復で往復し、$r$ へ到達しません。矛盾です。従って辺はちょうど $|V|-1$ 本あります。
木の特徴づけ「$n$ 頂点で連結かつ $n-1$ 辺なら木」により $(V,E)$ は木です。$v,p(v),\ldots,r$ を逆順に読めば $r$ から $v$ へのpathです。木ではこのpathが一意なので、$v$ の直前は $p(v)$ であり、与えた写像が親写像です。
逆にrooted treeでは、親へ移るたび命題 [27-prop-parent-depth] により深さが1減ります。深さは非負整数なので、$d(v)$ 回後に深さ0の唯一の頂点 $r$ へ到達します。□
有限性は重要です。無限集合 $\mathbb Z$ で $p(n)=n-1$ と置くと有向cycleはありませんが、どの頂点からも特定の根へ有限回で到達するとは限りません。
rooted treeに対する帰納法
通常の数学的帰納法は整数を一つずつ増やします。木では、子の部分木について証明した結果を親で組み合わせます。
有限rooted treeの各頂点 $v$ に関する命題 $P(v)$ を考える。任意の $v$ について
$v$ のすべての子 $c$ で $P(c)$ が成り立つなら $P(v)$ が成り立つ
ことを示せたとする。子をもたない場合もこの含意に含める。このとき全頂点で $P(v)$ が成り立つ。
$P(v)$ が成り立たない頂点があると仮定します。その中で深さが最大の頂点 $v$ を取れます。木は有限だからです。
$v$ の任意の子 $c$ は $d(c)=d(v)+1$ を満たします。$v$ の深さを反例中で最大に選んだため、子 $c$ は反例ではなく $P(c)$ が成り立ちます。従って仮定した含意から $P(v)$ も成り立ち、矛盾です。ゆえに反例はありません。□
葉では「すべての子で成立」が空条件として自動的に成り立つため、通常の帰納法の初期段階に対応します。
$s(v)=|V(T_v)|$ とする。$v$ の子全体を $C(v)$ と書けば
$$
s(v)=1+\sum_{c\in C(v)}s(c).
$$
補題 [27-lem-descendant-subtree] により、$T_v$ の頂点集合は $v$ 一点と、子 $c$ ごとの互いに素な $V(T_c)$ の和に分解されます。要素数を足せば式を得ます。□
子の順序を入れる
rooted treeだけでは、同じ親をもつ子に「左から何番目」という順序はありません。図で左右を入れ替えても同じrooted treeです。算法や式を表すときには順序が必要になります。
各頂点の子に線形順序を指定したrooted treeを順序付き根付き木|ordered rooted treeという。
各頂点の子が高々二つで、存在する子を左の子または右の子として区別したものを二分木|binary treeという。各internal vertexがちょうど二つの子をもつbinary treeをfull binary treeという。
子が一つだけのbinary treeでは、その子が左か右かも構造の一部です。一方、単に「子が高々二つ」のrooted treeでは左右を区別しません。この差は数え上げで重要になります。
有限full binary treeでinternal vertexが $I$ 個、leafが $L$ 個なら
$$
L=I+1.
$$
頂点総数は $I+L$ なので、木の辺数は
$$
I+L-1
$$
です。一方、各辺はあるinternal vertexからその子へ向かい、各internal vertexには子がちょうど二つあるため、親側から数えた辺数は $2I$ です。従って
$$
2I=I+L-1,
$$
これを整理して $L=I+1$ を得ます。□
preorderとpostorder
ordered rooted treeでは、子の順序を使って全頂点を再帰的に並べられます。
頂点 $v$ を根とするordered rooted subtreeについて、次のように定める。
- 先行順|preorder：まず $v$ を出力し、その後、子の部分木を左から順にpreorderで出力する。
- 後行順|postorder：子の部分木を左から順にpostorderで出力し、最後に $v$ を出力する。
例えば根 $r$ の子が左から $a,b$、$a$ の子が $c,d$、$b$ の子が $e$ なら
$$
\text{preorder}: r,a,c,d,b,e,
$$
$$
\text{postorder}: c,d,a,e,b,r.
$$
有限ordered rooted treeのpreorderとpostorderは、ともに全頂点をちょうど一度ずつ出力する。
rooted tree inductionを使います。leaf $v$ ではどちらも $v$ 一点だけを出力します。
$v$ の各子 $c$ の部分木で主張が成り立つとします。相異なる子の部分木は補題 [27-lem-descendant-subtree] により頂点を共有しません。また $T_v$ の頂点は $v$ と子の部分木へ分割されます。preorderもpostorderも $v$ を一度だけ出力し、各子の再帰呼出しがその部分木を一度ずつ出力するので、$T_v$ の全頂点を重複なく尽くします。根で主張を得ます。□
preorderは「親を処理してから子へ渡す」計算に向きます。postorderは「子の答えを集めてから親の答えを作る」計算に向き、部分木サイズ、高さ、式の値などを下から上へ計算できます。
最小共通祖先
二頂点が木のどこで枝分かれしたかを表す頂点を定義します。
rooted treeの二頂点 $u,v$ の共通祖先のうち、深さが最大のものを最小共通祖先|lowest common ancestorといい
$$
\operatorname{lca}(u,v)
$$
と書く。
有限rooted treeの任意の二頂点 $u,v$ は一意なlowest common ancestorをもつ。
根 $r$ は $u,v$ の共通祖先なので、共通祖先集合は空ではありません。有限集合なので深さ最大の共通祖先 $w$ が存在します。
一意性を示します。ある頂点の祖先は、根からその頂点への唯一のpath上に深さ順に並びます。従って $u$ の祖先で同じ深さをもつ頂点は高々一つです。深さ最大の共通祖先が二つあれば、どちらも $u$ の祖先で同じ最大深さをもつため一致します。□
根から $u,v$ へのpathを並べ、先頭から一致する最後の頂点を取ればlcaを計算できます。また距離はlcaを使って
$$
d_T(u,v)=d(u)+d(v)-2d(\operatorname{lca}(u,v))
$$
と書けます。
上の距離公式が成り立つ。
$w=\operatorname{lca}(u,v)$ とします。$u$ から $w$ へ親をたどるpathの長さは $d(u)-d(w)$、$w$ から $v$ へ下るpathの長さは $d(v)-d(w)$ です。これらをつないだwalkは頂点を重複しません。もし $w$ 以外を共有すれば、その共有頂点は $w$ より深い共通祖先になるからです。従ってこれは $u$ から $v$ への唯一のpathであり、長さは
$$
d(u)-d(w)+d(v)-d(w)
=d(u)+d(v)-2d(w)
$$
です。□
探索木との関係
「幅優先探索と深さ優先探索」のBFSとDFSは、各頂点を初めて発見した辺を親辺として記録しました。連結グラフ $G$ の始点 $r$ から得る親辺集合は全頂点を含む木、すなわちspanning treeになります。
連結グラフ $G$ を始点 $r$ から探索し、$r$ 以外の各頂点 $v$ に、それを初めて発見した頂点 $p(v)$ を割り当てる。発見時刻が親から子へ厳密に増えるなら、親辺 $vp(v)$ 全体は $G$ のrooted spanning treeを作る。
各親辺は探索時に実際に調べた $G$ の辺です。親へ移るたび発見時刻が厳密に小さくなるので、同じ頂点を巡るcycleには入れません。有限個の頂点上で親を反復すると、親をもたない唯一の始点 $r$ へ到達します。従って親写像の特徴づけ [27-thm-parent-map-characterization] により、親辺は $V(G)$ 上の木を作ります。全頂点を含むのでspanning treeです。□
BFS treeでは深さが元のグラフでの最短距離と一致します。DFS treeでは発見・終了時刻の区間が祖先関係を表します。探索算法固有の証明は「幅優先探索と深さ優先探索」、rooted treeとして共通に使える再帰構造は本章が担当します。
式を木として計算する
算術式
$$
(2+3)(7-4)
$$
を考えます。根を掛け算、その左部分木を加算、右部分木を減算、数をleafとするfull binary treeで表せます。
×
/ \
+ −
/ \ / \
2 3 7 4
postorderは
$$
2,3,+,7,4,-,\times
$$
となります。左部分木を計算して5、右部分木を計算して3、最後に根で掛けて15を得ます。括弧がなくても計算順序が一意なのは、木の親子関係が演算の結合順序を保持しているからです。
leafに数、各internal vertexに二項演算が付いた有限full binary treeでは、各頂点 $v$ の値を
$$
\operatorname{val}(v)=
\begin{cases}
v\text{ に書かれた数},&v\text{ がleaf},\\
\operatorname{val}(v_L)\mathbin{\circ_v}\operatorname{val}(v_R),&v\text{ がinternal}
\end{cases}
$$
と再帰的に定められる。postorderで処理すれば、各演算を一度ずつ実行して根の値を得る。
rooted tree inductionを使います。leafの値はlabelとして既に定まっています。internal vertex $v$ では、左の子 $v_L$ と右の子 $v_R$ の値が再帰的に一意に定まっていれば、指定された二項演算 $\circ_v$ により $v$ の値も一意に定まります。従って全頂点、特に根の値が定まります。
postorderでは子が親より前に現れるため、$v$ を処理する時点で二つの子の値は計算済みです。各internal vertexは一度だけ出力されるので、対応する演算も一度だけ実行されます。□
演習
頂点集合 $\{r,a,b,c,d,e,f\}$、辺集合
$$
\{ra,rb,ac,ad,be,ef\}
$$
の木を $r$ で根付ける。各頂点の親と深さを求め、$T_b$ の頂点集合と木の高さを書け。
根 $r$ の深さは0で親はありません。$a,b$ の親は $r$、深さは1です。$c,d$ の親は $a$、$e$ の親は $b$ で、深さは2です。$f$ の親は $e$、深さは3です。
$b$ の子孫は $b,e,f$ なので
$$
V(T_b)=\{b,e,f\}.
$$
最大深さは $f$ の3であり、木の高さは3です。□
$V=\{r,a,b,c,d\}$ 上で
$$
p(a)=r,\quad p(b)=a,\quad p(c)=d,\quad p(d)=c
$$
とする。この親表が根 $r$ のrooted treeを定めない理由を述べ、$p(d)$ だけを変更してrooted treeになる例を一つ作れ。
$c$ から親をたどると
$$
c,d,c,d,\ldots
$$
と有向2-cycleを巡り、$r$ へ到達しません。従って親写像の到達条件を満たしません。無向辺集合では $c$ と $d$ が同じ一本の辺を互いの親辺として指定するため、$r,a,b$ の成分から切り離されます。
例えば $p(d)=b$ と変更すれば、$c\to d\to b\to a\to r$ と全頂点が根へ到達します。辺集合は
$$
\{ar,ab,cd,bd\}
$$
で、これはrooted treeです。□
leafが16個ある有限full binary treeのinternal vertex数、総頂点数、辺数を求めよ。
定理 [27-thm-full-binary-leaves] の $L=I+1$ に $L=16$ を入れると $I=15$ です。総頂点数は
$$
I+L=15+16=31,
$$
木の辺数は総頂点数より1少ないので30です。親から子へ出る辺を数えても $2I=30$ になります。□
根 $r$ の子が左から $a,b,c$、$a$ の子が左から $d,e$、$c$ の唯一の子が $f$ であるordered rooted treeのpreorderとpostorderを書け。
preorderでは親を先に出し、子の部分木を左から処理するので
$$
r,a,d,e,b,c,f
$$
です。postorderでは子を先に処理して親を最後に出すので
$$
d,e,a,b,f,c,r
$$
です。各列に七頂点が一度ずつ現れます。□
最初の演習の木で $\operatorname{lca}(c,d)$ と $\operatorname{lca}(c,f)$ を求め、距離公式から $d_T(c,f)$ を計算せよ。
$c,d$ の根pathはそれぞれ $r,a,c$ と $r,a,d$ なので、最後の共通頂点は $a$ です。従って
$$
\operatorname{lca}(c,d)=a.
$$
$c$ の根pathは $r,a,c$、$f$ の根pathは $r,b,e,f$ なので、共通祖先は根だけで
$$
\operatorname{lca}(c,f)=r.
$$
深さは $d(c)=2,d(f)=3,d(r)=0$ だから
$$
d_T(c,f)=2+3-2\cdot0=5.
$$
実際、pathは $c,a,r,b,e,f$ で5辺です。□
式
$$
(8-3)\bigl(2+(6/3)\bigr)
$$
の式木を、各二項演算をinternal vertex、各数をleafとして記述せよ。preorderとpostorderを演算記号・数の列として書き、postorder順に値を計算せよ。
根は掛け算です。左の子は $-$ でleaf 8,3をもち、右の子は $+$ で、左leaf 2と、leaf 6,3をもつ右の子 $/$ をもちます。
preorderは
$$
\times,-,8,3,+,2,/,6,3,
$$
postorderは
$$
8,3,-,2,6,3,/,+,\times
$$
です。postorderで
$$
8-3=5,\qquad 6/3=2,\qquad 2+2=4,\qquad 5\cdot4=20
$$
と計算し、根の値20を得ます。□
本章で得たもの
木に根を指定すると、各辺が親から子へ向き、深さが定まり、相異なる子の部分木へ重なりなく分解できます。親写像が木を定めるための条件は、全頂点が親反復で根へ到達することです。この構造からrooted tree induction、preorder・postorder、lca、式木の再帰評価が生まれました。
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
