行列木定理による全域木の個数

ラプラシアン行列 $L = D - A$ の 1 行 1 列を除いた小行列式、または $L$ の 0 以外の固有値 $λ_{2}, \dots, λ_{n}$ を使う $τ (G) = \frac{1}{n} \prod_{i = 2}^{n} λ_{i}$ で全域木の個数を求められる。完全グラフ $K_{n}$ から辺集合 $H$ を除いたグラフでは、 $L (H)$ の固有値 $μ_{i}$ から $L (G)$ の固有値 $n - μ_{i}$ を求めて計算できる（ケーリーの公式 $n^{n - 2}$ を含む。例: $K_{7}$ から互いに交わらない 3 辺を除くと $\frac{5 ^{3} \cdot 7 ^{3}}{7}$ ）

前提

固有値と固有ベクトル（大学数学線形代数）
グラフの次数と握手補題（大学数学グラフ理論）

この技能までの道筋（45 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

三角形の角の大きさ（算数平面図形）
対頂角と平行線の同位角・錯角（中学数学平面図形）
三角形の外角と角の組み合わせ（中学数学平面図形）
小数の四則計算（算数計算と数のきまり）
分数のたし算・ひき算（算数計算と数のきまり）
分数のかけ算・わり算（算数計算と数のきまり）
小数と分数のまじった計算（算数計算と数のきまり）
逆算（□ を求める）（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
1 次方程式の解き方（中学数学方程式）
二等辺三角形の角（中学数学平面図形）
平行四辺形と特別な四角形の性質（中学数学平面図形）
三角形・四角形の面積（算数平面図形）
約数の見つけ方（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
平方根の意味と根号の簡単化（中学数学数と式）
三平方の定理（中学数学相似と三平方の定理）
乗法公式による展開（中学数学数と式）
折り返した図形の角と長さ（中学数学平面図形）
三平方の定理と平面図形（中学数学相似と三平方の定理）
ベクトルの演算と成分（数学C ベクトル）
行列の和・積と 2 次の逆行列（大学数学線形代数）
樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
順列・円順列・重複順列（数学A 場合の数と確率）
行列式（大学数学線形代数）
掃き出し法と連立 1 次方程式（大学数学線形代数）
行列の階数と解の存在（大学数学線形代数）
ベクトル空間・一次独立・基底・次元（大学数学線形代数）
円の周の長さと面積（算数平面図形）
おうぎ形の弧の長さと面積（算数平面図形）
弧の長さからおうぎ形の中心角と面積を求める（中学数学平面図形）
特別な直角三角形の辺の比（中学数学相似と三平方の定理）
弧度法と単位円による三角関数（数学II 三角関数）
加法定理と 2 倍角・半角・積和の公式（数学II 三角関数）
線形変換と行列（大学数学線形代数）
核と像と次元定理（大学数学線形代数）
固有値と固有ベクトル（大学数学線形代数）
組合せ（数学A 場合の数と確率）
グラフの次数と握手補題（大学数学グラフ理論）

説明

連結なグラフ $G$ の全域木とは、 $G$ のすべての頂点を含み、 $G$ の辺だけを使ってできる木（閉路をもたない連結なグラフ）のことです。行列木定理を使うと、全域木をひとつずつ数え上げなくても、行列式を 1 回計算するか固有値を求めるだけで、その個数 $τ (G)$ がわかります。回路網の解析、ネットワークの信頼性、ケーリーの公式 $τ (K_{n}) = n^{n - 2}$ の導出などで使います。特に完全グラフ $K_{n}$ から少数の辺を除いたグラフでは、除いた辺の側の固有値を調べるだけで済むので、大きなグラフでも計算が軽くなります。

なぜそうしてよいのか

