1-1 同型・部分グラフ・補グラフ
描き方と頂点名は本質ではない
同じ交通網を紙の上で違う形に描き、町へ違う名前を付けても、どの町どうしが結ばれているかが保存されていれば同じgraphです。その「同じ」を全単射として定義します。
部分graph・誘導部分graph・補graphは次のように定義されます。本章では、それらの構成が頂点名の付け替えと両立することを証明し、同型を否定する不変量、同型を構成する具体的方法、自己同型が数え上げへ与える影響まで進みます。
graph同型
単純graph $G,H$ の間のグラフ同型|graph同型とは、全単射
$$
\varphi:V(G)\longrightarrow V(H)
$$
で、任意の相異なる $u,v\in V(G)$ に対して
$$
uv\in E(G)
\quad\Longleftrightarrow\quad
\varphi(u)\varphi(v)\in E(H)
$$
を満たすものをいう。
同型が存在するとき $G\cong H$ と書く。
条件は辺を辺へ送るだけでなく、非辺も非辺へ送ることを要求しています。全単射であり辺数が等しい場合には「辺を辺へ送る」だけから逆向きも従いますが、定義では最初から同値として書く方が安全です。
有限単純graph全体で、同型関係 $\cong$ は反射的・対称的・推移的である。
恒等写像 $\operatorname{id}_{V(G)}$ は隣接関係をそのまま保つので $G\cong G$ です。
$\varphi:G\to H$ が同型なら全単射なので逆写像 $\varphi^{-1}:V(H)\to V(G)$ があります。定義の同値を逆向きに読めば、$\varphi^{-1}$ も隣接・非隣接を保ちます。従って $G\cong H$ なら $H\cong G$ です。
$\varphi:G\to H$ と $\psi:H\to K$ が同型なら、合成 $\psi\circ\varphi$ は全単射です。また
$$
uv\in E(G)
\Longleftrightarrow
\varphi(u)\varphi(v)\in E(H)
\Longleftrightarrow
\psi(\varphi(u))\psi(\varphi(v))\in E(K).
$$
従って合成も同型で、推移律が成り立ちます。□
同型が保存する量
$\varphi:G\to H$ が同型なら、各 $v\in V(G)$ に対して
$$
\varphi(N_G(v))=N_H(\varphi(v))
$$
であり、
$$
\deg_G(v)=\deg_H(\varphi(v)).
$$
$u\in N_G(v)$ であることは $uv\in E(G)$ と同値です。同型の定義から、これは
$$
\varphi(u)\varphi(v)\in E(H),
$$
すなわち $\varphi(u)\in N_H(\varphi(v))$ と同値です。$\varphi$ は全単射なので近傍どうしを全単射に移し、その要素数である次数も等しくなります。□
$\varphi:G\to H$ が同型なら、頂点列
$$
v_0,v_1,\ldots,v_k
$$
が $G$ のwalk、trail、path、cycleであることと
$$
\varphi(v_0),\varphi(v_1),\ldots,\varphi(v_k)
$$
が $H$ で同じ種類の列であることは同値である。従って連結性、連結成分数、各cycle長は同型で保存される。
連続する二頂点が隣接するという条件は、同型によって前後同値に保存されます。$\varphi$ は単射なので、頂点の一致・相異なりも保存します。また辺 $uv$ は辺 $\varphi(u)\varphi(v)$ へ一対一に移るので、辺の重複の有無も保存されます。従ってwalk、trail、path、cycleの各定義条件がすべて保存されます。
$u$ から $v$ へのpathは $\varphi(u)$ から $\varphi(v)$ へのpathへ移り、逆写像で逆向きも従います。従って同じ連結成分に属する関係が保存され、成分数も保存されます。□
同様に、辺数、次数列、三角形数、長さ $k$ のcycle数、clique数、独立集合数、彩色数などは同型不変量です。
graph $G$ に値 $I(G)$ を対応させ、$G\cong H$ なら必ず
$$
I(G)=I(H)
$$
となるものをグラフ不変量|graph不変量という。
不変量が異なれば非同型だと直ちに分かります。しかし一つ、あるいはいくつかの不変量が一致しても、同型とは限りません。
同じ次数列でも非同型
$K_{3,3}$ と三角柱graphは、ともに6頂点3-正則です。しかし $K_{3,3}$ は二部graphなので三角形をもちません。三角柱graphは上面と下面に三角形をもちます。三角形の有無は同型で保存されるため、二つは非同型です。
この例では次数列の次に三角形数を見ることで区別できました。同型判定では、安い不変量から順に試し、異なればそこで終了し、一致した場合だけ写像の構成へ進みます。
部分graph・誘導部分graph・埋め込み
ここで、$V(H)\subseteq V(G)$、$E(H)\subseteq E(G)$ を満たす部分graphと、選んだ頂点間の全辺を残す誘導部分graph $G[S]$ を定義しました。
単射
$$
\iota:V(H)\longrightarrow V(G)
$$
が
$$
uv\in E(H)
\Longrightarrow
\iota(u)\iota(v)\in E(G)
$$
を満たすとき、$H$ から $G$ へのグラフ埋め込み|部分graph埋め込みという。
さらに
$$
uv\in E(H)
\Longleftrightarrow
\iota(u)\iota(v)\in E(G)
$$
を満たすとき誘導埋め込みという。
部分graph埋め込みでは、$H$ にない辺が像の頂点間に存在しても構いません。誘導埋め込みでは非辺も保存するため、像上の誘導部分graphが $H$ と同型になります。
$H$ が $G$ と同型な部分graphとして現れることと、$H$ から $G$ への部分graph埋め込みが存在することは同値である。誘導部分graphについても、部分graph埋め込みを誘導埋め込みへ置き換えれば同じである。
$J\subseteq G$ と $H\cong J$ が与えられれば、同型 $H\to J$ と包含写像 $J\hookrightarrow G$ の合成が部分graph埋め込みです。
逆に埋め込み $\iota$ があれば、頂点集合 $\iota(V(H))$ と辺集合
$$
\{\iota(u)\iota(v)\mid uv\in E(H)\}
$$
からなる $G$ の部分graph $J$ を取れます。$\iota:H\to J$ は全単射で隣接関係を前後同値に保存するので同型です。
誘導の場合、非辺も保存する条件により $J=G[\iota(V(H))]$ となります。逆向きも同じ合成で従います。□
頂点・辺の削除
$v\in V(G)$ に対して
$$
G-v=G[V(G)\setminus\{v\}]
$$
と書きます。辺 $e\in E(G)$ に対しては、頂点を残して $e$ だけを削除したgraphを $G-e$ と書きます。
頂点削除は必ず誘導部分graphを作り、辺削除は一般には誘導部分graphを作りません。この二操作は「切断点・橋・ブロック」でcut vertexとbridgeを定義するときに使います。
補graphと同型
$$
G\cong H
\quad\Longleftrightarrow\quad
\overline G\cong\overline H.
$$
さらに $S\subseteq V(G)$ に対して
$$
\overline{G[S]}=\overline G[S],
$$
ただし左辺の補graphは頂点集合 $S$ 上で取る。
$\varphi:G\to H$ が同型なら、相異なる $u,v$ に対し
$$
\begin{aligned}
uv\in E(\overline G)
&\Longleftrightarrow uv\notin E(G)\\
&\Longleftrightarrow
\varphi(u)\varphi(v)\notin E(H)\\
&\Longleftrightarrow
\varphi(u)\varphi(v)\in E(\overline H).
\end{aligned}
$$
従って同じ $\varphi$ が補graph間の同型です。逆向きは補graphをもう一度取り
$$
\overline{\overline G}=G
$$
を使えば従います。
二つ目の式では、$u,v\in S$ に対し、左辺でも右辺でも「$uv$ が $G$ の辺でない」ときちょうど辺になります。頂点集合もともに $S$ なので等しいです。□
この命題から、$S$ が $G$ のcliqueであることと、$S$ が $\overline G$ の独立集合であることが同値になります。
自己補graph
$$
G\cong\overline G
$$
を満たすgraph $G$ を自己補グラフ|自己補graphという。
$n$ 頂点の自己補graphが存在するなら
$$
n\equiv0\ \text{または}\ 1\pmod4.
$$
$G\cong\overline G$ なら辺数は等しいです。一方、補graphの辺数公式から
$$
|E(G)|+|E(\overline G)|=\binom n2.
$$
従って
$$
2|E(G)|=\binom n2=\frac{n(n-1)}2,
$$
すなわち
$$
|E(G)|=\frac{n(n-1)}4.
$$
右辺が整数なので $4\mid n(n-1)$ です。連続する二整数の一方だけが偶数であり、その偶数が4の倍数でなければならないため
$$
n\equiv0\quad\text{または}\quad1\pmod4.
$$
□
これは必要条件であって、この命題だけでは存在を示していません。$P_4$ は自己補です。頂点をpath順に $1-2-3-4$ とすると、補graphの辺は
$$
13,\ 14,\ 24
$$
です。写像
$$
1\mapsto3,\quad2\mapsto1,\quad3\mapsto4,\quad4\mapsto2
$$
は $P_4$ から補graphへの同型になります。
隣接行列による同型判定
$V(G)=\{v_1,\ldots,v_n\}$ に対し、隣接行列を
$$
(A_G)_{ij}=
\begin{cases}
1,&v_iv_j\in E(G),\\
0,&v_iv_j\notin E(G)
\end{cases}
$$
と定めます。単純graphなので対角成分は0で、行列は対称です。
$n$ 頂点graph $G,H$ が同型であるための必要十分条件は、ある置換行列 $P$ が存在して
$$
A_H=P^{\mathsf T}A_GP
$$
となることである。
同型 $\varphi:V(G)\to V(H)$ があるとします。$H$ の頂点順序を、$\varphi(v_1),\ldots,\varphi(v_n)$ に並べ替える置換行列を $P$ と取ります。行と列を同じ置換で並べ替えた行列 $P^{\mathsf T}A_GP$ の $(i,j)$ 成分は、対応する二頂点が $G$ で隣接するかを表します。同型により、それは $H$ の対応する二頂点が隣接することと同値なので $A_H$ と一致します。
逆に等式を満たす置換行列 $P$ は頂点の全単射を定めます。行列の $(i,j)$ 成分が前後で等しいことは、対応する頂点対が辺であることが前後同値であることを意味します。従ってその全単射はgraph同型です。□
この定理は「頂点名の付け替え」が隣接行列の行と列を同時に置換することだと述べています。全置換を試せば有限時間で同型判定できますが、候補は $n!$ 個あります。実際の判定では次数、近傍次数multiset、成分、短いcycleなどの不変量で候補を先に絞ります。
自己同型群
graph $G$ から自分自身への同型全体を
$$
\operatorname{Aut}(G)
$$
と書く。写像の合成を積とすると、これを $G$ のグラフの自己同型群|自己同型群という。
$\operatorname{Aut}(G)$ は写像の合成について有限群をなす。また
$$
\operatorname{Aut}(G)=\operatorname{Aut}(\overline G)
$$
である。
同型の合成は同型なので積について閉じています。写像の合成は結合的です。恒等写像は自己同型であり、自己同型の逆写像も同型です。頂点集合が有限なので、その置換全体の部分集合である $\operatorname{Aut}(G)$ も有限です。従って有限群です。
補graphと同型の命題により、$G$ の自己同型 $\varphi$ は同じ写像のまま $\overline G$ の自己同型になります。逆向きも補を二回取れば従うため、二つの自己同型集合は等しいです。□
具体例
- $K_n$ では任意の頂点置換が辺を辺へ送るので
$|\operatorname{Aut}(K_n)|=n!$。 - $P_n$、$n\ge2$ では、次数1の二端点を固定するか交換するかで自己同型が決まり
$|\operatorname{Aut}(P_n)|=2$。 - $C_n$、$n\ge3$ では、一頂点の像を $n$ 通り、その隣の頂点の像を時計回り・反時計回りの2通りに選べるので
$|\operatorname{Aut}(C_n)|=2n$。
$P_n$ の主張では、端点の像が決まると、その端点から距離 $k$ の唯一の頂点の像も順に決まります。$C_n$ では最初の頂点と向きが決まれば、隣接関係により全頂点の像が決まります。どの選択も実際に恒等・反転、または回転・鏡映を与えるので、上の個数を尽くします。
ラベル付き実現の個数
同じ抽象graphへ頂点名 $1,\ldots,n$ を付ける方法は $n!$ 通りに見えます。しかし自己同型だけ異なる二つの付け方は、同じlabelled edge setを与えます。
$n$ 頂点の抽象graph $G$ を、固定した頂点集合 $[n]$ 上のgraphとして実現する異なる方法の個数は
$$
\frac{n!}{|\operatorname{Aut}(G)|}.
$$
全単射
$$
\lambda:V(G)\to[n]
$$
は $n!$ 個あります。各 $\lambda$ は辺 $uv$ を辺 $\lambda(u)\lambda(v)$ へ送り、$[n]$ 上のlabelled graphを作ります。
二つの全単射 $\lambda,\lambda'$ が同じlabelled graphを作るための必要十分条件は
$$
\alpha=\lambda'^{-1}\circ\lambda
$$
が $G$ の自己同型であることです。実際、同じ辺集合を作ることは
$$
uv\in E(G)
\Longleftrightarrow
\alpha(u)\alpha(v)\in E(G)
$$
と同値です。
一つのlabelled実現を与える $\lambda$ に対し、同じ実現を与える付け方は自己同型 $\alpha$ を用いた
$$
\lambda\circ\alpha
$$
の形でちょうど $|\operatorname{Aut}(G)|$ 個あります。従って $n!$ 個の全単射は同じ大きさの組へ分かれ、異なる実現数は
$$
\frac{n!}{|\operatorname{Aut}(G)|}
$$
です。□
例えば $C_5$ のlabelled実現数は
$$
\frac{5!}{|\operatorname{Aut}(C_5)|}
=\frac{120}{10}=12.
$$
これは $K_5$ の10本の辺から5本を選ぶ $\binom{10}{5}=252$ 通りのうち、5-cycleになるものが12個あるという意味です。
頂点推移性
任意の $u,v\in V(G)$ に対し
$$
\varphi(u)=v
$$
となる自己同型 $\varphi\in\operatorname{Aut}(G)$ が存在するとき、$G$ を頂点推移グラフ|頂点推移graphという。
有限頂点推移graphは正則である。
任意の $u,v$ に対し $u$ を $v$ へ送る自己同型があります。同型は次数を保存するので
$$
\deg(u)=\deg(v).
$$
すべての頂点次数が等しいため正則です。□
逆は成り立ちません。$C_3\cup C_4$ は全頂点次数2で正則ですが、自己同型は三角形成分の頂点を四角形成分へ送れません。cycle長と成分の大きさが保存されるからです。従って頂点推移ではありません。
演習
$G$ の頂点集合を $\{1,2,3,4\}$、辺集合を
$$
\{12,23,34\}
$$
とする。$H$ の頂点集合を $\{a,b,c,d\}$、辺集合を
$$
\{ac,cd,db\}
$$
とする。$G\cong H$ を示す同型を一つ与えよ。
$$
\varphi(1)=a,\quad
\varphi(2)=c,\quad
\varphi(3)=d,\quad
\varphi(4)=b
$$
と置きます。これは頂点集合間の全単射であり、三辺
$$
12,\ 23,\ 34
$$
をそれぞれ
$$
ac,\ cd,\ db
$$
へ送ります。両graphは4頂点3辺なので、残る三つの非辺も非辺へ送られます。従って同型です。□
$K_{3,3}$ と三角柱graphが非同型であることを、次数列だけではなく別の不変量を用いて示せ。
どちらも6頂点3-正則なので次数列は
$$
(3,3,3,3,3,3)
$$
です。
$K_{3,3}$ は二部graphであり、すべてのcycle長は偶数なので三角形をもちません。三角柱graphは上下の底面に三角形を二つもちます。三角形の個数は同型不変量なので、二つは非同型です。□
頂点 $1,2,3,4$ と辺 $12,23,34$ をもつ $P_4$ の補graphを求め、本文と異なる同型 $P_4\to\overline{P_4}$ を一つ与えよ。
$K_4$ の六辺から $12,23,34$ を除くので
$$
E(\overline{P_4})=\{13,14,24\}.
$$
例えば
$$
1\mapsto2,\quad
2\mapsto4,\quad
3\mapsto1,\quad
4\mapsto3
$$
と置くと
$$
12\mapsto24,\qquad
23\mapsto14,\qquad
34\mapsto13.
$$
三辺を補graphの三辺へ全単射に移すため、同型です。□
$S\subseteq V(G)$ とする。$G[S]$ が完全graphであることと、$\overline G[S]$ が空graphであることが同値であることを証明せよ。
$G[S]$ が完全であるとは、$S$ の相異なる任意の二頂点が $G$ で隣接することです。補graphでは各頂点対について隣接・非隣接が逆になるため、これは $S$ のどの二頂点も $\overline G$ で隣接しないことと同値です。後者は $\overline G[S]$ が空graphであることです。□
固定頂点集合 $[6]$ 上に、$C_6$ と同型なgraphはいくつあるか。
$|\operatorname{Aut}(C_6)|=2\cdot6=12$ です。従ってラベル付き実現数は
$$
\frac{6!}{12}
=\frac{720}{12}
=60.
$$
□
star graph $K_{1,4}$ の自己同型群が頂点集合上にもつ軌道を求め、自己同型群の位数を求めよ。
中心頂点は次数4、四つの葉は次数1です。自己同型は次数を保存するので中心を中心へ送り、葉全体を葉全体へ送ります。従って頂点軌道は
$$
\{\text{中心}\},\qquad
\{\text{四つの葉}\}
$$
の二つです。
四つの葉は任意に置換でき、その置換は隣接関係を保存します。中心の像は固定されるので、自己同型は葉の置換と一対一です。従って
$$
|\operatorname{Aut}(K_{1,4})|=4!=24.
$$
□
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
