木と森 ― 最小限の連結構造

木の同値条件を証明し，$|E|=|V|-1$，根付き木，Cayleyの公式，全域木，最小全域木（Kruskal/Primのアルゴリズム）を扱う．

2026年2月27日

1 木の定義と同値条件

定義 1 (木と森).

連結で閉路を持たないグラフを木（tree）という．閉路を持たないグラフ（連結とは限らない）を森（forest）という．すなわち森とは各連結成分が木であるグラフである．

定理 2 (木の同値条件).

n

頂点のグラフ

G

について，以下は同値である：

$G$ は木（連結かつ閉路なし）．
$G$ の任意の2頂点間にちょうど1本の道が存在する．
$G$ は連結で $∣ E (G) ∣ = n - 1$ ．
$G$ は閉路を持たず $∣ E (G) ∣ = n - 1$ ．
$G$ は連結であり，任意の辺を除去すると非連結になる（すべての辺が橋）．
$G$ は閉路を持たないが，任意の非辺 ${u, v} \in / E (G)$ を追加すると閉路が生じる．

証明.

(1) \Rightarrow (2)

：連結なので任意の2頂点間に道が存在する．道が2本以上あれば，それらを合わせて閉路が得られ矛盾．

(2) \Rightarrow (3)

：道の存在より連結．辺数について

n

に関する帰納法で示す．

n = 1

なら

∣ E ∣ = 0 = n - 1

．

n \geq 2

とする．次数

1

の頂点（葉）が存在する．実際，もしすべての頂点の次数が

\geq 2

ならば，任意の頂点から出発し未訪問の辺を辿り続ければ閉歩道が得られ，閉路の存在が従い（2）に矛盾する．葉

v

とそれに接続する辺を除くと条件(2)を満たす

n - 1

頂点のグラフとなり，帰納法の仮定より辺数は

n - 2

．辺を1本戻して

∣ E ∣ = n - 1

．

(3) \Rightarrow (4)

：

∣ E ∣ = n - 1

を保ったまま閉路が存在すると仮定して矛盾を導く．閉路の辺を1つ除去しても連結性は保たれ，

n

頂点

n - 2

辺の連結グラフが得られるが，連結グラフは

∣ E ∣ \geq n - 1

を満たすので矛盾．

(4) \Rightarrow (1)

：

G

の連結成分を

G_{1}, \dots, G_{c}

とし，

G_{i}

の頂点数を

n_{i}

とする．各

G_{i}

は木なので

(1) \Rightarrow (3)

より

∣ E (G_{i}) ∣ = n_{i} - 1

．

∣ E (G) ∣ = \sum (n_{i} - 1) = n - c

．

∣ E (G) ∣ = n - 1

より

c = 1

，すなわち

G

は連結．

(1) \Rightarrow (5)

：木のすべての辺は橋である．辺

e

がある閉路に含まれるならば矛盾．

(5) \Rightarrow (1)

：連結は仮定．辺

e = {u, v}

が閉路に含まれるならば

G - e

でも

u

v

間に道があり橋でないので矛盾．

(1) \Rightarrow (6)

：閉路がないことは仮定．非辺

{u, v}

を追加すると，元の

u

v

道と合わせて閉路が生じる．

(6) \Rightarrow (1)

：閉路がないことは仮定．非連結と仮定すると，異なる成分の頂点

u, v

に対し

{u, v}

を追加しても閉路は生じず矛盾． □

2 根付き木

定義 3 (根付き木).

木

T

の特定の頂点

r

を根（root）として指定したものを根付き木（rooted tree）という．根

r

から各頂点への唯一の道によって親子関係が定まる：

u

v

間の道において

u

が

r

に近い側にあるとき

u

は

v

の親，

v

は

u

の子である．子を持たない頂点を葉（leaf）という．

3 Cayley の公式

定理 4 (Cayley の公式).

n

個のラベル付き頂点

{1, 2, \dots, n}

上のラベル付き木の総数は

n^{n - 2}

である．

証明.

Prü

n

頂点のラベル付き木と長さ

n - 2

の列

(a_{1}, \dots, a_{n - 2})

（

a_{i} \in {1, \dots, n}

）の間に全単射を構成する．

木から列への写像：木

T

に対し，以下を

n - 2

回繰り返す．最小のラベルを持つ葉

v

を選び，

v

の隣接頂点を

a_{i}

として記録し，

v

を除去する．

列から木への写像：列

(a_{1}, \dots, a_{n - 2})

から木を復元する．

S = {1, \dots, n}