頂点が $1, \dots, n$ のグラフ（ループなし）について、次数を対角に並べた行列を $D$ 、隣接行列を $A$ とし、ラプラシアン行列 $L = D - A$ を考えます。各辺に好きな向きをつけ、辺 $e : u \to v$ の列が「 $u$ 成分に $+ 1$ 、 $v$ 成分に $- 1$ 、ほかは $0$ 」となる $n \times m$ 行列 $B$ （接続行列）を作ります。すると $B B^{T}$ の $(v, v)$ 成分は $v$ に接する辺の数 $de g v$ になり、 $u \neq = v$ の $(u, v)$ 成分は、 $uv$ が辺なら $- 1$ 、辺でなければ $0$ になります。つまり $L = B B^{T}$ です。 $B$ から第 1 行を除いた行列を $B_{0}$ とすると、 $L$ の 1 行 1 列を除いた行列は $B_{0} B_{0}^{T}$ になります。ここで行列式の積の展開公式（コーシー・ビネの公式）を使います。これは、 $(n - 1) \times m$ 行列 $P$ と $m \times (n - 1)$ 行列 $Q$ について、 $det (P Q) = \sum_{S} det P_{S} det Q_{S}$ （和は $n - 1$ 本の辺の選び方 $S$ 全体にわたり、 $P_{S}$ は $P$ から $S$ の列だけを、 $Q_{S}$ は $Q$ から $S$ の行だけを取り出した行列）が成り立つという公式です。 $P = B_{0}$ , $Q = B_{0}^{T}$ とおくと $det (B_{0} B_{0}^{T}) = \sum_{S} (det B_{0} [S])^{2}$ となります（ $B_{0} [S]$ は $B_{0}$ から $S$ の列だけを取り出した行列）。 $S$ が全域木なら、頂点 1 以外の葉（次数 1 の頂点）の行には $\pm 1$ がちょうど 1 つしかありません。その行で余因子展開し、葉を 1 つずつはがしていくと $det B_{0} [S] = \pm 1$ になります。 $S$ が全域木でなければ、辺が $n - 1$ 本なので $S$ は連結になれず、頂点 1 を含まない連結成分 $C$ ができます。 $C$ の頂点の行をすべて足すと、各辺の $+ 1$ と $- 1$ が打ち消し合って 0 になるので、 $det B_{0} [S] = 0$ です。こうして、小行列式はちょうど全域木の個数を数えています。頂点の番号は付け替えてよいので、どの $i$ 行 $i$ 列を除いても同じ値 $τ (G)$ になります。

固有値で表す形は特性多項式から出てきます。 $L$ の各行の和は 0 なので、すべての成分が 1 のベクトル $1$ について $L 1 = 0$ となり、 $λ_{1} = 0$ は固有値です。 $det (λ E - L) = \prod_{i = 1}^{n} (λ - λ_{i})$ の $λ$ の係数は、 $λ_{1} = 0$ より $(- 1)^{n - 1} λ_{2} \dots λ_{n}$ です。一方、行列式を展開すると、この係数は $(- 1)^{n - 1} \times$ ( $i$ 行 $i$ 列を除いた小行列式の $i = 1, \dots, n$ にわたる和) にもなります。各小行列式は $τ (G)$ なので $λ_{2} \dots λ_{n} = n τ (G)$ 、つまり $τ (G) = \frac{1}{n} \prod_{i = 2}^{n} λ_{i}$ です。 $G$ が連結でないときは 0 が重複して $λ_{2} = 0$ となり、式の値は正しく 0 になります。

$G = K_{n} - H$ の場合を考えます。 $J$ をすべての成分が 1 の $n$ 次行列とすると $L (K_{n}) = n E - J$ なので、 $L (G) = n E - J - L (H)$ です（ $H$ は $n$ 頂点すべてをもつグラフとみなします）。 $L (H)$ は実対称行列なので、互いに直交する固有ベクトルからなる基底をとれます。そのうち 1 本を $1$ （固有値 $μ_{1} = 0$ ）にすると、残りの固有ベクトル $v$ （固有値 $μ_{i}$ ）は $1$ と直交します。よって $J v = 0$ となり、 $L (G) v = (n - μ_{i}) v$ が成り立ちます。したがって $L (G)$ の固有値は $0$ と $n - μ_{2}, \dots, n - μ_{n}$ です。 $H$ が辺をもたなければ、すべての $μ_{i}$ が 0 なので $τ (K_{n}) = \frac{n ^{n - 1}}{n} = n^{n - 2}$ （ケーリーの公式）が出ます。

手順

