代数的グラフ理論入門 ― 行列で読むグラフの構造

隣接行列，ラプラシアン$L=D-A$，行列木定理，固有値と連結性，$A^k$の$(i,j)$成分が道の数を表すことを証明する．

2026年2月27日

1 隣接行列

定義 1 (隣接行列).

n

頂点の単純グラフ

G = (V, E)

（

V = {v_{1}, \dots, v_{n}}

）に対して，隣接行列（adjacency matrix）

A = A (G)

を

A_{ij} = {10 {v_{i}, v_{j}} \in E otherwise

で定める．

G

が無向グラフのとき

A

は実対称行列である．

例 2.

パスグラフ

P_{3}

（頂点

v_{1} - v_{2} - v_{3}

）の隣接行列は

A = 010101010

2 $A^{k}$ と歩道の数

定理 3 (

A^{k}

の組合せ的解釈).

グラフ

G

の隣接行列を

A

とする．

A^{k}

の

(i, j)

成分は，

v_{i}

から

v_{j}

への長さ

k

の歩道（walk）の数に等しい．

証明.

k

に関する帰納法で示す．

$k = 1$ ：

A^{1} = A

であり，

(A)_{ij} = 1

は

v_{i}

と

v_{j}

が隣接すること，すなわち長さ1の歩道が1つ存在することに対応する．

(A)_{ij} = 0

は隣接しないこと，すなわち歩道がないことに対応する．

帰納段階：

A^{k - 1}

の

(i, ℓ)

成分が

v_{i}

から

v_{ℓ}

への長さ

k - 1

の歩道の数であると仮定する．

(A^{k})_{ij} = ℓ = 1 \sum n (A^{k - 1})_{i ℓ} \cdot A_{ℓ j}

A_{ℓ j} = 1

のとき（

v_{ℓ}

と

v_{j}

が隣接するとき），

v_{i}

から

v_{ℓ}

への長さ

k - 1

の各歩道に辺

{v_{ℓ}, v_{j}}

を追加して

v_{i}

から

v_{j}

への長さ

k

の歩道が得られる．

A_{ℓ j} = 0

なら寄与しない．すべての中間頂点

v_{ℓ}

にわたる和を取ると，

v_{i}

から

v_{j}

への長さ

k

の歩道の総数が得られる． □

例 4.

K_{3}

（三角形）の隣接行列は

A = 011101110

であり，

A^{2} = 211121112

．

(A^{2})_{11} = 2

は

v_{1}

から

v_{1}

への長さ2の歩道が2つ（

v_{1} v_{2} v_{1}

と

v_{1} v_{3} v_{1}

）あることを表す．

3 ラプラシアン行列

定義 5 (次数行列とラプラシアン).

G

の次数行列（degree matrix）

D

を

D_{ii} = de g (v_{i})

，

D_{ij} = 0

（

i \neq = j

）で定める．

G

のラプラシアン（Laplacian matrix）を

L = L (G) = D - A

と定める．

$L$ の各行の和は $0$ である（ $\sum_{j} L_{ij} = D_{ii} - \sum_{j} A_{ij} = de g (v_{i}) - de g (v_{i}) = 0$ ）．よって $L 1 = 0$ ，すなわち全成分 $1$ のベクトル $1$ は固有値 $0$ に属する固有ベクトルである．

定理 6 (ラプラシアンの半正定値性).

L (G)

は半正定値である．すなわち任意の

x \in R^{n}

に対して

x^{T} L x \geq 0

．

証明.

x^{T} L x = i \sum D_{ii} x_{i}^{2} - i, j \sum A_{ij} x_{i} x_{j} = {v_{i}, v_{j}} \in E \sum (x_{i} - x_{j})^{2} \geq 0

最後の等号は各辺

{v_{i}, v_{j}}

について

D

への寄与と

A

への寄与を整理すれば得られる． □

4 固有値と連結性

$L$ は実対称かつ半正定値なので，固有値を $0 = λ_{1} \leq λ_{2} \leq \dots \leq λ_{n}$ と並べることができる．

定理 7 (連結成分と固有値

0

の重複度).

グラフ

G

の連結成分の数は，

L (G)

の固有値

0

の重複度に等しい．

証明.

G

が

c

個の連結成分

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

を持つとする．頂点を連結成分ごとにまとめると

L

はブロック対角行列

L = L (G_{1}) \oplus \dots \oplus L (G_{c})

となる．各

L (G_{k})

は半正定値で

L (G_{k}) 1_{k} = 0

を満たすから固有値

0

を少なくとも1つ持つ．

L (G_{k})

の固有値

0

の重複度が1であることを示す．

L (G_{k}) x = 0

ならば

x^{T} L (G_{k}) x = \sum_{{v_{i}, v_{j}} \in E (G_{k})} (x_{i} - x_{j})^{2} = 0

であり，

G_{k}

は連結なので任意の2頂点間にパスがあり，すべての成分が等しい．よって

ker L (G_{k})

は

1_{k}

のスカラー倍で1次元．

全体では固有値

0

の重複度は

c

である． □

定義 8 (代数的連結度).

G

が連結グラフのとき，

λ_{2} (L (G))

（

L

の2番目に小さい固有値）を

G

の代数的連結度（algebraic connectivity）またはFiedler値という．

注意 9.

λ_{2} > 0

と

G

が連結であることは同値である．

λ_{2}

が大きいほどグラフの連結度が「強い」ことを意味し，グラフの分割やクラスタリングにおいて重要な指標となる．

5 行列木定理

定理 10 (行列木定理（Kirchhoff, 1847年）).

G

を

n

頂点の連結グラフ，

L = L (G)

をラプラシアンとする．

L

の任意の

(i, i)

-余因子を

L_{ii}

とおくと，

G

の全域木の数

τ (G)

は

τ (G) = L_{ii} = \frac{1}{n} λ_{2} λ_{3} \dots λ_{n}

ここで

λ_{1} = 0 < λ_{2} \leq \dots \leq λ_{n}

は

L

の固有値である．

証明.

証明の概略を述べる．

\hat{L}

を

L

の第

i

行と第

i

列を除いた

(n - 1) \times (n - 1)

行列とする．Cauchy–Binet の公式により

det \hat{L} = ∣ S ∣ = n - 1 \sum det B_{S}^{T} det B_{S}

ここで

B

は

G

の接続行列（向き付きの辺頂点接続行列から第

i

行を除いたもの）であり，

S

は

E

の

(n - 1)

元部分集合を動く．

det B_{S} \neq = 0

と

S

が全域木であることが同値であり（このとき

det B_{S} = \pm 1

），上の和は全域木の数に等しい．

固有値との関係は

det \hat{L} = \frac{1}{n} \prod_{k = 2}^{n} λ_{k}

で与えられる（

L

の固有多項式の解析から従う）． □

例 11.

K_{4}

のラプラシアンの固有値は

0, 4, 4, 4

であり，

τ (K_{4}) = \frac{1}{4} \cdot 4^{3} = 16

．一般に

τ (K_{n}) = n^{n - 2}

（Cayleyの公式）．

グラフ理論離散数学教科書隣接行列ラプラシアン行列木定理

Folio公式

数学の「教科書が書かない行間」をLaTeXで．Folio公式アカウントです．

0 followers·105 articles

代数的グラフ理論入門 ― 行列で読むグラフの構造

1 隣接行列

2 $A^{k}$ と歩道の数

3 ラプラシアン行列

4 固有値と連結性

5 行列木定理

Share your expertise with the world

More from Folio公式

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

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

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

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

1 隣接行列

2 Akと歩道の数

3 ラプラシアン行列

4 固有値と連結性

5 行列木定理

Share your expertise with the world

More from Folio公式

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

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

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

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

2 $A^{k}$ と歩道の数