この用語はまだ監査を通っていません（未確認）。
全域木
ぜんいきぎ 1対1で対応spanning tree
名詞 ・話し言葉・書き言葉
式と読み方
the number of edges of T equals the number of vertices of G minus one
定義
連結なグラフのすべての頂点を含み、もとのグラフの辺だけでできている木のこと。頂点が n 個なら辺は n − 1 本になる。
A tree that contains every vertex of a connected graph and uses only edges of that graph. If the graph has n vertices, a spanning tree has n − 1 edges.
例文
話し言葉 Keep deleting edges that lie on a cycle until no cycles are left, and what you end up with is a spanning tree. 閉路に含まれる辺を、閉路がなくなるまで取り除いていこう。最後に残ったものが全域木だ。
書き言葉・答案 Find two different spanning trees of the graph below. 下のグラフの全域木を 2 つ求めよ。
言い間違えやすいところ
- 辺に重みがあるとき、重みの合計が最小の全域木を minimum spanning tree（最小全域木）という。
- 全域木をもつのは連結なグラフだけ。1 つのグラフに全域木はふつう何通りもある。
- 用例コーパスでは話し言葉はすべて MIT OCW、書き言葉はすべて MIT の講義ノート。Levin の本では 2.2 Trees に 13 件。