木
概要
木（tree）とは、有限単純グラフのうち連結で閉路を持たないものである。頂点をすべて結びながら余分な辺を持たず、辺を1本加えるとちょうど1つの閉路ができ、辺を1本除くとちょうど2つの連結成分に分かれる。道グラフ・星グラフを例に、森・根付き木との違い、空グラフを含めるかという流儀、全域木や探索木へのつながりを解説する。
木は連結で閉路をもたないグラフであり、頂点をすべてつなぎながら余分な辺を一本も持たない、もっとも単純な連結構造である。プログラムのディレクトリ構造、生物の系統樹、探索アルゴリズムの探索経路など、階層や最小接続を表す場面のほとんどに木が現れる。
木の形はさまざまだが、二頂点間の道の一意性、辺数の公式、辺の追加と除去に関する性質が共通する。連結性を外すと森になり、一つの頂点を根として指定すると根付き木になる。ここでは木と葉を定義し、これらの基本性質を証明する。基本的な流儀と例は Die25 §1.5、Wes01 §2.1 にもある。
本記事では、特に断らない限り有限の無向単純グラフ（ループも多重辺も持たない）を扱う。無限グラフでの木の理論は無限グラフに委ねる。
定義
木 $T=(V,E)$ の頂点 $v\in V$ が葉（leaf）であるとは、$v$ の次数が $1$ であることをいう。
木の定義から連結性だけを外し、閉路を持たないグラフを森（forest）という。森の各連結成分は木である。成分ごとに後述の辺数公式を足すと、頂点数 $n$、辺数 $m$、連結成分数 $c$ の森では $m=n-c$ となる。
木 $T$ の一頂点 $r$ を特別に指定した組 $(T,r)$ を根付き木（rooted tree）といい、$r$ を根（root）とよぶ。根を固定すると、根から各頂点への経路に沿って親・子・先祖・子孫・深さといった階層的な語彙が定まる。これらの定義と性質は根付き木で詳しく扱う。
連結グラフと同じく、ここでは連結性に頂点集合の非空性 $V\neq\emptyset$ を含める。したがって頂点を一つも持たない空グラフは、閉路を持たなくても木には含めず、以降は $n:=|V|\geq1$ とする。文献によっては連結性を「任意の二頂点が道で結ばれる」とだけ定義し、空虚な真によって空グラフを退化した木に含めることもある。ただし辺数公式 $m=n-1$ は $n=0$ では $0=-1$ となるため、この公式を使うときは非空性を確認する。
直感
木とは、頂点をすべて結びながら、どの辺も取り除くと連結性を失うほど余分な辺を一本も持たない、ぎりぎりの連結グラフである。逆に見れば、木に辺を1本足せば必ずどこかに輪ができ、木から辺を1本引けばどこかで確実に切れる。この「足せば輪、引けば切断」という両方向の脆さが、木の基本性質のほとんどの出発点になる。
例
頂点集合 $\{v_1,\ldots,v_n\}$（$n\geq1$）を辺 $\{v_1,v_2\},\{v_2,v_3\},\ldots,\{v_{n-1},v_n\}$ で結んだ道グラフ $P_n$ は木である。連結性は隣接する頂点を順にたどれば直ちに確認でき、各頂点の次数が高々2で「後戻り」する辺がないことから閉路を持たないことも分かる。$n=1$ のときは頂点1個・辺0個の自明な木であり、$v_1$ が（次数0の）唯一の頂点となる。$n\geq2$ のとき、葉は両端の $v_1,v_n$ のちょうど2個である。
中心頂点 $c$ と葉候補 $u_1,\ldots,u_{n-1}$（$n\geq2$）を辺 $\{c,u_1\},\ldots,\{c,u_{n-1}\}$ で結んだ星グラフ $K_{1,n-1}$ は木である。任意の $u_i$ から $u_j$ への移動は必ず $c$ を経由し、$c$ を経由しない別の経路は存在しないため閉路は生じない。道グラフとは全く形が違うが、頂点数が同じ $n$ であれば辺数はやはり $n-1$ である（$u_1,\ldots,u_{n-1}$ の $n-1$ 個がすべて葉であり、$n\geq3$ なら $c$ は葉ではない）。
3頂点3辺の三角形グラフ（頂点 $a,b,c$ を辺 $\{a,b\},\{b,c\},\{c,a\}$ で結んだもの）は連結だが、$a,b,c,a$ という長さ3の閉路を持つため木ではない。この例は、「連結」という条件だけでは木を特徴づけられず、閉路を持たないという条件が独立に必要であることを示す。
互いに交わらない道グラフ $P_2$（頂点 $\{a,b\}$、辺 $\{a,b\}$）と、孤立点だけからなる $P_1$（頂点 $\{c\}$、辺なし）を合わせたグラフは、閉路を一つも持たないが、$a$ から $c$ への道が存在しないため連結でなく、木ではない。これは2本の木からなる森の一例であり、閉路を持たないという条件だけでも木を特徴づけられないことを示す。
性質
道・葉・辺数
頂点数 $n\geq1$ の木 $T$ について、次が成り立つ。
- 任意の二頂点を結ぶ道はちょうど一つある。
- $n\geq2$ なら葉は少なくとも二つある。
- 辺数は $n-1$ である。
1：連結性から道が少なくとも一つある。異なる二つの単純道が同じ端点を結ぶなら、両者が初めて分かれて再び合流する部分から閉路を作れる。木に閉路はないので道は一意である。
2：有限なので最も長い単純道 $v_0,v_1,\ldots,v_k$ を取れる。$n\geq2$ なら $k\geq1$ である。もし端点 $v_0$ に $v_1$ 以外の隣接頂点があれば、その頂点が道の外なら道を延長でき、道の中なら閉路ができる。いずれも矛盾するので $v_0$ の次数は1である。同様に $v_k$ も葉で、両者は異なる。
3：$n=1$ なら辺はない。$n\geq2$ なら葉 $v$ とその唯一の辺を除く。残ったグラフは閉路を持たず、元の木の二頂点間の道は葉を内部に通れないので連結でもある。従って $n-1$ 頂点の木となる。帰納法でその辺数は $n-2$、元の木はそれより1本多いので $n-1$ 本である。$\blacksquare$
辺数公式はEulerの公式(平面グラフ)で、木を平面に描いたときの基底段階（$f=1$、$e=v-1$）として使われる。
辺を1本加えるとちょうど1つの閉路ができる
$T=(V,E)$ を頂点数 $n\geq2$ の木とし、$u,v\in V$ を $T$ で隣接していない相異なる頂点とする（すなわち $u\neq v$ かつ $\{u,v\}\notin E$）。このとき $T':=(V,\ E\cup\{\{u,v\}\})$ はちょうど1つの閉路を持ち、その閉路は $T$ における $u$–$v$ 道に辺 $\{u,v\}$ を付け加えたものに一致する。
閉路の存在。 $T$ は連結だから、$u$ から $v$ への道 $P\colon u=w_0,w_1,\ldots,w_k=v$ が $T$ の中に存在する（$k\geq1$）。$\{u,v\}\notin E$ より $P$ は辺 $\{u,v\}$ を使わないので $k\geq2$ である。$P$ に辺 $\{u,v\}$ を付け加えた閉じた歩道 $u=w_0,w_1,\ldots,w_k=v,u$ は、$P$ が単純道（頂点の重複がない）であり辺 $\{u,v\}$ が $P$ の辺として現れないことから、長さ $k+1\geq3$ の閉路 $C$ を成す。$C$ は $T'$ の部分グラフである。
閉路の一意性。 $C'$ を $T'$ の任意の閉路とする。$T$ 自身は閉路を持たない（木の定義）ので、$C'$ は $T'$ にのみ存在する辺 $\{u,v\}$ を用いなければならない。閉路の各辺はちょうど一度しか現れないから、$C'$ から辺 $\{u,v\}$ を除いた残りは $u$ から $v$（またはその逆順）への道であり、しかもその道の辺はすべて $E$ に属するので $T$ 内の $u$–$v$ 道である。prop-tree-basic-facts の道の一意性により、この道は上で構成した $P$ に限られる。したがって $C'=C$ である。
辺を1本除くとちょうど2つの連結成分に分かれる
$T=(V,E)$ を頂点数 $n\geq2$ の木とし、$e=\{x,y\}\in E$ を任意の辺とする。このとき $T-e:=(V,\ E\setminus\{e\})$ はちょうど2つの連結成分を持ち、一方が $x$ を、他方が $y$ を含む。
$x$ と $y$ は $T-e$ で異なる成分に属する。 もし $T-e$ の中に $x$ から $y$ への道 $Q$ があれば、$Q$ は辺 $e$ を用いないから、$Q$ に $e$ を付け加えると $T$ の中に長さ $3$ 以上の閉路ができる。これは $T$ が閉路を持たないことに反する。よって $T-e$ において $x$ と $y$ を結ぶ道は存在せず、両者は異なる連結成分に属する。したがって $T-e$ の連結成分数は2以上である。
成分数は2以下である。 $a\in V$ を任意の頂点とする。$T$ は連結だから、$a$ から $x$ への道 $P_a$ が $T$ の中に存在する。$P_a$ は単純道なので、頂点 $x$ は $P_a$ の中にちょうど一度、しかも終点としてのみ現れる。
$P_a$ が辺 $e=\{x,y\}$ を用いないならば、$P_a$ の辺はすべて $T-e$ に残っているから、$P_a$ はそのまま $T-e$ の中の $a$–$x$ 道であり、$a$ は $x$ の属する成分にある。
$P_a$ が辺 $e=\{x,y\}$ を用いるならば、$x$ が $P_a$ の終点であり、かつ単純道の中に一度しか現れないことから、辺 $e$ は $P_a$ の最後の一辺（$y$ から $x$ へ入る辺）としてのみ現れる。ゆえに $P_a$ から最後の辺を除いた部分 $P_a'$ は $a$ から $y$ への道であり、辺 $e$ を用いない。したがって $P_a'$ は $T-e$ の中の $a$–$y$ 道であり、$a$ は $y$ の属する成分にある。
いずれの場合も $a$ は $x$ の成分または $y$ の成分に属する。$a$ は任意だったから、$T-e$ の頂点はすべて $x$ の成分または $y$ の成分に属し、連結成分数は2以下である。
以上より $T-e$ の連結成分数はちょうど2であり、一方が $x$ を、他方が $y$ を含む。
応用
全域木
連結なグラフ $G$ の頂点集合をすべて含み、$G$ の辺集合の部分集合を辺集合とする木を $G$ の全域木（spanning tree）という。連結グラフが必ず全域木を持つことと、閉路上の辺を1本ずつ除いて全域木に到達する構成法は全域木で扱う。この構成では、閉路上の辺を除いても連結性が保たれることを使う。
最小全域木
各辺に重みが付いたグラフに対し、重みの総和が最小になる全域木を求める問題を最小全域木問題という。Kruskal法・Prim法などのアルゴリズムと、その正当性の証明は最小全域木で扱う。
探索木
始点を一つ固定して深さ優先探索・幅優先探索を行うと、その始点から到達できた頂点と、各頂点を初めて訪れたときの辺から探索木が得られる。始点が根となる。元のグラフが非連結で全成分を探索する場合、成分ごとに探索木ができ、全体では探索森となる。詳細は深さ優先探索・幅優先探索・根付き木で扱う。
注意
「閉路を持たない」という条件は非輪状（acyclic）とも呼ばれる。木は「連結な非輪状グラフ」、森は「連結とは限らない非輪状グラフ」と言い換えられる。
本記事は有限の単純グラフのみを扱う。無限グラフでも「連結かつ閉路を持たない」という定義自体は意味を持つが、辺数の公式（$m=n-1$）や葉の存在といった有限性に依存する性質は成り立たない場合がある（両側無限の道は葉を一つも持たない）。無限グラフでの木の理論は無限グラフに委ねる。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
