グラフ同型
概要
グラフ同型（graph isomorphism）とは、2 つのグラフの頂点集合の間の全単射であって、2 頂点が隣接することとその像が隣接することが同値になるもの、またはそのような全単射が存在するという関係のことである。同型なグラフは頂点の名前だけが違い、距離・クリーク数・彩色数などの不変量が等しいが、不変量の一致から同型は従わない。グラフから自分自身への同型（自己同型）は頂点の置換の群をなす。$n$ 個の決まった頂点の上でグラフ $G$ と同型なグラフは $n!/\lvert\operatorname{Aut}G\rvert$ 個あり、このため同型を除いた $n$ 頂点のグラフの個数は $2^{\binom n2}/n!$ 以上 $2^{\binom n2}$ 以下である。閉路グラフ $C_n$ の自己同型群は位数 $2n$ の二面体群である。
2 つのグラフが、頂点の名前を付け替えるだけで一致するとき、両者は同型であるという。同型なグラフは紙の上の描き方が違っても同じ「つながり方」をしており、グラフ理論ではふつう区別しない。この記事では、同型が保つ量（不変量）と保たない量を見分け、グラフから自分自身への同型（自己同型）のなす群を調べる。主な結果は、決まった $n$ 個の頂点の上で与えられたグラフと同型なグラフが $n!$ を自己同型群の位数で割った個数だけあることであり、ここから同型を除いたグラフの個数の評価や、閉路の数え上げが導かれる。
定義
この記事のグラフは、グラフ の記事の定義「グラフの定義」の意味の単純無向グラフ $G=(V,E)$（$E\subset[V]^2$）であり、辺 $\{u,v\}$ を $uv$ と書く。
- グラフ $G=(V,E)$ から $H=(V',E')$ への同型（isomorphism）とは、全単射 $f\colon V\to V'$ であって、任意の $u,v\in V$ について
$$uv\in E\iff f(u)f(v)\in E'$$
となるものをいう。同型が存在するとき $G$ と $H$ は同型であるといい、$G\cong H$ と書く。 - $G$ から $G$ 自身への同型を $G$ の自己同型（automorphism）という。自己同型全体を $\operatorname{Aut}G$ と書き、$G$ の自己同型群という。
- グラフに数・多項式・真偽などを対応させる規則であって、同型なグラフに同じ値を与えるものをグラフ不変量という。
1 は グラフ の記事の定義「グラフの同型」と同じであり、同じ記事の命題「同型の基本性質」で、$\cong$ が反射的・対称的・推移的であること、同型が頂点数・辺数・次数を保つことが示されている（Lev24 Definition 2.1.4、p. 104 も同じ定義である）。同型の条件は「辺を辺に写す」だけでなく「辺でないものを辺でないものに写す」ことも要求する。前者だけを満たす全単射は同型とは限らない（下の反例の表）。
グラフ $G=(V,E)$ の自己同型全体 $\operatorname{Aut}G$ は、写像の合成について $V$ の置換全体のなす群 $\operatorname{Sym}(V)$ の部分群である。
恒等写像は自己同型である。グラフ の記事の命題「同型の基本性質」の 1 の証明により、同型の逆写像と合成は同型なので、自己同型の逆写像と合成は自己同型である。$\square$
自己同型群は BM76 Exercise 1.2.12（pp. 6–7）で $\Gamma(G)$ として導入され、Bog17 Problem 326（p. 131）では頂点の置換で辺集合を辺集合自身に写すものとして述べられている。
直感
同型は「頂点の名札の付け替え」である。付け替えの後で、どの 2 頂点が結ばれているかの一覧が一致すればよい。自己同型は、グラフの形を変えずに頂点を入れ替える操作、つまりグラフの対称性である。対称性の多いグラフは、名札の付け方を変えても同じグラフになることが多いので、名札付きのグラフとしては少ない種類しか現れない。この反比例の関係を正確に述べたのが、この記事の主定理である。2 つのグラフが同型でないことを示すには、同型が保つ量（不変量）が 1 つでも違うことを見せればよい。同型であることを示すには、具体的な付け替えを見せればよい。
例と反例
頂点 $1,2,3,4$ と辺 $12,23,34$ の道 $P_4$ と、同じ頂点で辺が $13,14,24$ のグラフ $H$（$P_4$ の補グラフ）を考える。全単射 $f\colon1\mapsto3,\ 2\mapsto1,\ 3\mapsto4,\ 4\mapsto2$ は、辺 $12,23,34$ を $31,14,42$ に写す。これは $H$ の辺のすべてであり、$f$ は辺でない組 $13,14,24$ を $34,32,12$ に写し、どれも $H$ の辺でない。よって $f$ は $P_4$ から $H$ への同型である。
- 完全グラフ $K_n$ では、どの置換も自己同型なので $\operatorname{Aut}K_n=\operatorname{Sym}(V)$ で、位数は $n!$ である（完全グラフ の記事の命題「自己同型群」）。辺のないグラフ $E_n$ も同じである。
- 道 $P_n$（$n\ge2$、頂点 $1,\dots,n$）の自己同型は恒等写像と左右の反転 $i\mapsto n+1-i$ の 2 つである。次数 $1$ の頂点は両端 $1,n$ だけなので、自己同型は $1$ を $1$ か $n$ に写す。$1$ の行き先を決めると、thm-gi-cycle-aut の証明と同じく、道に沿って順に行き先が決まる。
- 星 $K_{1,3}$ では、中心は次数 $3$ の唯一の頂点なので固定され、3 枚の葉は任意に入れ替えられる。自己同型群の位数は $3!=6$ である。
- 頂点 $a,b,c,d,e,f$ と辺 $ab,bc,cd,de,cf,df$ のグラフでは、自己同型は恒等写像だけである。自己同型は次数を保つので、次数 $1$ の $a,e$、次数 $2$ の $b,f$、次数 $3$ の $c,d$ をそれぞれの組の中で写す。$a$ の隣接頂点 $b$ の次数は $2$、$e$ の隣接頂点 $d$ の次数は $3$ なので、$a$ と $e$ は入れ替わらず、ともに固定される。すると $a,e$ の隣接頂点 $b,d$ も固定され、残りの $c,f$ も次数の組の中で 1 つずつなので固定される。
頂点集合 $\{1,2,3\}$ の上のグラフは、同型を除いて $E_3$、1 本の辺と孤立点、道 $P_3$、$K_3$ の 4 種類である。どれにも 2 頂点を入れ替える自己同型がある（$E_3$ と $K_3$ では任意の互換、辺 $12$ と孤立点 $3$ では $(1\ 2)$、道 $1,2,3$ では $(1\ 3)$）。したがって、位数 $3$ の巡回群 $\{\mathrm{id},(1\ 2\ 3),(1\ 3\ 2)\}$ は、$\{1,2,3\}$ の上のどのグラフの自己同型群にもならない（BM76 Exercise 1.2.12 (e)、p. 7）。ただし、頂点の多いグラフまで許せば、この群と同型な自己同型群をもつグラフがある。実際、任意の有限群はあるグラフの自己同型群と同型になることが知られている（Frucht、1939。BM76 Exercise 1.2.12 (f)、p. 7。この記事では証明しない）。
同型でないグラフの反例の表は、性質の節の最後の「同型の判定」に置く。
性質
同型が保つもの
$f$ をグラフ $G=(V,E)$ から $H=(V',E')$ への同型とする。
- 頂点の列 $v_0,\dots,v_\ell$ が $G$ の歩道・道・閉路であることと、$f(v_0),\dots,f(v_\ell)$ が $H$ の歩道・道・閉路であることは同値である。特に任意の $u,v\in V$ で $d_H(f(u),f(v))=d_G(u,v)$ であり、$f$ は $G$ の連結成分を $H$ の連結成分に写す。
- 任意の $W\subset V$ について、$W$ が $G$ のクリーク（独立集合）であることと $f(W)$ が $H$ のクリーク（独立集合）であることは同値であり、$f$ の制限は誘導部分グラフ $G[W]$ から $H[f(W)]$ への同型である。
- $G$ の頂点彩色 $c$ に対し $c\circ f^{-1}$ は $H$ の頂点彩色である。
したがって、連結成分の個数、直径、閉路の長さの最小値（内周）、三角形の個数、クリーク数 $\omega$、独立数 $\alpha$、彩色数 $\chi$、与えられたグラフ $F$ と同型な誘導部分グラフの個数は、どれもグラフ不変量である。
1：$f$ は全単射なので、$v_i$ が相異なることと $f(v_i)$ が相異なることは同値である。同型の条件により $v_{i-1}v_i\in E\iff f(v_{i-1})f(v_i)\in E'$ である。歩道・道・閉路の定義（グラフ の記事の定義「歩道・道・閉路の定義」）はこの 2 種類の条件だけで書けるので、同値性が従う。$f^{-1}$ も同型なので、$H$ の歩道は $G$ の歩道から来る。よって $u,v$ を結ぶ道の長さの集合と $f(u),f(v)$ を結ぶ道の長さの集合は等しく、最小値である距離も等しい。連結成分は「道で結ばれる」同値関係の同値類なので、$f$ はこれを同値類に写す。
2：$W$ の相異なる 2 頂点がすべて隣接する（すべて隣接しない）ことは、同型の条件によりその像についても同じである。誘導部分グラフについては 誘導部分グラフ の記事の命題「誘導部分グラフの基本性質」の 3 である。
3：$H$ の辺 $xy$ について $f^{-1}(x)f^{-1}(y)\in E$ なので $c(f^{-1}(x))\neq c(f^{-1}(y))$ である。$\square$
このほか、頂点数・辺数・次数列（グラフ の記事の命題「同型の基本性質」）、隣接行列のスペクトル（隣接行列 の記事の定理「同型と置換行列」）もグラフ不変量である。補グラフについては $G\cong H\iff\overline G\cong\overline H$ である（補グラフ の記事の命題「補グラフの基本性質」の 5）。
同型なグラフの個数
有限集合 $V$ を固定し、頂点集合が $V$ のグラフ全体を $\mathcal G(V)$ とする。$\lvert V\rvert=n$ なら $\lvert\mathcal G(V)\rvert=2^{\binom n2}$ である（グラフ の記事の命題「ラベル付きグラフの個数」）。置換 $\sigma\in\operatorname{Sym}(V)$ と $G=(V,E)\in\mathcal G(V)$ に対し、頂点の名前を $\sigma$ で付け替えたグラフを
$$\sigma\cdot G:=\bigl(V,\ \{\sigma(u)\sigma(v)\mid uv\in E\}\bigr)$$
とおく。$\sigma$ は $G$ から $\sigma\cdot G$ への同型であり、$(\sigma\tau)\cdot G=\sigma\cdot(\tau\cdot G)$、$\mathrm{id}\cdot G=G$ が成り立つ。また $\sigma\cdot G=G$ であることは $\sigma\in\operatorname{Aut}G$ と同値である。$\mathcal G(V)$ の中で $G$ と同型なグラフは、ちょうど $\sigma\cdot G$ の形のグラフである（Bog17 Problem 327、p. 131 は、同型を除いたグラフを $\operatorname{Sym}(V)$ のこの働きの軌道として数える）。
$V$ を $n$ 元集合とし、$G\in\mathcal G(V)$ とする。頂点集合が $V$ で $G$ と同型なグラフの個数は
$$\frac{n!}{\lvert\operatorname{Aut}G\rvert}$$
である。
$\mathcal O:=\{H\in\mathcal G(V)\mid H\cong G\}$ とおき、写像 $\Phi\colon\operatorname{Sym}(V)\to\mathcal O$ を $\Phi(\sigma):=\sigma\cdot G$ で定める。$\sigma\cdot G\cong G$ なので $\Phi$ は $\mathcal O$ に値をとる。
$\Phi$ は全射である。$H=(V,E')\in\mathcal O$ とし、同型 $f\colon G\to H$ をとる。$f$ は $V$ の置換である。$uv\in E$ なら $f(u)f(v)\in E'$ であり、逆に $E'$ の元 $xy$ は $x=f(u)$、$y=f(v)$ と書けて、同型の条件から $uv\in E$ である。よって $E'=\{f(u)f(v)\mid uv\in E\}$、すなわち $H=f\cdot G=\Phi(f)$ である。
$\Phi$ の各点の逆像の元の個数は $\lvert\operatorname{Aut}G\rvert$ である。$\sigma,\tau\in\operatorname{Sym}(V)$ について
$$\Phi(\sigma)=\Phi(\tau)\iff\sigma\cdot G=\tau\cdot G\iff(\tau^{-1}\sigma)\cdot G=G\iff\tau^{-1}\sigma\in\operatorname{Aut}G$$
である（2 つ目の同値は両辺に $\tau^{-1}$ または $\tau$ を働かせればよい）。したがって $\Phi(\tau)$ の逆像は $\{\tau\pi\mid\pi\in\operatorname{Aut}G\}$ であり、$\pi\mapsto\tau\pi$ は単射なので、元の個数は $\lvert\operatorname{Aut}G\rvert$ である。
$\operatorname{Sym}(V)$ の $n!$ 個の元は、$\mathcal O$ の各元の逆像に $\lvert\operatorname{Aut}G\rvert$ 個ずつ分かれるので、$n!=\lvert\mathcal O\rvert\cdot\lvert\operatorname{Aut}G\rvert$ である。$\square$
これは群の作用の軌道と固定部分群の関係（群作用）を、グラフの付け替えの場合に直接確かめたものである。対称性の多いグラフほど、名前付きの写しは少ない。
頂点集合 $\{1,2,3,4\}$ の上のグラフは $2^6=64$ 個あり、同型を除くと次の 11 種類に分かれる。各行の個数 $24/\lvert\operatorname{Aut}\rvert$ の和は $64$ になる。
| グラフ | 辺数 | $\lvert\operatorname{Aut}\rvert$ | 名前付きの個数 |
|---|---|---|---|
| $E_4$ | 0 | 24 | 1 |
| 1 本の辺と孤立点 2 個 | 1 | 4 | 6 |
| 道 $P_3$ と孤立点 | 2 | 2 | 12 |
| 2 本の交わらない辺 | 2 | 8 | 3 |
| 三角形と孤立点 | 3 | 6 | 4 |
| 道 $P_4$ | 3 | 2 | 12 |
| 星 $K_{1,3}$ | 3 | 6 | 4 |
| 閉路 $C_4$ | 4 | 8 | 3 |
| 三角形に 1 本の辺を付けたもの | 4 | 2 | 12 |
| $K_4$ から 1 本の辺を除いたもの | 5 | 4 | 6 |
| $K_4$ | 6 | 24 | 1 |
例えば $C_4$ の自己同型は、4 角形の回転 4 個と裏返し 4 個の 8 個であり（thm-gi-cycle-aut）、$\{1,2,3,4\}$ の上の 4 角形は $24/8=3$ 個（向かい合う頂点の組の分け方の数）である。補グラフをとっても $\operatorname{Aut}$ は変わらず、表の上から $k$ 行目と下から $k$ 行目は互いの補グラフである（中央の $P_4$ は自分自身の補グラフと同型）。
$n$ 頂点のグラフの同型類の個数を $g_n$ とすると
$$\frac{2^{\binom n2}}{n!}\le g_n\le2^{\binom n2}$$
である。
$V=\{1,\dots,n\}$ とする。$\mathcal G(V)$ は同型類ごとに分かれ、どの同型類も $\mathcal G(V)$ の元を含む（頂点に $1,\dots,n$ と名前を付ければよい）ので、分かれた組の個数は $g_n$ である。thm-gi-orbit により、各組の元の個数は $n!/\lvert\operatorname{Aut}G\rvert$ で、$1$ 以上 $n!$ 以下である。組の元の個数の和は $2^{\binom n2}$ なので、$g_n\le2^{\binom n2}\le g_n\cdot n!$ である。$\square$
$n!\le n^n=2^{n\log_2n}$ なので、下界の 2 を底とする対数は $\binom n2-n\log_2n$ 以上であり、$\binom n2$ に比べて $n\log_2n$ は小さい。つまり、同型を除いても、$n$ 頂点のグラフの種類の数は名前付きのグラフの数とほぼ同じ速さで増える。実際の値は $g_1,\dots,g_6=1,2,4,11,34,156$ である（計算機で全グラフを分類して得られる値で、この記事では証明しない。$n\le6$ の値は BH11 §14.3.2 の Table 14.1、pdf p. 211 にある。$n=4$ は ex-gi-four-vertices）。
閉路グラフの自己同型
閉路グラフ $C_n$（$n\ge3$）の頂点を $\mathbb{Z}/n\mathbb{Z}$ の元 $0,1,\dots,n-1$ とし、$i$ と $i\pm1$ を辺で結ぶ。
$n\ge3$ とする。$C_n$ の自己同型は、回転 $\rho_j\colon i\mapsto i+j$ と裏返し $\tau_j\colon i\mapsto j-i$（$j\in\mathbb{Z}/n\mathbb{Z}$）の $2n$ 個であり、これらは相異なる。したがって $\lvert\operatorname{Aut}C_n\rvert=2n$ で、$\operatorname{Aut}C_n$ は二面体群と同型である。
$\rho_j,\tau_j$ は $\mathbb{Z}/n\mathbb{Z}$ の全単射で、2 頂点の差 $i-i'$ を $\rho_j$ はそのまま、$\tau_j$ は $-(i-i')$ に写す。2 頂点が隣接することは差が $\pm1$ であることなので、どちらも自己同型である。$\rho_j=\rho_{j'}$ なら $0$ の行き先から $j=j'$、$\tau_j=\tau_{j'}$ も同様である。$\rho_j=\tau_{j'}$ なら、すべての $i$ で $i+j=j'-i$、すなわち $2i=j'-j$ となるが、$i=0,1$ を比べると $2=0$（$\mathbb{Z}/n\mathbb{Z}$ で）となり、$n\ge3$ に反する。よってこれらの $2n$ 個は相異なる。
逆に $\pi\in\operatorname{Aut}C_n$ とする。$C_n$ の各頂点 $i$ の隣接頂点はちょうど 2 個 $i-1,i+1$ で、$n\ge3$ なのでこれらは相異なる。$\pi$ は隣接関係を保つ全単射なので、$\pi(i+1)$ は $\pi(i)$ の隣接頂点のうち $\pi(i-1)$ でない方である。したがって、$\pi(0)$ と $\pi(1)$ を決めると、$i=1,2,\dots$ の順に $\pi(i+1)$ が決まり、$\pi$ 全体が決まる。$\pi(0)$ は $n$ 通り、$\pi(1)$ は $\pi(0)$ の 2 つの隣接頂点のどちらかなので、自己同型は高々 $2n$ 個である。$\square$
thm-gi-orbit と合わせると、$n$ 個の名前付きの頂点の上の閉路（$C_n$ と同型なグラフ）の個数は
$$\frac{n!}{2n}=\frac{(n-1)!}{2}$$
である。$n=4$ では $3$ 個、$n=5$ では $12$ 個である。これは完全グラフ $K_n$ のすべての頂点を 1 回ずつ通る閉路（Hamilton 閉路）の個数でもある。
同型の判定
2 つのグラフが同型でないことは、不変量が 1 つでも違えば分かる。しかし、よく使う不変量をいくつそろえても、それらが一致することから同型は従わない。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 同型の条件の「$\Leftarrow$」（辺を辺に写すだけにする） | $E_2$ から $K_2$ への恒等写像 | 同型 |
| 同型を次数列の一致に弱める | $C_6$ と 2 つの三角形の非交和 | 同型 |
| 同型を頂点数・辺数・次数列・連結性の一致に弱める | 完全二部グラフ $K_{3,3}$ と三角柱 $\overline{C_6}$ | 同型 |
| 同型をスペクトルの一致に弱める | 星 $K_{1,4}$ と $C_4\cup K_1$ | 同型 |
- 頂点 $1,2$ の上の辺のないグラフ $E_2$ から $K_2$ への恒等写像は全単射で、辺を辺に写す（辺がないので条件は空）が、辺でない組 $12$ を辺に写すので同型ではない。辺数が違うので $E_2\not\cong K_2$ である。
- $C_6$ と 2 つの三角形の非交和は、どちらも 6 頂点で各頂点の次数が $2$ である。前者は連結で後者は連結でないので、prop-gi-invariants の 1 により同型でない（次数(グラフ) の記事の例「反例：同じ次数列を持つ非同型なグラフ」）。
- $K_{3,3}$ と三角柱（2 つの三角形の対応する頂点を 3 本の辺で結んだグラフ、補グラフ の記事の例「道 $P_4$ と閉路 $C_6$」）は、どちらも 6 頂点・9 辺の連結な 3-正則グラフである。三角柱は三角形を含むが、$K_{3,3}$ は二部グラフなので三角形を含まない。三角形の個数は不変量なので、同型でない。
- $K_{1,4}$ と $C_4\cup K_1$ は、隣接行列の固有値がどちらも $2,0,0,0,-2$ で等しいが、前者は連結で後者は連結でないので同型でない（隣接行列 の記事の例「同じスペクトルをもつ同型でないグラフ」）。
同型であるかは、隣接行列で言い換えられる。頂点に番号を付けた 2 つのグラフが同型であることは、隣接行列 $A,A'$ についてある置換行列 $P$ で $A'=PAP^{\mathsf T}$ となることと同値である（隣接行列 の記事の定理「同型と置換行列」）。$n$ 頂点の場合、候補の置換は $n!$ 個あり、すべてを調べるのは $n$ が大きいと現実的でない。不変量で候補を絞り込み（次数を保たない対応は除く、など）、残った対応を確かめるのが基本的な方法である。
補足
自己同型群は、グラフの対称性の大きさを測る。どの 2 頂点についても一方を他方に写す自己同型があるグラフを頂点推移的といい（BM76 Exercise 1.2.13、p. 7）、$C_n$、$K_n$、Petersen グラフはその例である。Petersen グラフ（$\{1,\dots,5\}$ の 2 元部分集合を頂点とし、交わらない 2 つを結ぶ）では、$\{1,\dots,5\}$ の置換は 2 元部分集合を 2 元部分集合に、交わらない組を交わらない組に写すので、自己同型を与える。2 元部分集合をすべて固定する置換は恒等写像なので、これで $5!=120$ 個の相異なる自己同型が得られる。
同型は、多重グラフ・有向グラフにも同じ考え方で定められる。多重グラフでは頂点の対応に加えて辺の対応も与え、端点の関係を保つことを要求する（BM76 p. 4 の同型は頂点の全単射と辺の全単射の組である）。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
