代数的グラフ理論(algebraic graph theory)とは、グラフを隣接行列・Laplacian 行列・自己同型群・彩色多項式などの代数的な対象に写し、その性質からグラフの性質を調べる分野である。固有値による連結性や彩色数の評価、全域木の個数の行列式による計算、強正則グラフや Cayley グラフの研究が主な主題である。たとえば $K_{10}$ の辺を 3 つの Petersen グラフに分けることは、2 つの 5 次元の固有空間が 9 次元の空間の中で交わることから不可能と分かる。一方、スペクトルが同じでも同型でないグラフがあり、代数的な不変量はグラフを完全には決めない。
代数的グラフ理論(algebraic graph theory)とは、グラフを行列・群・多項式などの代数的な対象に写し、その代数の性質からグラフの性質を調べる分野である。中心の問いは、固有値や自己同型群からグラフの何が読み取れるか、代数的な条件を満たすグラフはどれだけあるか、数えたい量や分解の可能性を代数の計算で決められるか、である。
この記事は分野の地図である。主な問いと代表的な結果を表にして、それぞれの記事へ案内する。続いて、代数がグラフの問題を解く典型として、立方体グラフの固有値と全域木の個数の計算、および $K_{10}$ が 3 つの Petersen グラフに分解できないことの証明を示す。
この記事では、グラフは有限の単純グラフとする。グラフ $G=(V,E)$ に結びつける代数的な対象は主に 3 種類ある。
グラフ $G$ の 自己同型 とは、頂点集合の全単射 $\pi\colon V\to V$ で、$\{u,v\}\in E$ と $\{\pi(u),\pi(v)\}\in E$ が同値であるものをいう。自己同型の全体は合成について群をなし、これを 自己同型群 $\mathrm{Aut}(G)$ という。任意の 2 頂点 $u,v$ に $\pi(u)=v$ となる $\pi\in\mathrm{Aut}(G)$ があるとき、$G$ は 頂点推移的 であるという。
行列と群は次のようにつながる。$\pi$ の置換行列を $P$ とすると、$\pi$ が自己同型であることは $PA=AP$ と同値である。したがって $\mathrm{Aut}(G)$ は $A$ の各固有空間に作用し、固有空間は $\mathrm{Aut}(G)$ の表現になる。可換な群を使って定義したグラフでは、下の prop-agt-cube のように、群の指標が固有ベクトルを与える。
| 問い | 代表的な結果 | 入る記事 |
|---|---|---|
| 固有値から形が分かるか | 連結グラフの相異なる固有値の個数は直径 $+1$ 以上である。連結グラフが二部であることは、スペクトルが $0$ について対称であることと同値である | 隣接行列 |
| 固有値で数を評価できるか | 彩色数は最大固有値 $\lambda_1$ について $1+\lfloor\lambda_1\rfloor$ 以下である(Wilf の定理) | スペクトルグラフ理論 |
| 全域木はいくつあるか | 全域木の個数は $\frac1n\mu_2\cdots\mu_n$ である($\mu_i$ は Laplacian 行列の $0$ でない固有値) | 行列木定理 |
| 固有値でつながり方が分かるか | 代数的連結度が正であることは連結であることと同値で、Cheeger 定数は $\mu_2$ で上下から評価される | Laplacian行列、Cheegerの不等式(グラフ) |
| 固有値の少ないグラフは何か | 強正則グラフの固有値と重複度はパラメータで決まり、三角形も四角形もない連結なものの頂点数は $5,10,50,3250$ のどれかである | 強正則グラフ、距離正則グラフ |
| 関係の行列はどんな代数をなすか | アソシエーションスキームの関係の行列は可換な Bose–Mesner 代数を張る | アソシエーションスキーム |
| 群からどんなグラフが作れるか | 自己同型群が頂点の上に正則に作用する部分群をもつグラフは Cayley グラフに限る | Cayleyグラフ、Paleyグラフ |
| 良くつながった疎なグラフはあるか | 連結な $d$-正則グラフで $d$ 以外の固有値の絶対値が $2\sqrt{d-1}$ 以下のものが Ramanujan グラフで、固有値の限界の意味で最良のエクスパンダーである | エクスパンダーグラフ、Ramanujanグラフ |
| 分解に何個要るか | $K_n$ の辺を完全二部グラフに分けるには $n-1$ 個以上要る(行列の階数の議論による) | Graham–Pollakの定理 |
| 塗り方の個数は何の関数か | 彩色多項式は削除縮約の公式 $P_G=P_{G-e}-P_{G/e}$ を満たす | 彩色多項式、Tutte多項式 |
頂点が $\{0,1\}^n$ で、1 成分だけ異なる 2 頂点を辺で結んだグラフを $n$ 次元の 立方体グラフ $Q_n$ という。これは群 $(\mathbb{Z}/2\mathbb{Z})^n$ の Cayleyグラフ である(生成系は単位ベクトル $e_1,\dots,e_n$)。
$Q_n$ の固有値は $n-2k$($k=0,1,\dots,n$)で、$n-2k$ の重複度は $\binom nk$ である。
$a\in\{0,1\}^n$ に対し、$\chi_a(x):=(-1)^{a\cdot x}$($a\cdot x=\sum_ia_ix_i$)で関数 $\chi_a\colon\{0,1\}^n\to\{\pm1\}$ を定める。$a$ の成分の $1$ の個数を $k$ とすると、隣接行列 $A$ について
$$
(A\chi_a)(x)=\sum_{i=1}^n\chi_a(x+e_i)=\sum_{i=1}^n(-1)^{a_i}\chi_a(x)=(n-2k)\chi_a(x)
$$
である。$2^n$ 個の $\chi_a$ は相異なる群の指標なので互いに直交し、$\mathbb{R}^{\{0,1\}^n}$ の基底をなす。よって固有値は $n-2k$ で尽き、重複度は成分の $1$ が $k$ 個の $a$ の個数 $\binom nk$ である。$\square$
この結果は Sta13 Corollary 2.4(p. 25)にある。同じ計算は有限アーベル群の Cayley グラフ全体に通用する。生成系を $S$ とすると、群の各指標 $\chi$ は固有値 $\sum_{s\in S}\chi(s)$ の固有ベクトルで、指標の全体でスペクトルが尽きる(BH11 §1.4.9、p. 11)。グラフの形を見なくても、群の計算だけで固有値が書ける。
$Q_3$ は $3$-正則なので $L=3I-A$ で、Laplacian 行列の固有値は $3-(3-2k)=2k$、すなわち $0,2,2,2,4,4,4,6$ である。行列木定理 により全域木の個数は
$$
\frac18\cdot2^3\cdot4^3\cdot6=384
$$
である。辺 12 本から 7 本を選ぶ $\binom{12}{7}=792$ 通りを調べなくても、固有値だけで答えが出る。
$K_{10}$ は辺が 45 本で各頂点の次数が 9、Petersen グラフは辺が 15 本で各頂点の次数が 3 である。個数の上では $K_{10}$ の辺を 3 つの Petersen グラフに分けられそうに見えるが、できない。証明は 2 つの固有空間の次元を数えるだけである。
$K_{10}$ の辺集合を 3 つに分け、それぞれが Petersenグラフ と同型なグラフ(頂点集合は 10 個すべて)をなすようにすることはできない。
そのような分割があるとし、3 つのグラフの隣接行列を $P_1,P_2,P_3$ とする。すべての成分が $1$ の行列を $J$ として $P_1+P_2+P_3=J-I$ である。Petersen グラフのスペクトルは $3,1^{(5)},(-2)^{(4)}$(肩は重複度)であり(Petersenグラフ)、同型なグラフのスペクトルは等しい。
Petersen グラフは $3$-正則で連結なので、固有値 $3$ の固有空間はすべての成分が $1$ のベクトル $\mathbf{1}$ で張られる。実対称行列の異なる固有値の固有ベクトルは直交するので、$P_1,P_2$ の固有値 $1$ の固有空間 $V_1,V_2$ は、どちらも 5 次元で $\mathbf{1}^{\perp}$(9 次元)に含まれる。よって
$$
\dim(V_1\cap V_2)\ge5+5-9=1
$$
であり、$0$ でない $u\in V_1\cap V_2$ がとれる。$u\perp\mathbf{1}$ なので $Ju=0$ であり、
$$
P_3u=(J-I-P_1-P_2)u=-u-u-u=-3u
$$
となる。これは $-3$ が $P_3$ の固有値であることを意味するが、Petersen グラフの固有値は $3,1,-2$ だけなので矛盾である。$\square$
この証明は BH11 §1.5.1(p. 12)による。組合せの場合分けを 1 つも使わず、「$5+5> 9$」だけが効いている。
代数的な不変量はグラフのすべてを覚えているわけではない。
| 主張 | 反例 | 確かめ |
|---|---|---|
| 同じスペクトルのグラフは同型である | $K_{1,4}$ と、$C_4$ に孤立点を加えたグラフ | どちらもスペクトルは $2,0,0,0,-2$(隣接行列)。一方は連結で他方は連結でないので同型でない |
| 隣接行列のスペクトルから連結性が分かる | 同じ組 | スペクトルが同じで連結性が違う。Laplacian 行列のスペクトルなら連結成分の個数が分かる(Laplacian行列) |
| 頂点推移的なグラフは Cayley グラフである | Petersen グラフ | 頂点推移的だが Cayley グラフでない(Cayleyグラフ) |
逆向きに、スペクトルで決まるグラフもある。$K_n$ や $C_n$ はスペクトルで同型類まで決まる(BH11 Proposition 14.4.4、p. 204)。
| 段階 | 記事 | 身につくこと |
|---|---|---|
| 1. 行列 | 隣接行列 → Laplacian行列 → 行列木定理 | 歩道・連結性・全域木と固有値の関係 |
| 2. 固有値の評価 | スペクトルグラフ理論 → Cheegerの不等式(グラフ) → エクスパンダーグラフ → Ramanujanグラフ | 固有値で組合せの量を抑える方法 |
| 3. 正則性の強いグラフ | 強正則グラフ → 距離正則グラフ → アソシエーションスキーム | 固有値の少ないグラフの分類 |
| 4. 群 | Cayleyグラフ、Paleyグラフ | 群から作るグラフと、その固有値の計算 |
| 5. 多項式 | 彩色多項式 → Tutte多項式 | 削除縮約で定まる不変量 |
段階 1 のあと、段階 2・3・4・5 は互いに独立に読める。段階 3 と 4 は Paleyグラフ や軌道によるスキームでつながる。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する