Kruskalの木定理(Kruskal's tree theorem)とは、有限の木の全体が位相的マイナーの関係について整擬順序である、すなわち有限の木の任意の無限列に、前の木が後の木の細分として含まれる組があるという定理である。より強く、整擬順序集合のラベルを付けた有限の根付き木は、最も近い共通の先祖とラベルの大小を保つ埋め込みについて整擬順序である。Nash-Williams の極小悪列の論法と Higman の補題で証明される。部分グラフの関係や一般のグラフでは成り立たない。
Kruskal の木定理(Kruskal's tree theorem)は、有限の木をどれだけたくさん並べても、ある木が後のある木の 位相的マイナー(辺を道に引き延ばした形で中に含まれるもの)になっている、という定理である。言いかえると、有限の木の全体は位相的マイナーの関係について 整擬順序 である。頂点に整擬順序集合のラベルを付けた根付き木でも同じことが成り立つ。
この定理は、有限の組合せ的対象の集合が整擬順序であることを示す定理の系列の中で、語についての Higmanの補題 と、グラフについての Robertson–Seymour のグラフマイナー定理(グラフマイナー)の間に位置する。証明は Nash-Williams による 極小悪列 の論法で、木を「根」と「根の子を根とする部分木の並び」に分け、部分木の並びに Higman の補題を使う。証明は短いが、Friedman による拡張は証明論の順序数の表記系と深く結びついている(rem-kr-friedman)。
この記事では、根付き木の埋め込みを定義し、ラベル付きの根付き木についての定理を完全に証明し、そこから木の位相的マイナーについての定理を導く。最後に、細分を許さない(部分グラフの関係にする)、木をグラフに広げる、などで結論が成り立たない例を反例の表にまとめる。
最小全域木を求める Kruskal のアルゴリズム(最小全域木)や Kruskal–Katonaの定理 とは別の結果である。グラフマイナー の記事は、整擬順序の定義と、Kruskal の木定理の主張と所在を述べている。この記事はその証明と例・反例を受け持つ。整擬順序の基本性質と、証明で使う Higman の補題は Higmanの補題 の記事で証明している。
以下、木はすべて有限とする。根付き木 $(T,r)$ について、$x$ が $y$ の先祖であることを $x\preceq y$ と書き、$x$ と $y$ の最も近い共通の先祖を $x\wedge y$ と書く(根付き木 の定理「先祖の順序による特徴づけ」と命題「最も近い共通の先祖と距離」)。$x\preceq y$ と $x\wedge y=x$ は同じことである。
集合 $Q$ の上の反射的かつ推移的な関係 $\le$(擬順序)が 整擬順序 であるとは、$Q$ の任意の無限列 $q_0,q_1,\dots$ に $i< j$ かつ $q_i\le q_j$ となる組(よい組)があることをいう。よい組をもたない無限列を 悪い列 という。
$(Q,\le)$ を擬順序集合とする。根付き木 $(T,r)$ と写像 $\ell\colon V(T)\to Q$ の組を $Q$ ラベル付き根付き木 という。$Q$ ラベル付き根付き木 $T=(T,r,\ell)$、$T'=(T',r',\ell')$ について、単射 $f\colon V(T)\to V(T')$ で、すべての頂点 $x,y$ について
$$f(x\wedge y)=f(x)\wedge f(y),\qquad \ell(x)\le\ell'(f(x))$$
となるものがあるとき、$T\le T'$ と書き、$f$ を 埋め込み という。$Q$ が 1 点のときはラベルを省き、根付き木の間の関係とみなす。
恒等写像は埋め込みで、埋め込みの合成は埋め込みなので、$\le$ は擬順序である。埋め込み $f$ は $x\preceq y$ を $f(x)\preceq f(y)$ に送り($x\wedge y=x$ から $f(x)\wedge f(y)=f(x)$)、単射なので $x\prec y$ を $f(x)\prec f(y)$ に送る。根 $r$ は $r=r\wedge y$ なので、$f(r)$ は $f$ の像のすべての頂点の先祖である。
グラフ $H$ の各辺を、端点以外で互いに交わらない道に置き換えたグラフを $H$ の 細分 という。グラフ $G$ が $H$ の細分と同型な部分グラフをもつとき、$H$ を $G$ の 位相的マイナー という。
位相的マイナーの関係は有限グラフの全体の上の擬順序である。木の位相的マイナーは森であり、連結なものは木である(連結なグラフの細分は連結で、木の部分グラフは閉路をもたない)。
根付き木 $(T,r)$ から $(T',r')$ への埋め込み $f$(ラベルなし)があれば、$T$ は $T'$ の位相的マイナーである。
$T$ の根以外の頂点 $x$ について、その親を $p$ とし、$T'$ の中で $f(p)$ と $f(x)$ を結ぶ道を $P_x$ とする。$f(p)\prec f(x)$ なので、$P_x$ は $f(p)$ から先祖の順序で上がっていく道で、内部の頂点 $w$ はすべて $f(p)\prec w\prec f(x)$ を満たす。$f(V(T))$ と道 $P_x$ たちを合わせたものが $T$ の細分であることを示すには、次の 2 つを示せばよい。
(i) $P_x$ の内部に $f(z)$($z\in V(T)$)はない。$f(p)\prec f(z)\prec f(x)$ とすると、$f(z)\wedge f(x)=f(z)$ から $f(z\wedge x)=f(z)$、単射性から $z\wedge x=z$、すなわち $z\preceq x$ である。同様に $p\preceq z$ である。$f$ は単射なので $z\ne p,x$ であり、$p\prec z\prec x$ となるが、$x$ は $p$ の子なのでこれは起こらない。
(ii) $x\ne y$ なら $P_x$ と $P_y$ の内部は交わらない。$y$ の親を $q$ とし、$w$ が両方の内部にあるとする。$w\preceq f(x)$ かつ $w\preceq f(y)$ なので $w\preceq f(x)\wedge f(y)=f(x\wedge y)$ である。$z:=x\wedge y$ とおく。$z=x$ なら $x\prec y$ なので $x\preceq q$ で、$f(q)\succeq f(x)\succeq w$ となり $w\succ f(q)$ に反する。$z=y$ のときも同様である。$z\ne x,y$ なら $z\prec x$ なので $z\preceq p$ で、$w\preceq f(z)\preceq f(p)\prec w$ となり矛盾する。
よって、$T$ の各辺 $px$ を道 $P_x$ に置き換えた $T$ の細分が、$T'$ の部分グラフとして現れる。$\square$
$(Q,\le)$ が整擬順序なら、有限の $Q$ ラベル付き根付き木の全体は、def-kr-embed の関係 $\le$ について整擬順序である。
木の位相的マイナーについての形(下の cor-kr-unrooted)は Die25 Theorem 12.2.1(p. 365)で、同書は Kruskal(1960)に帰している。同書の証明は、細分と部分木の同型で定めた根付き木の関係を使い、Higmanの補題 の有限部分集合の形(Lemma 12.1.3)から導いている。以下の証明はその論法をラベル付きの形に書き直したもので、ラベル付きの形は同書の演習 7(p. 405)が求めているものである。
証明の考え方を先に述べる。悪い列があるとして、各項がなるべく小さい悪い列 $(T_n)$ を選ぶ。$T_n$ の根を取り除いてできる部分木は $T_n$ より小さいので、それらを集めた集合は、選び方の極小性から整擬順序になる。すると Higmanの補題 により、部分木の並びも整擬順序になり、根のラベルと合わせて $(T_n)$ のよい組が作れてしまう。
$Q$ ラベル付き根付き木 $T=(T,r,\ell)$ の根の子 $c$ について、$c$ の子孫が誘導する部分木 $T_c$ に根 $c$ と $\ell$ の制限を与えたものを、$T$ の 根の部分木 という。$x,y\in V(T_c)$ について $c$ は共通の先祖なので、$T$ での $x\wedge y$ は $c$ の子孫であり、$T_c$ での最も近い共通の先祖と一致する。よって包含写像 $T_c\to T$ は埋め込みで、$T_c\le T$ である。また $|T_c|<|T|$($|\cdot|$ は頂点の個数)である。
悪い列があると仮定する。
(1) 極小悪列を選ぶ。 $T_0,\dots,T_{n-1}$ まで選ばれ、それで始まる悪い列があるとする($n=0$ では仮定による)。そのような悪い列の $n$ 番目の項として現れる木のうち、頂点の個数が最小のものを $T_n$ とする。$i< j$ なら、$T_0,\dots,T_j$ で始まる悪い列があるので $T_i\not\le T_j$ であり、$(T_n)$ は悪い列である。$T_n$ の根を $r_n$、ラベルを $\ell_n$ と書く。
(2) 根の部分木の全体は整擬順序である。 $T_n$ の根の部分木の集合を $A_n$ とし、$A:=\bigcup_nA_n$ とおく(同型な部分木も、出どころの $T_n$ と頂点が違えば別の元として数える)。$A$ の無限列 $(S^k)_{k\ge0}$ をとり、$S^k\in A_{n(k)}$ となる $n(k)$ を選ぶ。$n(k)$ が最小になる $k$ を 1 つとり $k_0$ とする。列
$$T_0,\dots,T_{n(k_0)-1},\ S^{k_0},\ S^{k_0+1},\ S^{k_0+2},\dots$$
は $T_0,\dots,T_{n(k_0)-1}$ で始まり、次の項 $S^{k_0}$ は $T_{n(k_0)}$ より頂点が少ないので、(1) の選び方から悪い列でなく、よい組をもつ。それが $(T_i,T_j)$($i< j< n(k_0)$)なら $(T_n)$ が悪いことに反する。$(T_i,S^k)$($i< n(k_0)$、$k\ge k_0$)なら $T_i\le S^k\le T_{n(k)}$ で $i< n(k_0)\le n(k)$ なので、やはり反する。よってよい組は $(S^k,S^m)$($k_0\le k< m$)の形であり、$(S^k)$ はよい列である。
(3) 根で継ぎ合わせる。 Higmanの補題 の補題「増加部分列」により、$n_0< n_1<\cdots$ で $\ell_{n_0}(r_{n_0})\le\ell_{n_1}(r_{n_1})\le\cdots$ となるものがある。各 $n$ について $A_n$ の元を何らかの順に並べた語を $w_n\in A^*$ とする。(2) と Higmanの補題 の定理「Higman の補題」により、$s< t$ で $w_{n_s}\le^*w_{n_t}$ となるものがある。$i:=n_s$、$j:=n_t$ とおくと、$r_i$ の子から $r_j$ の子への単射 $\iota$ と、各子 $c$ について埋め込み $g_c\colon T_c\to T_{\iota(c)}$ がある($T_c$ は $T_i$ の、$T_{\iota(c)}$ は $T_j$ の根の部分木)。$f\colon V(T_i)\to V(T_j)$ を $f(r_i):=r_j$、$T_c$ の上では $f:=g_c$ で定める。
・$f$ は単射である。$g_c$ の像は $T_{\iota(c)}$ に入り、$\iota$ が単射なので異なる $c$ の像は互いに交わらない根の部分木に入り、どれも $r_j$ を含まない。
・$f(x\wedge y)=f(x)\wedge f(y)$ である。$x,y$ が同じ $T_c$ にあれば、$x\wedge y$ は $T_c$ の中で計算でき、$g_c$ が保ち、$T_{\iota(c)}$ の中での最も近い共通の先祖は $T_j$ でのものと等しい。$x\in T_c$、$y\in T_d$($c\ne d$)なら $x\wedge y=r_i$ で、$f(x)$ と $f(y)$ は $r_j$ の異なる子の部分木にあるので $f(x)\wedge f(y)=r_j=f(r_i)$ である。$x=r_i$ なら両辺とも $r_j$ である。
・ラベル:$\ell_i(r_i)\le\ell_j(r_j)$ は部分列の選び方から、ほかの頂点では $g_c$ から従う。
よって $T_i\le T_j$ かつ $i< j$ となり、$(T_n)$ が悪い列であることに反する。$\square$
有限の木の全体は、位相的マイナーの関係について整擬順序である。すなわち、有限の木の任意の無限列 $T_0,T_1,\dots$ に、$i< j$ で $T_i$ が $T_j$ の位相的マイナーとなるものがある。
各 $T_n$ に任意に根を選び、$Q$ を 1 点として thm-kr-main を使うと、$i< j$ で根付き木の埋め込み $T_i\to T_j$ があるものが見つかる。lem-kr-topminor により $T_i$ は $T_j$ の位相的マイナーである。$\square$
有限の木の族 $\mathcal P$ が位相的マイナーをとる操作で閉じている($T\in\mathcal P$ で、木 $T'$ が $T$ の位相的マイナーなら $T'\in\mathcal P$)とする。このとき有限個の木 $X_1,\dots,X_k$ があって、木 $T$ が $\mathcal P$ に属することと、どの $X_i$ も $T$ の位相的マイナーでないことが同値になる。
$\mathcal P$ に属さない木のうち、その真の位相的マイナー(自身と同型でないもの)である木がすべて $\mathcal P$ に属するものを 極小 とよぶ。真の位相的マイナーは、頂点と辺の個数の和が真に小さい。極小な木のうち互いに同型でないものは、どの 2 つも位相的マイナーの関係で比べられない。$X$ が $Y$ の位相的マイナーで同型でなければ、$X\notin\mathcal P$ が $Y$ の極小性に反するからである。cor-kr-unrooted により比べられない木の無限列はないので、極小な木は同型を除いて有限個 $X_1,\dots,X_k$ である。$T\notin\mathcal P$ なら、$T$ の位相的マイナーである木で $\mathcal P$ に属さないもののうち頂点と辺の個数の和が最小のものは極小なので、ある $X_i$ と同型である。逆に $X_i$ が $T$ の位相的マイナーで $T\in\mathcal P$ なら、閉じていることから $X_i\in\mathcal P$ となり矛盾する。$\square$
たとえば次数 3 以上の頂点をもたない木(道)の族は、$K_{1,3}$ 1 つを禁止することで特徴づけられる(ex-kr-star の後半と、次数 3 以上の頂点 $v$ とその 3 つの隣接頂点が $K_{1,3}$ を作ることによる)。グラフ全体とマイナーの関係について同じ形の主張が、グラフマイナー の系「禁止マイナーの有限性」である。
$T$ を、根 $r$ に 2 つの子 $a,b$ がある木とする。$T'$ を、根 $r'$ から道 $r'\,u\,v$ が伸び、$v$ に 2 つの子 $s,t$ がある木とする。$f(r)=r'$、$f(a)=s$、$f(b)=t$ とすると $f(a)\wedge f(b)=v\ne f(r)$ なので埋め込みでない。$f(r)=v$、$f(a)=s$、$f(b)=t$ は埋め込みで、$T\le T'$ である。このように埋め込みは根を根に送るとは限らず、根の像は像全体の最も近い共通の先祖になる。
根に 3 つの子がある木 $K$ は、どの頂点の子も 2 個以下の根付き木 $B$ に埋め込めない。埋め込み $f$ があるとすると、3 つの子 $a,b,c$ の像のどの 2 つの最も近い共通の先祖も $f(\text{根})$ なので、$f(a),f(b),f(c)$ は $f(\text{根})$ の相異なる子の部分木に入り、$f(\text{根})$ は子を 3 個以上もつ。木として見ても、$K=K_{1,3}$ は次数 3 以上の頂点のない木(道)の位相的マイナーにならない。細分は次数 3 の頂点を残すからである。
語 $(a_1,\dots,a_m)\in Q^*$ を、根 $v_1$ から $v_1v_2\cdots v_m$ と伸びる道に $\ell(v_i)=a_i$ とラベルを付けた根付き木と同一視する。道の上では $x\wedge y$ は $x,y$ の浅い方なので、道から道への埋め込みは先祖の順序を保つ単射、つまり番号を狭義に増やす写像で、ラベルの条件と合わせて Higmanの補題 の順序 $\le^*$ そのものである。よって thm-kr-main は Higman の補題を含む。ただし上の証明は Higman の補題を使っているので、これは Higman の補題の別証明にはならない。
| 外す・変える条件 | 例 | 成り立たなくなること |
|---|---|---|
| 細分を許す(位相的マイナー) | 部分グラフの関係、両端に 2 本ずつ葉を付けた道 $H_n$ | 結論。$H_1,H_2,\dots$ がどの 2 つも比べられない |
| ラベルの集合 $Q$ が整擬順序 | $Q=\mathbb{N}$ に等号の順序 | 結論。1 頂点の木のラベル $0,1,2,\dots$ が悪い列 |
| 対象が木 | 一般の有限グラフと位相的マイナーの関係 | 結論。無限の反鎖がある(主張と所在のみ) |
1 行目:$n\ge1$ について、道 $v_0v_1\cdots v_n$ の $v_0$ と $v_n$ にそれぞれ新しい葉を 2 つずつ付けた木を $H_n$ とする。$H_n$ で次数が 3 以上の頂点は $v_0,v_n$ だけで、どちらも次数 3 である。$m< n$ として、$H_m$ と同型な $H_n$ の部分グラフがあるとすると、$H_m$ の次数 3 の頂点 2 つは $H_n$ の次数 3 以上の頂点、すなわち $v_0,v_n$ に移り、その間の長さ $m$ の道も $H_n$ の中の道に移る。木の中で 2 頂点を結ぶ道はただ 1 つで、$v_0$ と $v_n$ を結ぶ道の長さは $n\ne m$ なので矛盾する。$m>n$ なら $H_m$ は $H_n$ より頂点が多い。よって $(H_n)$ は部分グラフの関係で悪い列である。一方、$m\le n$ なら真ん中の道を細分すれば $H_m$ は $H_n$ の位相的マイナーで、cor-kr-unrooted とは矛盾しない。有限の木が部分グラフの関係で整擬順序でないことは Die25 第 12 章の演習 5(p. 405)である。
2 行目:1 頂点の木どうしの埋め込みはラベルの比較だけで、等号の順序では異なるラベルは比べられない。
3 行目:閉路の各辺を二重にし、新しく加えた辺をそれぞれ 1 回細分したグラフたちは、閉路の長さが違えば位相的マイナーの関係で比べられない(Die25 第 12 章の注、p. 412。同書の演習 10、p. 405 も参照)。この記事では証明しない。マイナーの関係では有限グラフの全体は整擬順序である(グラフマイナー の定理「Robertson–Seymour の定理」)。
Rat06(§2.5、p. 62)は、順序数の表記系から新しい組合せ論の結果が生まれた例として、Friedman による Kruskal の定理の拡張(拡張 Kruskal 定理)を挙げている。これは、埋め込みに「隙間」(gap)の条件を課しても有限の木が整擬順序であるという主張である。同所によれば、隙間の条件は $\Pi^1_1$ 内包公理の体系の順序数解析に使われた順序数の表記系と直接に結びついており、この原理は Robertson–Seymour のグラフマイナー定理の証明で決定的な役割を果たした。この記事では拡張の主張の詳細と証明は扱わない。逆数学 の記事は、二階算術の部分体系で定理の強さを測る枠組みを述べている。
極小悪列の論法は「悪い列があれば極小のものがある」という形の議論で、整礎な量(ここでは頂点の個数)についての帰納法と、無限列の選択を組み合わせている。木幅が有界なグラフのマイナーについての Robertson–Seymour の定理(Die25 Theorem 12.4.2、p. 371)の証明では、おおまかに言えば同じ論法を木幅の回数だけ繰り返す(同書 p. 371 の説明)。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する