スペクトルグラフ理論
概要
スペクトルグラフ理論（spectral graph theory）とは、グラフの隣接行列や Laplacian 行列の固有値と固有ベクトルによってグラフの性質を調べる数学の分野である。固有値は頂点の番号の付け方によらない不変量で、辺や三角形の個数、二部グラフであるか、連結成分の個数などを与え、独立数・彩色数・連結度・Cheeger 定数などを上下から評価するが、同じスペクトルをもつ同型でないグラフもある。たとえば彩色数は隣接行列の最大固有値 $\lambda_1$ について $1+\lfloor\lambda_1\rfloor$ 以下である（Wilf の定理）。強正則グラフ、エクスパンダーグラフ、Ramanujan グラフなど、固有値に特徴のあるグラフの構成と分類も主な主題である。
スペクトルグラフ理論（spectral graph theory）は、グラフに付随する行列、とくに 隣接行列 と Laplacian行列 の固有値と固有ベクトルを使って、グラフの性質を調べる数学の分野である。グラフは頂点と辺の組み合わせ的な対象だが、行列にすると線形代数の道具がそのまま使える。固有値は頂点の番号の付け方によらないので、グラフの同型で変わらない量（不変量）になり、しかも計算しやすい。
たとえば、隣接行列の冪の成分は歩道の個数を数え（隣接行列と道の数）、その結果、固有値から辺の本数と三角形の個数が決まる。Laplacian 行列の固有値 $0$ の重複度は連結成分の個数に等しく、2 番目に小さい固有値はグラフが「どれだけよくつながっているか」を測る。一方で、同じ固有値をもつ同型でないグラフもあるので、固有値だけでグラフが決まるわけではない。
この記事では、まず分野の対象を定義し、主な問いと代表的な定理を、それを扱う記事とともに一覧にする。続いて代表例として、彩色数が最大固有値で上から抑えられること（Wilf の定理）を完全に証明し、仮定を替えた反例を示す。最後に、学ぶ順に記事を並べた道筋を示す。
定義
この記事では、グラフは有限の単純グラフ（ループも多重辺もない）とし、頂点を $v_1,\dots,v_n$、頂点 $v$ の次数を $d_v$ とする。
グラフ $G$ の 隣接行列 $A$ は、$v_i$ と $v_j$ が隣接すれば $(i,j)$ 成分が $1$、そうでなければ $0$ の $n$ 次正方行列である。次数を並べた対角行列を $D$ として、$L:=D-A$ を Laplacian 行列 という。$A$ の固有値を重複度をこめて並べたものを $G$ の スペクトル、$L$ の固有値を並べたものを Laplacian スペクトル という。同型でない 2 つのグラフのスペクトルが等しいとき、それらは 同スペクトル（cospectral）であるという。
スペクトルグラフ理論 とは、グラフの性質を、これらの行列の固有値と固有ベクトルによって調べる数学の分野である。
$A$ と $L$ は実対称行列なので、固有値はすべて実数であり、固有ベクトルからなる正規直交基底がある（スペクトル定理）。頂点の番号を付け替えると $A$ は置換行列 $P$ で $P^{\mathsf T}AP$ に変わるが、固有値は変わらない（隣接行列 の定理「同型と置換行列」）。したがってスペクトルはグラフの同型不変量である。以下、隣接行列の固有値を $\lambda_1\ge\lambda_2\ge\dots\ge\lambda_n$、Laplacian 行列の固有値を $0=\mu_1\le\mu_2\le\dots\le\mu_n$ と並べる。$d$-正則グラフでは $L=dI-A$ なので $\mu_i=d-\lambda_i$ であり、2 つのスペクトルは同じ情報をもつ。
固有値は、次の Rayleigh 商 の最大・最小として現れる。実対称行列 $M$ の最大固有値は $0$ でない $x$ についての $x^{\mathsf T}Mx/x^{\mathsf T}x$ の最大値であり（隣接行列 の補題「Rayleigh 商による最大固有値」）、ほかの固有値も最大と最小の組み合わせで表される（固有値の交錯定理 の定理「Courant–Fischer の定理」）。$x^{\mathsf T}Ax=2\sum_{v_iv_j\in E}x_ix_j$ と $x^{\mathsf T}Lx=\sum_{v_iv_j\in E}(x_i-x_j)^2$ は辺についての和なので、適当な $x$ を選ぶと、グラフの組み合わせ的な量と固有値を比べる不等式が得られる。スペクトルグラフ理論の多くの定理はこの形で証明される。
スペクトルグラフ理論の主な問い
- スペクトルから何が読み取れるか。 頂点の個数、辺の本数、三角形の個数、二部グラフであるかどうか、正則であるかどうか、（Laplacian スペクトルからは）連結成分の個数はスペクトルで決まる。連結グラフの直径は、相異なる固有値の個数から $1$ を引いた数以下である。
- 固有値で組み合わせ的な量を評価する。 独立数、彩色数、連結度、2 つに分けるときに切る辺の本数（Cheeger 定数）、直径などを、固有値で上下から評価する。
- スペクトルはグラフを決めるか。 同スペクトルで同型でないグラフの例を作り、どのようなグラフならスペクトルで決まるかを問う。
- 固有値が特別なグラフを作り、分類する。 相異なる固有値が少ないグラフ（強正則グラフ・距離正則グラフ）や、2 番目の固有値が小さいグラフ（エクスパンダー・Ramanujan グラフ）を構成し、分類する。
代表的な定理
| 定理 | 主張の要点 | 記事 |
|---|---|---|
| 隣接行列の冪と歩道 | $A^k$ の $(i,j)$ 成分は長さ $k$ の歩道の個数で、$\operatorname{tr}A^2=2\lvert E\rvert$、$\operatorname{tr}A^3=6\cdot$（三角形の個数） | 隣接行列と道の数, 隣接行列 |
| 最大固有値と次数 | 平均次数 $\le\lambda_1\le$ 最大次数で、$d$-正則なら $\lambda_1=d$ | 隣接行列 |
| 二部グラフの判定 | 連結なグラフが二部グラフであることと、$-\lambda_1$ が固有値であることは同値 | 隣接行列 |
| Perron–Frobenius の定理 | 既約な非負行列の最大固有値は単純で、正の固有ベクトルをもつ | Perron–Frobeniusの定理 |
| 固有値の交錯定理 | 誘導部分グラフの固有値は元のグラフの固有値と交錯する | 固有値の交錯定理 |
| Hoffman の上界 | $k$-正則グラフ（$k\ge1$）の独立数は $n(-\lambda_n)/(k-\lambda_n)$ 以下 | 正則グラフ |
| 連結成分と Laplacian | 固有値 $0$ の重複度は連結成分の個数で、完全グラフでなければ $\mu_2\le$ 頂点連結度 | Laplacian行列 |
| 行列木定理 | 全域木の個数は $\frac1n\mu_2\cdots\mu_n$ | 行列木定理 |
| 強正則グラフの固有値 | 連結で完全でなければ相異なる固有値は 3 個で、パラメータから決まる | 強正則グラフ |
| Cheeger の不等式 | $\mu_2/2\le h(G)\le\sqrt{2\Delta\mu_2}$ | Cheegerの不等式(グラフ) |
| エクスパンダー混合補題・Alon–Boppana | $\lambda$ が小さいと辺の分布は無作為に近く、$\lambda$ は $2\sqrt{d-1}$ より本質的に小さくできない | エクスパンダーグラフ |
スペクトルがグラフを決めない例として、星 $K_{1,4}$ と、閉路 $C_4$ に孤立点を加えたグラフは、どちらもスペクトル $2,0,0,0,-2$ をもつが同型でない（隣接行列 の例「同じスペクトルをもつ同型でないグラフ」）。前者は連結で後者は連結でないので、連結性は隣接行列のスペクトルからは決まらない。Laplacian スペクトルはこの 2 つを区別する（Laplacian行列 の節「反例と注意」）。
スペクトルから決まる量
問い 1 についてわかっていることを、既存の記事の定理を組み合わせてまとめる。
$G$ を頂点が $n\ge1$ 個のグラフとし、隣接行列のスペクトル $\lambda_1\ge\dots\ge\lambda_n$ が与えられているとする。このとき次が決まる。
- 頂点の個数 $n$、辺の本数 $\frac12\sum_i\lambda_i^2$、三角形の個数 $\frac16\sum_i\lambda_i^3$。
- $G$ が二部グラフであるかどうか（スペクトルが $0$ について対称であるかどうか）。
- $G$ が正則であるかどうか（$\lambda_1$ が平均次数 $\frac1n\sum_i\lambda_i^2$ に等しいかどうか）と、正則な場合の次数 $\lambda_1$ と連結成分の個数（$\lambda_1$ の重複度）。
1：$\operatorname{tr}A^k=\sum_i\lambda_i^k$（トレースと固有値）であり、$\operatorname{tr}A^2$ は辺の本数の $2$ 倍、$\operatorname{tr}A^3$ は三角形の個数の $6$ 倍である（隣接行列と道の数 の命題「閉じた道筋の数と辺・三角形の数」）。2：隣接行列 の定理「スペクトルによる二部グラフの判定」の 2。3：平均次数は $2\lvert E\rvert/n$ で、1 により決まる。正則であることと $\lambda_1$ が平均次数に等しいことの同値は 正則グラフ の命題「固有値による正則性の判定」であり、正則なら次数は $\lambda_1$ で、$\lambda_1$ の重複度は連結成分の個数に等しい（隣接行列 の定理「最大固有値と次数」の 3）。$\square$
正則でないグラフでは連結性はスペクトルから決まらない（上の $K_{1,4}$ の例）。また、彩色数や独立数のようにスペクトルから決まらない量でも、固有値で上下から挟めることが多い。次の例はその様子を 1 つのグラフで見る。
Petersen グラフ $P$ の隣接行列のスペクトルは $3,1^{(5)},(-2)^{(4)}$（右肩は重複度）、Laplacian スペクトルは $0,2^{(5)},5^{(4)}$ である（隣接行列 の例「Petersen グラフの隣接行列」、Laplacian行列 の表）。スペクトルだけから次がわかる。
- 辺と三角形． 辺は $\frac12(9+5\cdot1+4\cdot4)=15$ 本、三角形は $\frac16(27+5-4\cdot8)=0$ 個である。
- 正則・連結・二部． 平均次数は $30/10=3=\lambda_1$ なので $3$-正則で、$\lambda_1$ が単純なので連結である。$-3$ が固有値でないので二部グラフでない。
- 直径． 相異なる固有値は 3 個なので、直径は $2$ 以下である（隣接行列 の定理「直径と相異なる固有値の個数」）。
- 独立数と彩色数． Hoffman の上界から独立数は $10\cdot2/(3+2)=4$ 以下である。次の節の Wilf の定理（thm-sgt-wilf）から $\chi\le4$、各色の頂点が独立集合をなすことから $\chi\ge10/4$、すなわち $\chi\ge3$ である。
- 全域木と Cheeger 定数． 全域木の個数は $\frac1{10}\cdot2^5\cdot5^4=2000$ である（行列木定理）。Cheeger 定数は $\mu_2/2=1$ 以上であり、実際に $1$ である（Cheegerの不等式(グラフ) の例「等号に近い例と遠い例」）。
実際、Petersen グラフの独立数は $4$（正則グラフ の例「上界の計算」）、彩色数は $3$ で（彩色数 の例「Petersen グラフの彩色数」）、スペクトルからの評価はどれも正確か、ほぼ正確である。
代表例：彩色数と最大固有値
グラフの頂点に色を塗り、隣接する頂点が違う色になるようにするとき、必要な色の個数の最小値が 彩色数 $\chi(G)$ である。頂点を 1 つずつ順に塗れば、各頂点の隣接頂点は最大次数 $\Delta$ 個以下なので、$\Delta+1$ 色で塗れる。次の定理は、$\Delta$ を最大固有値 $\lambda_1$ に置き換えてよいことを示す。$\lambda_1\le\Delta$ なので（隣接行列 の定理「最大固有値と次数」）、これは改良であり、次数のばらつきが大きいグラフでは大幅な改良になる。証明は、固有値を Rayleigh 商として扱う典型的な議論である。
$H$ がグラフ $G$ の部分グラフ（頂点も辺も $G$ のものの一部）で、頂点を 1 個以上もつなら、$\lambda_1(H)\le\lambda_1(G)$ である。
$H$ の頂点集合を $W$、$H$ と $G$ の隣接行列を $A_H$、$A_G$ とする。$A_Hx=\lambda_1(H)x$、$x^{\mathsf T}x=1$ となる実ベクトル $x\in\mathbb R^W$ をとり、各成分の絶対値を並べたベクトルを $\lvert x\rvert$ とする。$A_H$ の成分は $0$ 以上なので
$$
\lambda_1(H)=x^{\mathsf T}A_Hx=\sum_{i,j\in W}(A_H)_{ij}x_ix_j\le\sum_{i,j\in W}(A_H)_{ij}\lvert x_i\rvert\lvert x_j\rvert
$$
である。$\lvert x\rvert$ の成分を $W$ の外で $0$ として $y\in\mathbb R^V$ を作る。$H$ の辺は $G$ の辺なので $i,j\in W$ で $(A_H)_{ij}\le(A_G)_{ij}$ であり、右辺は $\sum_{i,j\in W}(A_G)_{ij}y_iy_j=y^{\mathsf T}A_Gy$ 以下である。$y^{\mathsf T}y=1$ なので、隣接行列 の補題「Rayleigh 商による最大固有値」により $y^{\mathsf T}A_Gy\le\lambda_1(G)$ である。$\square$
頂点を 1 個以上もつ有限単純グラフ $G$ について、$\lambda_1$ を隣接行列の最大固有値とすると
$$
\chi(G)\ \le\ 1+\lfloor\lambda_1\rfloor
$$
である。
$k:=\lfloor\lambda_1(G)\rfloor$ とおく。$G$ の部分グラフ $H$ で頂点を 1 個以上もつものをとり、その最小次数を $\delta(H)$、平均次数を $\overline d(H)$ とする。最小値は平均以下なので $\delta(H)\le\overline d(H)$ であり、隣接行列 の定理「最大固有値と次数」の 1 により $\overline d(H)\le\lambda_1(H)$ である。lem-sgt-subgraph と合わせて $\delta(H)\le\lambda_1(G)$ であり、$\delta(H)$ は整数なので $\delta(H)\le k$ である。
すべての部分グラフの最小次数が $k$ 以下なので、彩色数 の命題「部分グラフの最小次数による上界」により $\chi(G)\le k+1$ である。$\square$
引いた命題の証明の考え方を開く
最小次数が $k$ 以下の頂点 $v$ を除き、残りのグラフでも同じことを繰り返して頂点を並べる。並べた順の逆に色を塗ると、各頂点を塗るときにすでに塗られた隣接頂点は $k$ 個以下なので、$k+1$ 色のうちどれかが使える。
この定理は、連結なグラフについての $\chi(G)\le1+\lambda_1$ の形で BH11 Proposition 3.6.1（p. 40）に Wilf の定理としてあり（$\chi(G)$ は整数なので $\lambda_1$ を $\lfloor\lambda_1\rfloor$ に替えてよく、連結でないグラフには連結成分ごとに当てはめればよい）、連結なグラフで等号が成り立つのは完全グラフと奇数長の閉路に限ることも述べている（この記事では等号の場合を証明しない）。
- 完全グラフ $K_n$． $\lambda_1=n-1$ なので上界は $n$ で、$\chi(K_n)=n$ と一致する。
- 奇数長の閉路 $C_{2m+1}$． $2$-正則なので $\lambda_1=2$、上界は $3$ で、$\chi=3$ と一致する。
- 星 $K_{1,n-1}$． $\lambda_1=\sqrt{n-1}$（隣接行列 の例「完全グラフと完全二部グラフ」）なので上界は $1+\lfloor\sqrt{n-1}\rfloor$ である。$\Delta+1=n$ よりずっと小さいが、実際の値 $\chi=2$ よりはまだ大きい。
- Petersen グラフ． $\lambda_1=3$ なので上界は $4$ で、実際は $\chi=3$ である（彩色数 の例「Petersen グラフの彩色数」）。
彩色数の下界も固有値で与えられる。辺をもつグラフについて $\chi(G)\ge1-\lambda_1/\lambda_n$ である（Hoffman。BH11 Theorem 3.6.2、p. 40。この記事では証明しない）。$k$-正則グラフでは、これは 正則グラフ の定理「Hoffman の比の上界」と、各色の頂点が独立集合をなすことから直ちに従う。
固有ベクトルの使い方
固有値だけでなく、固有ベクトルもグラフの形を映す。連結なグラフの隣接行列の最大固有値の固有ベクトルは、成分がすべて正にとれ（Perron–Frobeniusの定理）、頂点の「中心らしさ」の尺度として使われる。Laplacian 行列の 2 番目の固有値の固有ベクトル（Fiedler ベクトル）の成分で頂点を並べ、値の大きい頂点から順に集めた集合のうち切る辺の比が最小のものをとると、Cheeger 定数に近い分け方が得られる（Cheegerの不等式(グラフ) の定理「グラフの Cheeger の不等式」）。$d$-正則グラフの上のランダムウォークでは、推移行列 $A/d$ の固有値 $\lambda_i/d$（$i\ge2$）の絶対値が $1$ より小さいほど、一様分布へ速く近づく（エクスパンダーグラフ）。
反例：仮定を替えると崩れること
| 外す条件・替える条件 | 反例 | 成り立たなくなること |
|---|---|---|
| $\lambda_1$ を平均次数 $\overline d$ に替える | 完全グラフ $K_5$ と孤立点 $15$ 個の非交和 | $\overline d=1$ で $1+\overline d=2$ だが、$\chi=5$ |
| $\lambda_1$ を 2 番目の固有値 $\lambda_2$ に替える | 完全グラフ $K_n$（$n\ge2$） | $\lambda_2=-1$ で $1+\lfloor\lambda_2\rfloor=0$ だが、$\chi=n$ |
| 上界を下界に替える（$\chi\ge1+\lfloor\lambda_1\rfloor$） | 星 $K_{1,4}$ | $\lambda_1=2$ で $1+\lfloor\lambda_1\rfloor=3$ だが、$\chi=2$ |
各行の確認を開く
1 行目：頂点は $20$ 個、辺は $K_5$ の $10$ 本なので $\overline d=20/20=1$ である。$K_5$ を含むので $\chi\ge5$ であり、$5$ 色で塗れるので $\chi=5$ である。$\lambda_1=4$ なので Wilf の上界 $5$ は成り立つ。
2 行目：$K_n$ の固有値は $n-1$ と $-1$（重複度 $n-1$）なので、$n\ge2$ で $\lambda_2=-1$ である。
3 行目：$K_{1,4}$ の固有値は $\pm2$ と $0$ で、二部グラフなので $\chi=2$ である。
学ぶ順の道筋
スペクトルグラフ理論は、次の順に記事をたどると学べる。各段の記事は、前の段の定義と定理を使う。
- 準備：グラフ・次数(グラフ)・連結グラフ・二部グラフ、線形代数の 固有値・対称行列・スペクトル定理・トレースと固有値。
- 隣接行列：隣接行列と道の数 → 隣接行列 → 正則グラフ → Perron–Frobeniusの定理。
- 固有値の評価：固有値の交錯定理（Courant–Fischer の定理と交錯）→ 正則グラフ の Hoffman の上界、彩色数・独立集合 との関係（この記事の Wilf の定理）。
- Laplacian 行列：Laplacian行列（代数的連結度）→ 行列木定理 → 連結度(グラフ)。
- 固有値の少ないグラフ：強正則グラフ → 距離正則グラフ。例として Petersenグラフ・Paleyグラフ・Cayleyグラフ。
- 拡大性：Cheegerの不等式(グラフ) → エクスパンダーグラフ（混合補題、Alon–Boppana の評価、Ramanujan グラフ）。
2 と 3 は隣接行列の固有値、4 以降は Laplacian 行列の固有値と 2 番目の固有値が中心になる。上の代表例は、2 の最大固有値の性質だけで証明できる。
歴史
グラフの行列を使う考え方は、全域木の個数を Laplacian 行列の小行列式で表す Kirchhoff の仕事にさかのぼる（行列木定理）。固有値と彩色数を結ぶ Wilf の定理は 1967 年、代数的連結度を導入した Fiedler の論文は 1973 年に発表された。1980 年代には、2 番目の固有値とグラフの拡大性の関係（Alon、1986 年）や、Ramanujan グラフの構成（Lubotzky–Phillips–Sarnak、1988 年）が得られた（年は BH11 の文献表による）。
関連項目
- 前提: グラフ, 隣接行列, 固有値, 対称行列
- 基本の記事: 隣接行列と道の数, Laplacian行列, Perron–Frobeniusの定理, 固有値の交錯定理
- 定理: 行列木定理, Cheegerの不等式(グラフ), 正則グラフ
- 特別なグラフ: 強正則グラフ, 距離正則グラフ, エクスパンダーグラフ
- 応用: 彩色数, 独立集合, ランダムウォーク
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
