1 グラフ同型の基本概念
1.1 グラフと頂点対応の定義
グラフ同型は、2つのグラフが「つながりの構造として同じ」であることを、頂点どうしの対応づけによって形式化する考え方である。ここでいう対応は、ある頂点集合から別の頂点集合への写像として与えられる。
典型的には、単純グラフ（多重辺やループを許さない）を考え、各辺は頂点対で表される。グラフ同型では、頂点のラベル（名前）を付け替えても隣接関係が同一になるかどうかが焦点となる。
1.2 同型写像（全単射）の条件
2つのグラフ \(G=(V,E)\) と \(H=(W,F)\) が同型であるとは、全単射 \(f:V\to W\) が存在して、辺の集合が対応づけにより一致することをいう。具体的には、任意の頂点 \(u,v\in V\) について \[ \{u,v\}\in E \quad\Longleftrightarrow\quad \{f(u),f(v)\}\in F \] が成り立つことが必要十分条件である。
この条件は「隣接している頂点どうしが写像によって隣接する頂点対へ対応し、逆も同様に保証される」ことを意味する。全単射であることにより、頂点の対応が過不足なく対応づくため、情報が欠落しない。
1.3 同型の性質（反射・対称・推移）
同型関係は、標準的に同型写像の性質として理解できる。まず反射律として、各グラフ \(G\) には恒等写像があり、辺は変わらないため \(G\) は自分自身と同型である。
次に対称律として、同型写像 \(f:V\to W\) が全単射である以上、その逆写像 \(f^{-1}:W\to V\) も全単射となり、同じ辺対応条件が成立する。したがって \(G\) が \(H\) と同型なら \(H\) も \(G\) と同型である。
さらに推移律として、\(G\) が \(H\) と同型、かつ \(H\) が \(K\) と同型であれば、同型写像の合成が全単射となり、辺対応条件が連続的に保たれる。よって \(G\) は \(K\) と同型になる。
2 同型関係と分類
2.1 同型類（同型クラス）
同型関係が反射・対称・推移を満たすため、グラフ全体は同型を同一視する枠組みによって分類できる。すなわち、同型で互いに移り合えるグラフの集合は同型類（同型クラス）と呼ばれ、各同型類の中では構造が同一である。
この分類は、ラベルの取り違えを排除して「構造の違い」だけを残す役割を果たす。したがって、2つのグラフが同型でない場合には、同型類が異なる。
2.2 同型不変量の考え方
同型類の区別や同型判定の補助として、同型写像で変化しない量や性質を「同型不変量」と呼ぶ。もし2つのグラフが同型であれば、同型不変量は一致する。逆に、不変量が一致したとしても同型が保証されるとは限らず、必要条件として用いられることが多い。
同型不変量は計算の観点からも重要で、頂点対応を直接探す代わりに、比較しやすい特徴量を利用して候補を絞る。
2.2.1 次数列と連結性
最も基本的な同型不変量の一つは次数列である。各頂点の次数（隣接する頂点数）は、同型写像によって保存される。したがって、2つのグラフの次数の多重集合が一致しないなら同型ではない。
連結性も同型不変量として扱える。連結成分の分解構造は、辺の配置が保存される以上変わらない。すなわち、連結かどうか、また連結成分の個数やそれぞれの同型類が同型であれば整合する。
ただし次数列や連結性だけでは同型の十分条件にならないことがある。異なる構造が同じ次数列を持つ例は存在するため、より洗練された特徴量が必要になる場合がある。
2.2.2 部分グラフ・補グラフとの関係
部分グラフの関係も同型不変性と結びつく。あるグラフの誘導部分（指定した頂点集合とそれらの間の辺全体からなるもの）は、頂点対応があれば同型写像により対応づけられる。したがって、一定の部分構造を含むかどうかは同型で保存される性質として利用できる。
補グラフも同型不変量と関連する。補グラフとは、同じ頂点集合の上で「元のグラフに存在しない辺」を辺として持つグラフである。元のグラフが同型なら、その補グラフも同型である。これにより、元のグラフと補グラフの両方で見える特徴を組み合わせることで、情報量を増やす戦略が可能になる。
3 記述論理とロジック的観点
3.1 同型性の論理的表現
記述論理や論理学の枠組みでは、「ある構造が別の構造と同型である」という主張を、論理式で表せるかが問題になる。ここでの対象は通常、頂点集合と辺関係をシンボルとして持つ構造（グラフ構造）である。
同型そのものは「存在する全単射が辺関係を保存する」という性質なので、量化（存在・全称）を含む表現が自然に必要になる。どの程度制限した論理（例：使える量化の形や、固定個数の変数だけ許すか）で同型性を表現できるかが、研究テーマとして位置づけられる。
3.2 不変性（同型によって変わらない性質）
論理的観点では、不変性（不変条件）という概念が中心になる。同型によって不変である性質とは、同型写像により構造が「見かけ上入れ替わっても」真偽が変わらない論理文に対応する。
一般に、論理式が定義する性質が同型不変であるなら、論理式は本質的に同型類に依存する。逆に、同型不変な性質が特定の論理体系で表現可能かどうかは自明ではない。このギャップが「表現力」と「同型不変性」の関係として研究される。
3.3 記述的表現と判定可能性の関係
記述的表現が可能であることは、しばしば判定手続きの設計とも結びつく。ある論理体系で表現できる性質は、その体系に基づく計算モデルにより評価できる場合があるためである。
ただし、表現可能性が直ちに効率的アルゴリズムを与えるとは限らない。論理式の複雑さ（量化の深さや変数数、演算子の種類）によっては、理論的には判定できても実用上の計算量が大きくなることがある。したがって、論理的に定義できるかどうかと、現実的に求まるか（計算量やアルゴリズムの性質）は別問題として扱われる。
4 計算機科学としてのグラフ同型
4.1 グラフ同型判定問題の概要
計算機科学では、入力として2つのグラフが与えられ、同型かどうかを判定する問題が中心となる。頂点のラベルは機械的に与えられているため、単純には「全ての全単射を試す」ことが考えられるが、頂点数が増えると総当たりは計算不能な規模になる。
そのため、同型不変量による絞り込み、構造的性質の利用、さらには分割と絞り込み（refinement）といった手法が検討される。問題設定としては、通常、無向単純グラフを扱うことが多いが、バリエーションとして有向グラフや色付きグラフへの拡張もある。
4.2 よく使われる判定の前処理
前処理では、同型であるなら必ず満たす条件を使い、探索空間を縮める。次数分布、連結性、連結成分の構造、最大次数、直径や中心など、比較的安価に計算できる特徴が用いられる。
さらに、色付け（頂点への補助情報の割当）を行い、同型候補となる対応を「同じ色同士に限る」形で制約を課すことがある。たとえば、次数が等しい頂点のみを対応候補に含めるような操作は、自然な前処理として機能する。
前処理は完全な同型判定には届かないことも多いが、後段の探索・分割の効率を大きく左右する。
4.3 同型を見つけるための代表的方針（概要）
同型判定の代表的方針は、候補対応を系統的に構築し、矛盾した場合に探索を打ち切ることである。実装上は、頂点の集合を分割し、分割を局所的情報で細かくしていく手法がよく用いられる。これは「曖昧な候補を次第に絞っていく」発想に基づく。
もう一つの方針として、対称性の高い構造では探索が膨張するため、同型候補の探索木を管理する工夫（固定点の選択、バックトラックの制御、候補の順序付け）が重要になる。色付きグラフとして問題を焼き直し、圧縮された情報のもとで同型写像を組み立てる流れもある。
概略としては、(1)不変量で早期に弾く、(2)分割・洗練で候補を減らす、(3)必要なら限定的な探索で対応を確定する、という組み合わせで実用性を高めるのが典型である。