12.4 同型

見た目の異なる二つのグラフが本質的には同一となる状況がある。例えば図 \(\text{12.7}\) に示した二つのグラフはどちらも \(4\) 個の頂点と \(5\) 個の辺を持ち、\(\text{(a)}\) を反時計回りに \(90^{\circ}\) 回転させると \(\text{(b)}\) に形状が一致する。

厳密に言えば、これら二つのグラフを表す数学的オブジェクトは同じではない。ただ事実として、二つのグラフを図で表すと同じ形状となる。この「ラベルを無視して」同一である事実は、グラフの同型 (isomorphic) と呼ばれる概念を使うと表現できる。二つのグラフが同型とは、辺を保存する頂点集合間の全単射が存在することを言う:

図 \(\text{12.7}\) に示したグラフ \(\text{(a)}\), \(\text{(b)}\) 間の同型写像 \(f\) は次の写像である:

「二頂点が \(\text{(a)}\) で辺の端点である」と「それらに対応する二頂点が \(\text{(b)}\) で辺の端点である」が同値なことを確認しておくとよい。

同型なグラフを表す図が似た形状をしているとは限らない。例えば図 \(\text{12.8}\) に示す二つのグラフはどちらも閉路グラフ \(C_{5}\) と同型であるものの、図の形状は異なる。

\(f\) が \(G\), \(H\) 間の同型写像なら、\(f^{-1}\) は \(H\), \(G\) 間の同型写像である。また、同型写像の合成は同型写像なので、同型関係は推移性を持つ。反射性は自明なので、同型関係は同値関係である。

同型写像はグラフの頂点の接続に関する性質を保存する。例えば、頂点がどんな数学的オブジェクトであるか、あるいはグラフを表す図で頂点がどのように表されるかといった特徴は同型写像によって抽象化される。こういった事実を表現するための表現がある: グラフに関する性質が同型写像の下で保存される (preserved under isomorphism) とは「あるグラフ \(G\) がその性質を持つなら、\(G\) と同型な全てのグラフもその性質を持つ」ことを意味する。

同型写像 \(f\) は頂点集合間の全単射なので、同型なグラフは同じ個数の頂点を持つ。さらに、もし同型写像 \(f\) が頂点 \(v\) を頂点 \(f(v)\) に対応付けるなら、同型写像の定義より、\(v\) に隣接する全ての頂点は \(f(v)\) に隣接する頂点に対応付けられ、その他に \(f(v)\) に隣接する頂点は存在しない。つまり \(v\) と \(f(v)\) は同じ次数を持つ。そのため例えば \(4\) 頂点のグラフと \(5\) 頂点のグラフが同型になることはなく、次数が \(4\) の頂点の個数が異なる二つのグラフは必ず同型でない。

同型写像によって保存される性質に注目すると、二つのグラフが同型でないことを簡単に確認できる。また、同型写像が存在するならどんなものかを考えるヒントにもなる。現実の問題で扱う規模の二つのグラフが同型かどうかを判定するのは難しくない場合が多い。しかし、任意のグラフの組が同型かどうかを確実に判定する手続きであって多項式時間で実行できるものは現在でも見つかっていない¹。

グラフの同型性の効率的な判定手続きには様々な応用が考えられる。例えば、分子結合の形態から分子を特定するデータベースの高速な検索が可能になるだろう。一方で、そういった手続きが存在しないと分かった場合にも応用が可能になる: 暗号化やリモート認証で用いられる安全なプロトコルを、グラフの同型性は計算量的に判定不可能という仮定を利用して構築できるようになる。

全単射や同型写像といった概念は有限グラフだけではなく無限グラフにも適用でき、本章で示される結果の多くも無限グラフに適用できる。ただし、グラフ理論は有限グラフだけを考えることが多いので、本書でもそのようにする。

実は、前節で「\(n\) 個の頂点を持ち任意の異なる二頂点間に辺が存在するグラフを \(K_{n}\) と呼ぶ」と述べたときに同型の概念は暗黙に使われている。