全域木

同義語:spanning tree

概要

全域木(spanning tree)とは、グラフのすべての頂点を含み、もとのグラフの辺の一部からなる木のことである。全域木をもつことと連結であることは同値で、$n$ 頂点のグラフの全域木の辺はちょうど $n-1$ 本である。辺に重みがあるとき、Kruskal 法は重みの最小な全域木を与える。全域木の個数 $\tau(G)$ はループでない辺 $e$ について $\tau(G)=\tau(G-e)+\tau(G/e)$ を満たし、ループのない連結なグラフでは Laplace 行列の小行列式で表される(行列木定理)。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: グラフ, 木, 連結グラフ, 部分グラフ

定義

4 つの町を結ぶ道路の候補が 6 本(どの 2 町の間にも 1 本)あり、そのうち何本かを整備して、どの町からどの町へも行けるようにしたい。無駄を省くなら、輪(閉路)のない、ちょうど 3 本の道路を選べばよい。そのような選び方は 16 通りある。道路の候補が町 1–2–3–4–1 の輪の 4 本だけなら、どれか 1 本を整備しない選び方の 4 通りしかない。このように、グラフのすべての頂点を残し、辺をいくつか選んで作った木を全域木という。全域木は、ネットワークを最少の辺でつなぐ方法であり、辺に費用が付いていれば、費用が最小の全域木を探す問題(最小全域木問題)になる。
頂点が 5 個、辺が 7 本の連結なグラフでは、全域木の辺はちょうど 4 本なので、どの全域木も 3 本の辺を除いて得られる(cor-spt-edge-count)。たとえば 5 角形 $0,1,2,3,4$ に対角線 $02$、$03$ を加えたグラフの全域木は 21 個ある(thm-spt-matrix-tree で計算できる)。
本記事では、平行辺やループを許すグラフも扱う。辺の縮約(def-spt-contraction)で平行辺やループが生じるためである。

ループを許す多重グラフと基本用語

