Tutte–Nash-Williamsの定理(Tutte–Nash-Williams theorem)とは、有限の多重グラフが互いに辺を共有しない全域木を $k$ 本もつための必要十分条件は、頂点集合のどの分割 $\mathcal P$ についても異なる組を結ぶ辺が $k(\lvert\mathcal P\rvert-1)$ 本以上あることだ、という定理である。全域木の辺の交換を繰り返す交換列を使い、各組の中に辺素な全域木が $k$ 本あり、組を縮めたグラフの辺が $k$ 本の全域木で覆える分割を作る詰め込みと被覆の定理から導かれる。同じ定理から、辺を $k$ 個の森で覆える条件(Nash-Williams の樹化数の公式)と、$2k$ 辺連結なグラフが辺素な全域木を $k$ 本もつことが従う。
Tutte–Nash-Williamsの定理(Tutte–Nash-Williams theorem)は、有限の多重グラフ $G$ が辺を共有しない全域木を $k$ 本もつための必要十分条件を、頂点の分割で述べる定理である。頂点集合をどのように $p$ 個の組に分けても、異なる組を結ぶ辺が $k(p-1)$ 本以上あること、がその条件である。Nash-Williams(NW61)と Tutte(Tut61)がそれぞれ 1961 年に示した(Die25 Theorem 2.4.1、p. 50)。電気回路網の有効抵抗についての Nash-Williams の不等式(電気回路網と有効抵抗)とは別の定理である。
全域木は頂点の分割のどの 2 組の間も最終的にはつながなければならないので、各全域木は組をまたぐ辺を $p-1$ 本以上使う。したがって条件が必要なことはすぐ分かり、定理の中身はそれで十分だという点にある。対になる定理として、辺を $k$ 個の森で覆えるための条件(Nash-Williams、1964 年。NW64、Die25 Theorem 2.4.3、p. 51)がある。
この記事では、Bowler と Carmesin による詰め込みと被覆の定理(Die25 Theorem 2.4.4、p. 52)を全域木の交換で証明し(thm-tnw-pc)、そこから主定理(thm-tnw-main)と森による被覆の定理(thm-tnw-cover)を導く。証明の道筋は Die25 pp. 52–54 に従う。マトロイドの言葉では主定理は互いに素な基の詰め込みの特別な場合で、マトロイド和定理 の系としても得られる。
| 内容 | 場所 |
|---|---|
| 横断辺と縮約、基本閉路 | def-tnw-cross、lem-tnw-fund |
| 主定理 | thm-tnw-main |
| 交換列と詰め込みと被覆の定理 | def-tnw-chain、lem-tnw-chain、thm-tnw-pc |
| 森による被覆と樹化数 | thm-tnw-cover、cor-tnw-arboricity |
| 辺連結度による十分条件 | cor-tnw-2k |
| 例と反例 | ex-tnw-examples、ex-tnw-counter |
グラフはループと平行辺を許す有限のグラフとし、歩道・閉路・連結・木・森・全域木は 全域木 の定義「ループを許す多重グラフと基本用語」「全域木」のとおりとする。全域木はその辺集合と同一視する。$G=(V,E)$ について $n:=\lvert V\rvert$ とし、$U\subseteq V$ について $G[U]$ は頂点集合 $U$ と、両端(ループなら 1 端)が $U$ に入る辺からなるグラフ、$e(G[U])$ はその辺の数とする。
$\mathcal P$ を $V$ の分割(空でない互いに素な組 $U$ の族で合併が $V$)とする。両端が $\mathcal P$ の異なる組に入る辺を 横断辺 といい、その数を $e_G(\mathcal P)$ と書く。頂点集合を $\mathcal P$ とし、横断辺 $uv$($u\in U$、$v\in U'$)を $U$ と $U'$ を結ぶ辺とみたグラフを $G/\mathcal P$ と書く(組の中の辺は捨てる)。
$T$ を $G$ の全域木、$e\in E\setminus T$ とする。$T+e$ が含む閉路はただ 1 つで、それは $e$ を含む。これを $C_T(e)$ と書く。$f\in C_T(e)$、$f\ne e$ なら $f\in T$ であり、$T+e-f$ は全域木である。
$T$ はグラフ的マトロイドの基であり(マトロイド の命題「グラフ的マトロイド」の直後)、$T+e$ は $n$ 本の辺をもつか $e$ がループなので森でなく、従属である。グラフ的マトロイドの閉路はグラフの閉路の辺集合なので、マトロイド の補題「基本閉路」により $T+e$ の閉路はただ 1 つで $e$ を含む。$f\in C_T(e)\setminus\{e\}\subseteq T$ をとると、$(V,T+e)$ は連結で、$f$ は閉路の上にあるので 全域木 の補題「閉路上の辺を除いても連結成分は変わらない」により $(V,T+e-f)$ も連結であり、辺は $n-1$ 本なので、全域木 の命題「木の判定」により全域木である。$\square$
$k\ge1$ とする。有限のグラフ $G=(V,E)$ が互いに辺を共有しない全域木を $k$ 本もつための必要十分条件は、$V$ のすべての分割 $\mathcal P$ について
$$
e_G(\mathcal P)\ge k\bigl(\lvert\mathcal P\rvert-1\bigr)
$$
が成り立つことである。
必要性を示す。全域木 $T$ と分割 $\mathcal P$ をとる。$T$ の横断辺を $G/\mathcal P$ の辺とみると、$T$ の歩道から組の中の辺を除いたものは $G/\mathcal P$ の歩道になるので、$T$ の横断辺は $\mathcal P$ の上の連結な全域部分グラフをなし、全域木 の系「全域木の辺の本数」の直後の注意により $\lvert\mathcal P\rvert-1$ 本以上ある。辺素な $k$ 本の全域木はこれを別々の辺で満たすので、$e_G(\mathcal P)\ge k(\lvert\mathcal P\rvert-1)$ である。$\square$
十分性は次節の thm-tnw-pc から導く(prf-tnw-main)。条件は、分割のどの組も $G$ で連結になる分割($G$ の縮約で得られるグラフ)だけで確かめれば足りる。組 $U$ を $G[U]$ の連結成分に細分すると、組の数は増え、横断辺の数は変わらない(異なる成分を結ぶ辺はない)ので、細分した分割で条件が成り立てばもとの分割でも成り立つからである(Die25 p. 51 の注意)。
以下、$G$ は連結とし、$\mathcal T=(T_1,\dots,T_k)$ を全域木の族(辺の共有を許す)とする。$E(\mathcal T):=T_1\cup\dots\cup T_k$ とおく。
辺の列 $(e_0,e_1,\dots,e_m)$($m\ge0$)が $\mathcal T$ についての 交換列 であるとは、$e_m\notin E(\mathcal T)$ であり、各 $i< m$ について添字 $j(i)$ があって、$e_{i+1}\notin T_{j(i)}$ かつ $e_i\in C_{T_{j(i)}}(e_{i+1})\setminus\{e_{i+1}\}$ となることをいう。このとき $e_0$ は交換列を 始める という。
$e_i\in C_{T_{j(i)}}(e_{i+1})\setminus\{e_{i+1}\}$ なので $e_i\in T_{j(i)}$ であり、lem-tnw-fund により $T_{j(i)}$ の $e_i$ を $e_{i+1}$ に取り替えても全域木である。$E(\mathcal T)$ に入らない辺は、長さ $0$ の交換列 $(e_0)$ を始める。
辺 $e_0$ が $\mathcal T$ についての交換列を始め、$\mathcal T$ の 2 本以上の木に含まれるとする。このとき全域木の族 $\mathcal T'=(T'_1,\dots,T'_k)$ で $E(\mathcal T)\subsetneq E(\mathcal T')$ となるものがある。
$e_0$ から始まる交換列のうち $m$ が最小のもの $(e_0,\dots,e_m)$ をとる。$e_0\in E(\mathcal T)$ なので $m\ge1$ である。最小性から次が成り立つ。
$G=(V,E)$ を連結な有限のグラフ、$k\ge1$ とする。$V$ の分割 $\mathcal P$ で、次の 2 つをみたすものがある。
$G$ は連結なので全域木があり(全域木 の定理「全域木の存在」)、全域木の族は有限個である。$E(\mathcal T)$ が包含について極大になる族 $\mathcal T=(T_1,\dots,T_k)$ をとる。$D$ を、$\mathcal T$ についての交換列を始める辺の集合とする。$E\setminus E(\mathcal T)\subseteq D$ であり、極大性と lem-tnw-chain により、$D$ の辺は $\mathcal T$ の 2 本以上の木には含まれない。$\mathcal P$ を、全域部分グラフ $(V,D)$ の連結成分の頂点集合の族とする。$D$ の辺は横断辺でない。
1 の証明.$U\in\mathcal P$ とし、$D_U$ を両端が $U$ に入る $D$ の辺の集合、$S_j:=T_j\cap D_U$ とおく。$D$ の辺は 2 本以上の木に含まれないので $S_1,\dots,S_k$ は互いに素であり、$S_j\subseteq T_j$ なので $(U,S_j)$ は閉路をもたない。$(U,D_U)$ は連結なので、$(U,S_j)$ が連結であることを示すには、$f\in D_U$ の両端 $u,u'$ が $S_j$ の道で結ばれることを示せばよい。$f\in T_j$ なら $f\in S_j$ である。$f\notin T_j$ なら、$C_{T_j}(f)$ から $f$ を除いた部分は $T_j$ の中の $u$ から $u'$ への道である($f$ がループなら $u=u'$ で示すことはない)。この道の辺 $g$ は $g\in C_{T_j}(f)\setminus\{f\}$ をみたすので、$f$ から始まる交換列の前に $g$ を付けた列は交換列であり、$g\in D$ である。道の頂点は $u$ と $D$ の辺で結ばれるので $U$ に入り、$g\in D_U\cap T_j=S_j$ である。よって $(U,S_j)$ は連結で、$G[U]$ の全域木である。
2 の証明.$T_j$ の横断辺の集合を $T'_j$ とし、$G/\mathcal P$ の辺の集合とみる。$T_j$ の組 $U$ の中の辺は $U$ の上の森をなすので $\lvert U\rvert-1$ 本以下で(全域木 の命題「木と森の辺の本数」)、1 の $S_j$ を含むのでちょうど $\lvert U\rvert-1$ 本である。よって $\lvert T'_j\rvert=(n-1)-\sum_U(\lvert U\rvert-1)=\lvert\mathcal P\rvert-1$ である。$T_j$ は連結なので、必要性の証明と同じく $(\mathcal P,T'_j)$ は連結であり、全域木 の命題「木の判定」により $G/\mathcal P$ の全域木である。横断辺は $D$ に入らず、$E\setminus E(\mathcal T)\subseteq D$ なので、どの横断辺もある $T_j$ に、したがって $T'_j$ に含まれる。$\square$
必要性は thm-tnw-main の直後に示した。十分性を示す。$n=1$ なら空集合が $k$ 本の辺素な全域木である。$n\ge2$ とする。$G$ が連結でなければ、連結成分による分割 $\mathcal P$ は $\lvert\mathcal P\rvert\ge2$、$e_G(\mathcal P)=0$ で条件に反するので、$G$ は連結である。
thm-tnw-pc の分割 $\mathcal P$ をとる。$G/\mathcal P$ の辺は $k$ 本の全域木 $T'_1,\dots,T'_k$ の合併で覆われ、各 $T'_j$ は $\lvert\mathcal P\rvert-1$ 本の辺をもつので
$$
k\bigl(\lvert\mathcal P\rvert-1\bigr)\le e_G(\mathcal P)\le\sum_j\lvert T'_j\rvert=k\bigl(\lvert\mathcal P\rvert-1\bigr)
$$
である。等号が成り立つので $T'_1,\dots,T'_k$ は互いに素である。各組 $U$ について、thm-tnw-pc の 1 の辺素な全域木を $S^U_1,\dots,S^U_k$ とし、$F_j:=T'_j\cup\bigcup_{U\in\mathcal P}S^U_j$ とおく。$(V,F_j)$ は、各組の中が $S^U_j$ で連結で、組どうしが $T'_j$ で連結なので連結であり、辺は $(\lvert\mathcal P\rvert-1)+\sum_U(\lvert U\rvert-1)=n-1$ 本なので、全域木 の命題「木の判定」により全域木である。$F_1,\dots,F_k$ は、組の中の部分も横断辺の部分も互いに素なので、辺素である。$\square$
$k\ge1$ とする。有限のグラフ $G=(V,E)$ の辺集合が $k$ 個の森の合併になるための必要十分条件は、空でないすべての $U\subseteq V$ について $e(G[U])\le k(\lvert U\rvert-1)$ が成り立つことである。
必要性:森は $U$ の中の辺を $\lvert U\rvert-1$ 本以下しか含まない(全域木 の命題「木と森の辺の本数」)。
十分性:$U$ が 1 点のとき条件は $e(G[U])=0$ なので、$G$ にループはない。$G$ の連結成分の頂点集合 $W$ を 1 つとり、連結なグラフ $G[W]$ に thm-tnw-pc を当てて分割 $\mathcal P$ を得る。各組 $U$ について、1 の辺素な全域木 $S^U_1,\dots,S^U_k$ は $G[U]$ の辺をあわせて $k(\lvert U\rvert-1)$ 本使い、条件から $e(G[U])\le k(\lvert U\rvert-1)$ なので、$G[U]$ の辺はすべてどれかの $S^U_j$ に入る。2 の全域木 $T'_j$ は $G[W]/\mathcal P$ の辺、すなわち $G[W]$ の横断辺をすべて覆う。$F^W_j:=T'_j\cup\bigcup_US^U_j$ は prf-tnw-main と同じ理由で $G[W]$ の全域木であり、$F^W_1,\dots,F^W_k$ は $G[W]$ の辺を覆う。成分ごとの $F^W_j$ を $W$ にわたって合わせた $k$ 個の森が $E$ を覆う。$\square$
辺を覆うのに要る森の最小の個数をグラフの 樹化数(arboricity)という。
ループのない有限のグラフ $G$ が辺を 1 本以上もつとき、その樹化数は
$$
\max_{U\subseteq V,\ \lvert U\rvert\ge2}\Bigl\lceil\frac{e(G[U])}{\lvert U\rvert-1}\Bigr\rceil
$$
に等しい。
ループがないので 1 点の $U$ では条件はつねに成り立つ。$k$ 個の森で覆えることは、thm-tnw-cover により、$\lvert U\rvert\ge2$ のすべての $U$ で $k\ge e(G[U])/(\lvert U\rvert-1)$、すなわち $k$ が上の最大値以上であることと同値である。$\square$
$\lvert V\rvert\ge2$ のグラフ $G$ が $k$ 辺連結 であるとは、空でない真部分集合 $U\subsetneq V$ のどれについても、$U$ と $V\setminus U$ を結ぶ辺が $k$ 本以上あることをいう。辺を $k-1$ 本以下除いても連結であることと同じである。
$2k$ 辺連結なグラフは、辺素な全域木を $k$ 本もつ。
分割 $\mathcal P$ が $\lvert\mathcal P\rvert\ge2$ をみたすとき、各組 $U$ からほかの組へ出る辺は $2k$ 本以上ある。これを組にわたって足すと、各横断辺はその両端の 2 組で 1 回ずつ数えられるので、$2e_G(\mathcal P)\ge2k\lvert\mathcal P\rvert$、すなわち $e_G(\mathcal P)\ge k\lvert\mathcal P\rvert> k(\lvert\mathcal P\rvert-1)$ である。$\lvert\mathcal P\rvert=1$ なら条件は自明なので、thm-tnw-main から従う。$\square$
$k$ 辺連結であることは $k$ 本の辺素な全域木の存在に必要だが(全域木が $k$ 本あれば、どの $U$ についても各木が $U$ と $V\setminus U$ を結ぶ辺を 1 本以上含む)、十分ではない。$k=2$ では $2k$ を $2k-1$ に下げることもできない(ex-tnw-examples の 2、表の 3 行目。$k=1$ では連結であることだけで足りる)。Die25 Corollary 2.4.2(p. 50)はこの系を述べる。
$K_{3,3}$ の左右の頂点集合を $L,R$ とし、$U$ が $L$ の $a$ 個と $R$ の $b$ 個の頂点を含むとする($(a,b)\ne(0,0),(3,3)$)。$U$ と外を結ぶ辺は、$U\cap L$ と $R\setminus U$ の間の $a(3-b)$ 本と、$U\cap R$ と $L\setminus U$ の間の $b(3-a)$ 本で、合計 $3a+3b-2ab$ 本である。$0\le a,b\le3$ の 14 通りでこの値は $3$ 以上である($(1,0)$、$(3,2)$ などで $3$)。実際、$3a+3b-2ab=\tfrac92-2(a-\tfrac32)(b-\tfrac32)$ で、$(a-\tfrac32)(b-\tfrac32)\le\tfrac94$ の等号は $(a,b)=(0,0),(3,3)$ だけなので、ほかの組では $(a-\tfrac32)(b-\tfrac32)\le\tfrac34$、値は $3$ 以上である。
| 外した仮定・替えた条件 | 反例 | 成り立たなくなる結論 |
|---|---|---|
| すべての分割で条件を課す → 1 点ずつの分割だけ(thm-tnw-main) | $K_5$ の頂点と新しい頂点 $w$ を辺 $p$ で結んだグラフ(6 頂点、11 辺)、$k=2$ | $11\ge2\cdot5$ だが、辺素な全域木は 2 本ない |
| すべての分割で条件を課す → 2 組の分割だけ(thm-tnw-main) | $C_4$、$k=2$ | どの 2 組の分割も横断辺が 2 本以上あるが、辺素な全域木は 2 本ない |
| $2k$ 辺連結 → $2k-1$ 辺連結(cor-tnw-2k) | $K_{3,3}$、$k=2$ | 3 辺連結だが、辺素な全域木は 2 本ない |
| すべての $U$ で条件を課す → $U=V$ だけ(thm-tnw-cover) | $K_5$ の頂点 $v$ から道 $v\,w_1\,w_2$ を伸ばしたグラフ(7 頂点、12 辺)、$k=2$ | $12\le2\cdot6$ だが、辺は 2 つの森で覆えない |
どの行も、右の欄の主張を直接確かめられる。
1 行目:$p$ を除くと $w$ が孤立するので、$p$ はどの全域木にも含まれ、2 本の全域木は $p$ を共有する。分割 $\{V(K_5),\{w\}\}$ では横断辺は $p$ だけで、$1< 2(2-1)$ である。
2 行目:$C_4$ の頂点を 2 組に分けると、閉路を一周する間に組をまたぐ回数は偶数で 0 でないので、横断辺は 2 本以上ある。一方、辺は 4 本で $2(4-1)=6$ 本に足りない。
3 行目:ex-tnw-examples の 2 による。
4 行目:森は $K_5$ の 5 頂点の上で辺を 4 本以下しか含まないので、2 つの森は $K_5$ の 10 辺を覆えない。$U=V(K_5)$ で $10> 2\cdot4$ と条件が満たされていない。
マトロイドの言葉では、thm-tnw-main はグラフ的マトロイドが互いに素な基を $k$ 個もつ条件であり、thm-tnw-cover は台集合を $k$ 個の独立集合に分ける条件である。一般のマトロイドでの同じ形の定理(Edmonds の詰め込みと被覆の定理)は マトロイド和定理 の系にある。無限グラフでは、通常の全域木についてはこの定理は成り立たず、端を加えた位相的な全域木で類似が成り立つ(Die25 p. 51)。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する