頂点数 $n$ と各頂点の次数を求め、ラプラシアン行列 $L = D - A$ を作る（対角成分は次数、辺 $uv$ に対応する成分は $- 1$ 、それ以外は $0$ 。各行の和が 0 になることで検算できる）。
【小行列式で求める場合】 $L$ から同じ番号の $i$ 行と $i$ 列を除いた $n - 1$ 次の行列式を計算する。その値が $τ (G)$ である（ $i$ はどれを選んでもよい）。
【固有値で求める場合】 $det (L - λ E) = 0$ を解いて $L$ の固有値を重複も含めて $0 = λ_{1}, λ_{2}, \dots, λ_{n}$ と並べ、 $τ (G) = \frac{1}{n} \prod_{i = 2}^{n} λ_{i}$ を計算する。
【 $G = K_{n} - H$ の場合】除く辺の集合 $H$ を $n$ 頂点すべてをもつグラフとみなし、 $L (H)$ の固有値を重複込みで $μ_{1} = 0, μ_{2}, \dots, μ_{n}$ と並べる。 $H$ の連結成分ごとに $L (H)$ はブロック対角になるので、成分ごとに固有値を求めて合わせればよい。孤立点は固有値 $0$ を 1 つ、1 本の辺は固有値 $0, 2$ を与える。
$L (G)$ の 0 以外の固有値 $n - μ_{2}, \dots, n - μ_{n}$ を使って、 $τ (G) = \frac{1}{n} \prod_{i = 2}^{n} (n - μ_{i})$ を計算する。

例題

完全グラフ $K_{6}$ から、互いに端点を共有しない 2 本の辺を除いたグラフ $G$ の全域木の個数を求めよ。

例題の解答

$G = K_{6} - H$ で、 $n = 6$ です。 $H$ は 2 本の辺が互いに交わらないグラフです。

（手順 4） $H$ を 6 頂点すべてをもつグラフとみなすと、連結成分は「辺 1 本」が 2 つと「孤立点」が 2 つです。辺 1 本のラプラシアン行列は $(1 - 1 - 1 1)$ で、特性多項式は $(1 - λ)^{2} - 1 = λ (λ - 2)$ なので、固有値は $0, 2$ です。孤立点はそれぞれ固有値 $0$ を与えます。 $L (H)$ はこれらのブロックからなるブロック対角行列なので、固有値を重複込みで並べると $0, 0, 0, 0, 2, 2$ です。このうち $μ_{1} = 0$ を 1 つだけ除くと、 $μ_{2}, \dots, μ_{6} = 0, 0, 0, 2, 2$ となります。

（手順 5） $L (G)$ の 0 以外の固有値は $6 - μ_{i}$ より $6, 6, 6, 4, 4$ です。よって
$τ (G) = \frac{1}{6} \cdot 6^{3} \cdot 4^{2} = \frac{216 \cdot 16}{6} = 576.$

（検算）辺を除かない場合はケーリーの公式から $6^{4} = 1296$ です。辺を除くと全域木が減るので、 $576 < 1296$ は妥当です。

答え: $576$

よくある誤り

$\frac{1}{n}$ を掛け忘れて $\prod_{i = 2}^{n} λ_{i}$ をそのまま答えにしてしまう誤り。正しくは $τ (G) = \frac{1}{n} \prod_{i = 2}^{n} λ_{i}$ 。例えば $K_{3}$ では固有値が $0, 3, 3$ なので、 $9$ ではなく $\frac{9}{3} = 3$ が答え。
$H$ の頂点だけで $L (H)$ を作り、孤立点の固有値 $0$ を数え落とす誤り。正しくは $H$ を $n$ 頂点すべてをもつグラフとみなして、重複込みで $n$ 個の固有値をそろえる。例えば $K_{6}$ から辺 1 本を除くときは、 $μ = 0, 0, 0, 0, 0, 2$ から 0 を 1 つだけ除いて $τ = \frac{1}{6} \cdot 6^{4} \cdot 4 = 864$ 。
$μ = 0$ をすべて除いてしまう、あるいは 1 つも除かない誤り。正しくは $1$ に対応する $μ_{1} = 0$ を 1 つだけ除く。0 をすべて除くと $K_{6} - H$ の例で $\frac{1}{6} \cdot 4^{2}$ のような誤った値になり、1 つも除かないと因子 $n$ が 1 つ余分に入る。
$L$ の代わりに $A$ や $D + A$ を使ったり、異なる番号の $i$ 行 $j$ 列を符号を付けずに除いたりする誤り。正しくは $L = D - A$ を使い、同じ番号の $i$ 行 $i$ 列を除く。例えば $K_{4}$ から辺 1 本を除いたグラフでは、1 行 1 列を除いた行列式は $det 2 - 1 0 - 1 3 - 1 0 - 1 2 = 8$ になる。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

行列木定理による全域木の個数

前提

説明

なぜそうしてよいのか

手順

例題

よくある誤り

入口の問題

この技能を使う問題