有限集合 $V\neq\emptyset$、有限集合 $E$、各辺 $e\in E$ に端点の集合 $\partial(e)$($V$ の 1 元または 2 元の部分集合)を対応させる写像 $\partial$ の組 $G=(V,E,\partial)$ を、本記事ではグラフとよぶ。$\partial(e)$ が 1 元集合の辺をループ、$\partial(e)=\partial(e')$ となる相異なる辺 $e,e'$ を平行辺という。ループも平行辺もないグラフは、グラフ の記事の単純グラフと同じものである。

  1. 頂点と辺の交互列 $v_0,e_1,v_1,\dots,e_\ell,v_\ell$ で $\partial(e_i)=\{v_{i-1},v_i\}$ を満たすものを $v_0$ から $v_\ell$ への長さ $\ell$ の歩道という。頂点 $v_0,\dots,v_\ell$ が相異なる歩道を道という。
  2. $\ell\geq1$ の歩道で、$v_\ell=v_0$ であり、辺 $e_1,\dots,e_\ell$ が相異なり、頂点 $v_0,\dots,v_{\ell-1}$ が相異なるものを閉路という。ループ 1 本は長さ $1$ の閉路、平行辺 $e\neq e'$ は長さ $2$ の閉路 $u,e,v,e',u$ を作る。
  3. どの 2 頂点も歩道で結ばれるとき、$G$ は連結であるという。歩道で結ばれるという関係は同値関係であり、その同値類(に含まれる頂点と、それらを結ぶ辺)を連結成分という。
  4. 閉路をもたない連結なグラフを木、閉路をもたないグラフを森という。

歩道 $u\to v$ から、同じ頂点が 2 度現れる部分を切り取ることを繰り返すと、$u$ から $v$ への道が得られる。したがって「歩道で結ばれる」と「道で結ばれる」は同じことである。木はループも平行辺ももたない(それらは閉路だから)ので、本記事の木は 木 の記事の木(連結で閉路をもたない有限単純グラフ)と同じものである。

全域木

グラフ $G=(V,E,\partial)$ と辺の部分集合 $F\subset E$ に対し、頂点集合 $V$ と辺集合 $F$(端点は $\partial$ の制限)からなるグラフを $G$ の全域部分グラフといい、$(V,F)$ と書く。全域部分グラフ $(V,F)$ が木であるとき、これを $G$ の全域木(spanning tree)という。$G$ の全域木の個数を $\tau(G)$ と書く。

全域木は頂点をすべて含むことが要点で、頂点の一部だけを含む木(部分グラフ)は全域木ではない。全域木は辺集合 $F$ で決まるので、「$F$ は全域木である」ともいう。平行辺 $e\neq e'$ は区別して数えるので、$e$ を含む全域木と $e'$ を含む全域木は別のものである。この定義は 部分グラフ の記事の例「全域木の例」と同じもので、Lev Definition 2.2.6(p. 122)、Bog §2.3.4(p. 45)、Sta13 第 9 章(平行辺を区別して数える)にある。

直観

全域木は、グラフの連結性を保ったまま辺を削れるだけ削ったもの、あるいは閉路を作らないように辺を足せるだけ足したものである。閉路の上の辺は 1 本除いても連結性が失われない(lem-spt-cycle-edge)ので、連結なグラフから閉路の辺を 1 本ずつ除いていけば、最後に全域木が残る。どの全域木も辺はちょうど「頂点数 $-1$」本で、除いた辺の本数「辺数 $-$ 頂点数 $+1$」は、どの全域木を選んでもグラフだけで決まる。
全域木は、グラフをたどるための骨組みでもある。全域木の中では 2 頂点を結ぶ道がただ 1 つなので、道順が一意に決まる。辺に費用が付いていれば、費用の安い辺から閉路を作らないように貪欲に選ぶだけで、費用が最小の全域木が得られる(最小全域木 の定理「Kruskal 法の正しさ」)。

例と反例

完全グラフと閉路グラフ

4 頂点の完全グラフ $K_4$ の全域木は $16=4^{4-2}$ 個ある。一般に $K_n$ の全域木の個数は $n^{n-2}$ である(Cayleyの公式 の記事の系「完全グラフの全域木と根付き木」)。4 頂点の閉路グラフ $C_4$(辺 $12,23,34,41$)の全域木は、4 本の辺から 1 本を除いた 4 個である。3 本を選ぶと閉路が残らず 4 頂点を結ぶからである。$n$ 頂点の木 $T$ 自身の全域木は $T$ だけである($T$ の辺 $n-1$ 本から 1 本でも除くと $n-1$ 本未満になり、cor-spt-edge-count に反する)。

平行辺とループ

2 頂点 $u,v$ を 3 本の平行辺 $a,b,c$ で結んだグラフの全域木は $\{a\}$、$\{b\}$、$\{c\}$ の 3 個である。平行辺は区別して数えるので、全域木の「形」は 1 種類でも個数は 3 である。これにループを何本加えても全域木の個数は変わらない。ループは長さ $1$ の閉路なので、全域木に含まれることはないからである。

反例:連結でないグラフ

頂点 $1,2,3,4$ と辺 $12$、$34$ だけからなるグラフには全域木がない。全域木は連結なので、その中の $1$ から $3$ への歩道はもとのグラフの歩道でもあるが、もとのグラフで $1$ と $3$ は結ばれていないからである。このグラフは「頂点をすべて含み、閉路をもたない全域部分グラフ」(たとえば辺集合 $\{12,34\}$ 自身)をもつが、それは連結という性質を満たさない。$\{12,34\}$ は 2 つの木からなる全域的な森(全域森)である。一般に、全域木をもつことと連結であることは同値である(thm-spt-existence)。

性質

以下、$G=(V,E,\partial)$ を def-spt-graph の意味のグラフとし、$n:=|V|$、$m:=|E|$ とする。

全域木の存在

閉路上の辺を除いても連結成分は変わらない

辺 $e$ が $G$ のある閉路 $C$ に含まれるならば、$G$ で歩道で結ばれる 2 頂点は、全域部分グラフ $(V,E\setminus\{e\})$ でも歩道で結ばれる。特に $G$ が連結なら $(V,E\setminus\{e\})$ も連結である。

閉路の残りで迂回する

$C$ を $u=c_0,e,c_1,f_2,c_2,\dots,f_\ell,c_\ell=u$($e$ を最初の辺とし、$\partial(e)=\{c_0,c_1\}$)と書く。$\ell=1$($e$ がループ)なら、歩道の中の「$c_0,e,c_0$」の部分を $c_0$ に置き換えればよい。$\ell\geq2$ なら、$c_1,f_2,c_2,\dots,f_\ell,c_0$ は $e$ を使わない $c_1$ から $c_0$ への歩道であり(閉路の辺は相異なる)、その逆順は $c_0$ から $c_1$ への歩道である。$G$ の歩道の中で $e$ を通る部分「$c_0,e,c_1$」または「$c_1,e,c_0$」をこれらの歩道に置き換えれば、同じ端点をもち $e$ を使わない歩道が得られる。

全域木の存在

$G$ が全域木をもつための必要十分条件は、$G$ が連結であることである。

連結性を保つ最小の辺集合をとる

全域木 $(V,F)$ があれば、その中の歩道は $G$ の歩道でもあり、全域木は連結なので $G$ も連結である。
逆に $G$ が連結であるとする。$(V,F)$ が連結となる $F\subset E$ 全体は $F=E$ を含むので空でなく、有限なので、その中で元の個数が最小のもの $F_0$ をとる。$(V,F_0)$ が閉路をもてば、その閉路上の辺 $e$ を除いた $(V,F_0\setminus\{e\})$ は lem-spt-cycle-edge により連結であり、$F_0$ の最小性に反する。よって $(V,F_0)$ は閉路をもたない連結なグラフ、すなわち $G$ の全域木である。

この証明は、「閉路が残っている限り、閉路上の辺を 1 本除く」という手順が必ず全域木で止まることを述べている。辺は有限個なので手順は有限回で終わり、各段階で連結性は保たれ(lem-spt-cycle-edge)、終わったときには閉路がない。Lev Theorem 2.2.7(p. 122)はこの手順を証明として与え、閉路を作らないように辺を加えていく逆向きの手順にも触れている。Bog Problem 117(p. 46)は両方の向きの証明を問うている。木 の記事は、連結グラフが全域木をもつことの証明を本記事に委ねている。

辺の本数

木と森の辺の本数

$n$ 頂点の木の辺はちょうど $n-1$ 本である。より一般に、$n$ 頂点の森で連結成分が $c$ 個のものの辺はちょうど $n-c$ 本である。

葉を 1 枚ずつ除く

木はループも平行辺ももたないので、Cayleyの公式 の記事の補題「葉の存在と葉の付け外し」が使える。$n$ についての帰納法で示す。$n=1$ なら辺はループになるので辺は $0$ 本である。$n\geq2$ なら、同補題の 1 により木 $T$ は葉(次数 $1$ の頂点)$\ell$ をもち、同補題の 2 により $\ell$ とそれに接続するただ 1 本の辺を除いた $T-\ell$ は $n-1$ 頂点の木である。帰納法の仮定により $T-\ell$ の辺は $n-2$ 本なので、$T$ の辺は $n-1$ 本である。
森の各連結成分は連結で閉路をもたないので木であり、どの辺も端点を含むただ 1 つの連結成分に属する。成分の頂点数を $n_1,\dots,n_c$ とすると、辺の本数は $\sum_i(n_i-1)=n-c$ である。

木の辺の本数は Lev Proposition 2.2.5(p. 121)に、森の場合は KT17 Proposition 12.3(p. 240、証明は演習)にある。

全域木の辺の本数

$G$ が連結ならば、$G$ のどの全域木も辺をちょうど $n-1$ 本もつ。したがって全域木は、$G$ から辺をちょうど $m-n+1$ 本除いて得られる。

木の辺の本数による

全域木は $n$ 頂点の木なので、prop-spt-tree-edges により辺は $n-1$ 本であり、除いた辺は $m-(n-1)$ 本である。

冒頭の 5 頂点 7 辺のグラフでは $7-5+1=3$ 本を除く。連結なグラフは辺を $n-1$ 本以上もつ(全域木をもつので)ことも、ここから分かる。

木の判定

$n$ 頂点のグラフ $G$ について、次の 3 条件は同値である。

  1. $G$ は木である。
  2. $G$ は連結で、辺を $n-1$ 本もつ。
  3. $G$ は閉路をもたず、辺を $n-1$ 本もつ。
全域木と森の辺の本数から

1 ならば 2 と 3 が成り立つことは prop-spt-tree-edges による。2 を仮定する。thm-spt-existence により $G$ は全域木 $(V,F)$ をもち、cor-spt-edge-count により $|F|=n-1=|E|$ なので $F=E$ であり、$G$ 自身が木である。3 を仮定する。$G$ は森なので、連結成分の個数を $c$ とすると prop-spt-tree-edges により辺は $n-c$ 本である。これが $n-1$ に等しいので $c=1$ であり、$G$ は連結、したがって木である。

この同値は Sta13 Proposition 9.1(同書は平行辺を許しループを許さないグラフで述べ、証明は演習としている)にある。上の証明はループがあっても通る(ループは閉路なので、2・3 のどちらの仮定のもとでも、最終的に木であることからループがないことが分かる)。

辺を加えても閉路ができない条件

$(V,F)$ を閉路をもたない全域部分グラフとし、$e\in E\setminus F$ とする。$(V,F\cup\{e\})$ が閉路をもたないための必要十分条件は、$e$ がループでなく、$e$ の 2 つの端点が $(V,F)$ の異なる連結成分に属することである。このとき $(V,F\cup\{e\})$ の連結成分は、$e$ の端点を含む 2 つの成分を合わせたものと、残りの成分である。

閉路は必ず $e$ を通る

$e$ がループなら、それ自身が閉路である。$\partial(e)=\{x,y\}$($x\neq y$)とする。$x$ と $y$ が $(V,F)$ の同じ成分にあれば、$F$ の中の $x$ から $y$ への道 $P$ に $e$ を加えると、$e\notin F$ なので辺が相異なり、閉路になる。逆に $(V,F\cup\{e\})$ に閉路 $C$ があれば、$(V,F)$ は閉路をもたないので $C$ は $e$ を含み、$C$ から $e$ を除いた部分は $F$ の辺だけを使う $y$ から $x$ への歩道なので、$x,y$ は同じ成分に属する。後半は、$e$ を加えると $x$ の成分と $y$ の成分の頂点どうしが $e$ を経由して結ばれ、ほかの成分どうしの結ばれ方は変わらないことによる。

最小全域木と Kruskal 法

$G$ を連結なグラフとし、各辺 $e$ に実数の重み $w(e)$ が与えられているとする。辺の集合 $F$ の重みを $w(F):=\sum_{e\in F}w(e)$ と定め、重みが最小の全域木を最小全域木(最小全域木)という。全域木は有限個で、thm-spt-existence により 1 つ以上あるので、最小全域木は必ず存在する。
最小全域木は、辺を重みの小さい順(重みの等しい辺の順は任意)に並べ、閉路ができない限り採用していく手順で求まる。これを Kruskal 法という。採用するかどうかは、lem-spt-add-edge により「辺がループでなく、その両端点がそれまでに採用した辺の森の異なる連結成分に属するか」で判定でき、採用した辺はつねに森をなす。この手順の出力が最小全域木であることは 最小全域木 の定理「Kruskal 法の正しさ」で、辺の重みがすべて相異なれば最小全域木がただ 1 つであることは同記事の系「重みが相異なるときの一意性」で証明されている。頂点を 1 つずつ増やしながら、今の木とその外を結ぶ最も軽い辺を加える Prim 法も最小全域木を与える(同記事の定理「Prim 法の正しさ」)。
たとえば頂点 $a,b,c,d$ と、辺 $ab$(重み $1$)、$bc$($2$)、$ac$($3$)、$cd$($4$)、$bd$($5$)、$ad$($6$)からなるグラフ($K_4$ に重みを付けたもの)では、Kruskal 法は $ab$、$bc$ を採用し、$a,b,c$ の閉路を作る $ac$ を捨て、$cd$ を採用する。残りの $bd$、$ad$ はどちらも閉路を作るので、出力は重み $1+2+4=7$ の全域木 $\{ab,bc,cd\}$ である。重みが等しい辺があると、最小全域木は一意とは限らない。三角形の 3 辺の重みをすべて $1$ にすると、3 個の全域木はどれも重み $2$ で、すべてが最小全域木である(同記事の例「反例:最小全域木は一意とは限らない」)。

削除と縮約の漸化式

辺の削除と縮約

$e\in E$ とする。辺 $e$ だけを除いたグラフ $(V,E\setminus\{e\},\partial)$ を $G-e$ と書き、$e$ の削除という。$e$ がループでなく $\partial(e)=\{u,v\}$ のとき、$u$ と $v$ を 1 つの新しい頂点 $z$ にまとめ、$e$ を除いたグラフ $G/e$ を $e$ の縮約という。すなわち $G/e$ の頂点集合は $(V\setminus\{u,v\})\cup\{z\}$、辺集合は $E\setminus\{e\}$ であり、各辺の端点は $\partial$ の値の中の $u$、$v$ を $z$ に置き換えたものとする。

縮約では、$u$ と $v$ を結んでいた $e$ 以外の辺は $z$ におけるループになり、$u$ と $v$ の両方に隣接していた頂点 $x$ への 2 本の辺は $z$ と $x$ を結ぶ平行辺になる。単純グラフから出発しても縮約で平行辺やループが生じるので、本記事はこれらを許すグラフを扱っている。この操作は Bog §2.3.6(p. 47)にある。

削除と縮約の漸化式

$e$ が $G$ のループでない辺ならば
$$ \tau(G)=\tau(G-e)+\tau(G/e) $$
である。

$e$ を含むかどうかで分ける

$\partial(e)=\{u,v\}$ とし、$G$ の全域木を、$e$ を含まないものと含むものに分ける。
($e$ を含まない全域木)$F\subset E\setminus\{e\}$ について、$(V,F)$ が $G$ の全域木であることと $G-e$ の全域木であることは同じことである(頂点集合も端点も同じ)。よってその個数は $\tau(G-e)$ である。
($e$ を含む全域木)$G/e$ の頂点集合を $V'$ とし($|V'|=n-1$)、$e$ を含む $G$ の全域木 $F$ に $F\setminus\{e\}$ を対応させる。これが $G/e$ の全域木の全体への全単射であることを示す。
$F$ を $e$ を含む $G$ の全域木とする。$F$ は $e$ 以外に $u,v$ を結ぶ辺を含まない(含めば $e$ と長さ $2$ の閉路を作る)ので、$F\setminus\{e\}$ は $G/e$ でループを含まない。$(V,F)$ の歩道で頂点 $u,v$ を $z$ に置き換え、辺 $e$ を通る部分「$u,e,v$」「$v,e,u$」を $z$ に縮めると、$(V',F\setminus\{e\})$ の歩道になるので、$(V',F\setminus\{e\})$ は連結である。辺の本数は $(n-1)-1=n-2=|V'|-1$ なので、prop-spt-tree-criterion により $G/e$ の全域木である。
逆に $S\subset E\setminus\{e\}$ を $G/e$ の全域木とする。木はループを含まないので、$S$ は $G$ で $u,v$ を結ぶ辺を含まない。$(V,S\cup\{e\})$ が連結であることを示す。$(V',S)$ の歩道 $x_0,f_1,x_1,\dots,f_\ell,x_\ell$ をとり、各辺 $f_i$ の $G$ での端点を使って、$x_i=z$ である頂点を $u$ か $v$ に戻す。すると隣り合う辺 $f_i$、$f_{i+1}$ が $z$ で接続していた箇所では、$f_i$ の端点と $f_{i+1}$ の端点が $u$ と $v$ に分かれることがあるが、その間に辺 $e$ をはさめば $G$ の歩道になる。$G$ の 2 頂点 $x,y$ をとり、$u,v$ なら $z$ に置き換えた $V'$ の頂点を結ぶ $(V',S)$ の歩道をこのように戻すと、両端は $x$ か($x\in\{u,v\}$ のとき)$u,v$ のどちらかになり、$y$ についても同様である。端が目的の頂点でなければ、さらに $e$ を 1 回通って $u$ と $v$ を行き来すればよい。よって $(V,S\cup\{e\})$ は連結である。辺の本数は $(n-2)+1=n-1$ なので、prop-spt-tree-criterion により $G$ の全域木である。
2 つの対応 $F\mapsto F\setminus\{e\}$ と $S\mapsto S\cup\{e\}$ は互いに逆なので、$e$ を含む全域木の個数は $\tau(G/e)$ である。2 つの場合を合わせて主張を得る。

Bog Problem 119(p. 48)はこの漸化式を導く問題である。$K_4$ で確かめる。辺 $e=12$ について、$K_4-e$ は 4 頂点 5 辺のグラフで全域木は $8$ 個、$K_4/e$ は頂点 $z,3,4$ で $z3$、$z4$ がそれぞれ 2 本の平行辺、$34$ が 1 本のグラフで、全域木は $\{z3,z4\}$ 型が $2\cdot2=4$ 個、$\{z3,34\}$ 型と $\{z4,34\}$ 型が $2$ 個ずつの計 $8$ 個である。$8+8=16=\tau(K_4)$ となる。ループ $e$ では縮約が定義されず、$\tau(G)=\tau(G-e)$ である(ループはどの全域木にも含まれない)。
この漸化式を、橋とループでの振る舞いも含めて 2 変数の多項式として記録したものが Tutte多項式 であり、連結な $G$ では 2 つの変数にともに $1$ を代入した値が $\tau(G)$ に等しい。

行列木定理

行列木定理

$G$ をループをもたない連結なグラフとし、頂点を $v_1,\dots,v_n$ とする。$n\times n$ 行列 $L=(L_{ij})$ を
$$ L_{ii}:=\deg(v_i),\qquad L_{ij}:=-(\text{$v_i$ と $v_j$ を結ぶ辺の本数})\quad(i\neq j) $$
で定め($\deg(v_i)$ は $v_i$ に接続する辺の本数)、$L$ から第 $i$ 行と第 $i$ 列を除いた行列を $L_0$ とする。このとき、どの $i$ についても
$$ \det L_0=\tau(G) $$
である。

行列木定理の出典と例

$L$ を $G$ の Laplace 行列(ラプラシアン行列)という。この定理は Sta13 Theorem 9.8($L$ の定義は Definition 9.5 (b))にあり、同書は行列式の Binet–Cauchy の公式を使って証明している。本記事では証明しない。$K_4$ では $L_0=\begin{pmatrix}3&-1&-1\\-1&3&-1\\-1&-1&3\end{pmatrix}$ で $\det L_0=16$、$C_4$ では $L_0=\begin{pmatrix}2&-1&0\\-1&2&-1\\0&-1&2\end{pmatrix}$ で $\det L_0=4$ となり、ex-spt-small と一致する。冒頭の 5 角形に対角線 $02$、$03$ を加えたグラフでは $\det L_0=21$ である(すべての 4 辺の組を調べても 21 個)。$K_n$ に使うと Cayley の公式 $\tau(K_n)=n^{n-2}$ が得られる(Sta13 Example 9.11。Cayleyの公式 の記事は Prüfer 符号による別の証明を与えている)。

無限グラフと選択公理

thm-spt-existence の証明は、辺が有限個であることを使って「連結性を保つ最小の辺集合」をとった。頂点や辺が無限個あるグラフでは、この議論は使えない。以下、def-spt-graph で $V$ と $E$ が有限であるという条件を外したものを 無限グラフ とよぶ($V\ne\emptyset$ は残す)。歩道・閉路・連結・木・全域木は同じ定義で、歩道と閉路はつねに有限の長さである。lem-spt-add-edge の証明は有限性を使わないので、無限グラフでもそのまま成り立つ。
無限グラフでも連結なら全域木をもつが、その証明には選択公理が要り、しかも全域木の存在は選択公理と同値になる。以下、選択公理を含まない集合論の公理系 $\mathsf{ZF}$(ZFC から選択公理を除いたもの)の上で考える。

無限グラフの全域木と選択公理

$\mathsf{ZF}$ の上で、次の 2 つは同値である。

  1. 選択公理。
  2. 連結な無限グラフは、すべて全域木をもつ。

要点:1 ⇒ 2 は、閉路をもたない辺集合の全体に Zornの補題 を使い、極大なものが連結であることを示す。2 ⇒ 1 は、選択したい集合族 $(A_i)_{i\in I}$ から、根 $o$ と頂点 $v_i$ を $A_i$ の元で添字づけた平行辺で結んだグラフを作る。全域木は各 $v_i$ でちょうど 1 本の辺を残すので、その辺の添字が選択関数になる。

詳しい証明を開く

1 ⇒ 2:$G=(V,E,\partial)$ を連結な無限グラフとする。$(V,F)$ が閉路をもたないような $F\subset E$ の全体を $\mathcal{F}$ とし、包含で順序づける。$\emptyset\in\mathcal{F}$ なので $\mathcal{F}$ は空でない。$\mathcal{C}\subset\mathcal{F}$ を鎖とし、$F^*:=\bigcup\mathcal{C}$($\mathcal{C}=\emptyset$ なら $F^*=\emptyset$)とおく。$(V,F^*)$ に閉路があれば、その有限個の辺はそれぞれ $\mathcal{C}$ のある元に属し、$\mathcal{C}$ は鎖なので、それらすべてを含む $\mathcal{C}$ の元が 1 つある。その元が閉路をもつことになり矛盾する。よって $F^*\in\mathcal{F}$ は $\mathcal{C}$ の上界である。選択公理から従う Zorn の補題(選択公理 の記事の定理「Zornの補題との同値」)により、$\mathcal{F}$ は極大元 $F$ をもつ。$(V,F)$ が連結でないとし、$u,v$ を異なる連結成分の頂点、$C_u$ を $u$ の成分とする。$G$ は連結なので $G$ の歩道 $u=w_0,e_1,w_1,\dots,e_\ell,w_\ell=v$ がある。$w_\ell\notin C_u$ なので、$w_i\notin C_u$ となる最小の $i$ をとると、$w_{i-1}\in C_u$ であり、辺 $e_i$ は $(V,F)$ の異なる成分の 2 頂点を結ぶ。とくに $e_i$ はループでなく $e_i\notin F$ であり、lem-spt-add-edge により $F\cup\{e_i\}\in\mathcal{F}$ となって $F$ の極大性に反する。よって $(V,F)$ は連結で閉路をもたず、$G$ の全域木である。

2 ⇒ 1:$(A_i)_{i\in I}$ を空でない集合の族とする。$I=\emptyset$ なら空の写像が選択関数である。$I\ne\emptyset$ とし、新しい点 $o$ と各 $i\in I$ に対応する頂点 $v_i$ からなる頂点集合 $V:=\{o\}\sqcup\{v_i\mid i\in I\}$ と、辺集合 $E:=\{(i,a)\mid i\in I,\ a\in A_i\}$、端点 $\partial(i,a):=\{o,v_i\}$ によりグラフ $G$ を作る。これらはどれも集合の公理だけで作れる。$G$ は連結である。実際、各 $i$ について $A_i\ne\emptyset$ なので $(i,a)$ となる辺が存在し、$v_i$ は $o$ と結ばれる($i$ ごとに辺の存在を言うだけで、辺を一斉に選んではいない)。2 により全域木 $(V,F)$ がある。各 $i$ について、$v_i$ は $(V,F)$ で $o$ と歩道で結ばれ、その歩道の $v_i$ での辺は $(i,a)$ の形なので、$(i,a)\in F$ となる $a$ がある。$(i,a),(i,a')\in F$、$a\ne a'$ なら、$o,(i,a),v_i,(i,a'),o$ は $F$ の長さ $2$ の閉路になるので、そのような $a$ はただ 1 つである。よって $f:=\{(i,a)\mid(i,a)\in F\}$ は $I$ から $\bigcup_iA_i$ への写像で $f(i)\in A_i$ を満たし、族の選択関数である(選択公理 の記事の公理「選択公理の言明」)。$f$ は $F$ から分出公理で定まり、ここで選択は使っていない。$\square$

2 ⇒ 1 の証明は平行辺を使ったが、単純グラフに限っても同じ同値が成り立つ。各辺 $(i,a)$ の中ほどに新しい頂点 $m_{i,a}$ を置き、辺 $\{o,m_{i,a}\}$ と $\{m_{i,a},v_i\}$ に分ければよい。全域木の中で $v_i$ から $o$ への道は、$v_i$ の隣の頂点 $m_{i,a}$ を通り、$m_{i,a}$ のもう一方の隣 $o$ に着くので $v_i,m_{i,a},o$ の形である。そのような $a$ が 2 つあれば長さ $4$ の閉路ができるので、$a$ はただ 1 つに決まる。
位相幾何では、グラフを 1 次元の胞体複体とみて、可縮なグラフを木とよぶ流儀がある(Hat02 §1.A, p. 84)。そこでの「連結なグラフはすべての頂点を含む木をもつ」という命題(同 Proposition 1A.1)の証明も、各頂点に辺を 1 本ずつ同時に選んでいる。上の定理は、無限のグラフではこの種の選択が避けられないことを示している。

補足

全域木の数え方と応用

全域木は、通信網の設計(最小全域木)や電気回路の解析などに現れる。Sta13 第 11 章は全域木と電気回路の関係を扱っている。thm-spt-deletion-contraction を繰り返し使うと、ループ以外の辺がなくなるまで分解して $\tau(G)$ を計算できる。ループ以外の辺のないグラフの全域木は、頂点が 1 個なら辺のない $1$ 個、2 個以上なら(連結でないので)$0$ 個である。ただし分解の途中でグラフの個数が倍々に増えるので、手計算では小さなグラフに向き、大きなグラフには thm-spt-matrix-tree の行列式の計算が向いている。

関連項目

参考文献

[5]
Allen Hatcher, Algebraic Topology, 1st edition, Cambridge University Press, 2002, §1.A Graphs and Free Groups(p. 84:木を可縮なグラフとする定義、Proposition 1A.1)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する