とする．

i = 1, \dots, n - 2

に対し，

S

の元のうち列

(a_{i}, \dots, a_{n - 2})

に現れない最小のものを

v

とし，辺

{v, a_{i}}

を追加して

S

から

v

を除く．最後に

S

に残った2頂点を辺で結ぶ．

この2つの写像が互いに逆であることが確認でき，全単射が得られる．列は

n^{n - 2}

通りあるので結論が従う． □

例 5.

n = 3

のとき

3^{1} = 3

．3頂点のラベル付き木は辺集合が

{{1, 2}, {1, 3}}

，

{{1, 2}, {2, 3}}

，

{{1, 3}, {2, 3}}

の3種類で一致する．

4 全域木と最小全域木

定義 6 (全域木).

連結グラフ

G

の全域木（spanning tree）とは，

G

の全頂点を含む部分グラフであって木であるものをいう．

定理 7.

連結グラフは必ず全域木を持つ．

証明.

G

が連結で閉路を持てば木である．そうでなければ閉路の辺を1つ除去しても連結性は保たれる．辺数は有限なのでこの操作を繰り返せば木が得られる． □

定義 8 (最小全域木).

辺に重み

w : E \to R

が付いた連結グラフ

G

に対して，全域木

T

のうち

w (T) = \sum_{e \in E (T)} w (e)

を最小にするものを最小全域木（MST: minimum spanning tree）という．

定理 9 (カット性質).

辺重みが相異なるとき，任意のカット（

V

の2分割

(S, V ∖ S)

を跨ぐ辺の集合）の中で最小重みの辺は MST に含まれる．

証明.

最小重み辺

e = {u, v}

（

u \in S

，

v \in V ∖ S

）が MST

T

に含まれないと仮定する．

T

における

u

v

道はカットを奇数回横切るので，

e

以外のカット辺

f

を含む．

T - f + e

は全域木であり

w (e) < w (f)

より

w (T - f + e) < w (T)

となって最小性に矛盾． □

注意 10 (Kruskal のアルゴリズム).

辺を重みの小さい順にソートし，閉路を作らない限り辺を追加する．Union-Find を用いると時間計算量

O (m lo g m)

で MST が得られる．

アルゴリズム 1: Kruskal のアルゴリズム

Input:

連結グラフ

G = (V, E)

，重み関数

w : E \to R

Output:

最小全域木の辺集合

T

T \leftarrow \emptyset

E

の辺を重み

w

の昇順にソート:

e_{1}, e_{2}, \dots, e_{m}

for all

v \in V

MakeSet(

v

)

// Union-Find 初期化

end for

for

i = 1

m

e_{i} = {u, v}

とする

Find (u) \neq = Find (v)

T \leftarrow T \cup {e_{i}}

Union(

u, v

)

end if

end for

return

T

注意 11 (Prim のアルゴリズム).

1頂点から開始し，現在の木に隣接するカット辺のうち最小重みの辺を繰り返し追加する．優先度付きキューを用いると時間計算量

O (m lo g n)

で MST が得られる．

アルゴリズム 2: Prim のアルゴリズム

Input:

連結グラフ

G = (V, E)

，重み関数

w

，開始頂点

r

Output:

最小全域木の辺集合

T

T \leftarrow \emptyset

，

S \leftarrow {r}

key [r] \leftarrow 0

for all

v \in V ∖ {r}

key [v] \leftarrow + \infty

end for

優先度付きキュー

Q

に全頂点を

key

値で挿入

while

Q \neq = \emptyset

u \leftarrow ExtractMin (Q)

S \leftarrow S \cup {u}

u \neq = r

T \leftarrow T \cup {{u, parent [u]}}

end if

for all

(u, v) \in E

with

v \in Q

w (u, v) < key [v]

key [v] \leftarrow w (u, v)

parent [v] \leftarrow u

DecreaseKey(

Q, v, key [v]

)

end if

end for

end while

return

T

木と森 ― 最小限の連結構造

1 木の定義と同値条件

2 根付き木

3 Cayley の公式

4 全域木と最小全域木

関連する「教科書の行間」記事

あなたの専門知識を世界に発信しよう

Folio公式の他の記事

Folio LaTeXの基本 ― 標準LaTeXとの違いと始め方

カタラン数はなぜどこにでも現れるのか ― 括弧列・二分木・格子経路の不思議な一致

漸化式と母関数 ― 数列を「関数」にすると何が見えるか

包除原理はなぜ「足して引いて」を繰り返すのか ― ベン図からメビウス関数へ