グラフ同型性

グラフ理論では、グラフGとHの同型性は、 GとHの頂点集合間の一対一表現である。

${\displaystyle f\colon V(G)\to V(H)}$

Gの任意の2 つの頂点uとvがGで隣接している場合と、 H で隣接している場合に限ります。この種の全単射は、同型性が構造保存の全単射であるという一般的な概念に従って、一般に「辺保存の全単射」と呼ばれます。 ${\displaystyle f(u)}$${\displaystyle f(v)}$

2 つのグラフの間に同型性が存在する場合、そのグラフは同型であるとされ、 と表記されます。同型性がグラフのそれ自身への写像である場合、つまりGとHが 1 つの同じグラフである場合、同型性はGの自己同型性と呼ばれます。 ${\displaystyle G\simeq H}$

グラフ同型性はグラフ上の同値関係であり、すべてのグラフのクラスを同値クラスに分割します。互いに同型なグラフの集合はグラフの同型クラスと呼ばれます。グラフ同型性が多項式時間で決定できるかどうかという問題は、グラフ同型性問題として知られている、コンピュータサイエンスにおける未解決の大きな問題です。^{[1] [2]}

以下に示す 2 つのグラフは、見た目は異なりますが、同型です。

上記の定義では、グラフは無向 、ラベルなし 、重みなしのグラフであると理解されています。ただし、同型性の概念は、対応する構造の追加要素 (弧の方向、エッジの重みなど) を保持するための要件を追加することで、グラフの概念の他のすべてのバリエーションに適用できます。ただし、次の例外があります。

ラベル付きグラフの場合、同型性の 2 つの定義が使用されます。

ある定義によれば、同型写像は辺とラベルの両方を保存する頂点の一対一写像である。^{[3] [4]}

別の定義では、同型性はラベルの同値類を保存する辺保存頂点一対一写像であり、すなわち、等価な（例えば同じ）ラベルを持つ頂点は、等価なラベルを持つ頂点にマッピングされ、その逆もまた同様である。辺ラベルについても同様である。^[5]

たとえば、1 と 2 のラベルが付けられた 2 つの頂点を持つグラフには、最初の定義では 1 つの自己同型がありますが、2 番目の定義では 2 つの自己同型があります。 ${\displaystyle K_{2}}$

2 番目の定義は、グラフに一意のラベルが付与される特定の状況で想定されます。ラベルは一般に 1,..., nの整数範囲から取得されます。ここで、n はグラフの頂点の数であり、頂点を一意に識別するためだけに使用されます。このような場合、2 つのラベル付きグラフは、対応する基礎となるラベルなしグラフが同型である場合に同型であると言われることがあります (そうでない場合、同型性の定義は自明です)。

「同型性」の正式な概念、たとえば「グラフ同型性」は、問題のオブジェクトの「原子」コンポーネントの個々の違いを無視すれば、いくつかのオブジェクトは「同じ構造」を持つという非公式な概念を捉えています。グラフによってモデル化されるものを正しく表現するために「原子」コンポーネント (グラフの場合は頂点と辺) の個別性が重要である場合は、構造に追加の制限を課すことでモデルが洗練され、他の数学的オブジェクト (有向グラフ、ラベル付きグラフ、色付きグラフ、ルート付きツリーなど) が使用されます。同型性関係は、グラフのこれらすべての一般化に対して定義することもできます。同型性一対一は、問題のオブジェクト タイプを定義する構造の要素 (アーク、ラベル、頂点/辺の色、ルート付きツリーのルートなど) を保存する必要があります。

「グラフ同型性」という概念により、グラフ自体の構造に固有のグラフ特性と、グラフ表現に関連する特性（グラフ描画、グラフのデータ構造、グラフのラベル付けなど）を区別することができます。たとえば、グラフにちょうど 1 つのサイクルがある場合、その同型性クラス内のすべてのグラフにもちょうど 1 つのサイクルがあります。一方、グラフの頂点が整数1、2、... Nで表される一般的なケースでは、式

${\displaystyle \sum _{v\in V(G)}v\cdot {\text{deg }}v}$

2 つの同型グラフでは異なる場合があります。

ハスラー・ホイットニーによって示されたホイットニーグラフ同型定理[ ^6]は、 2つの連結グラフは、その線グラフが同型である場合にのみ同型であると述べています。ただし、3頂点の完全グラフK ₃と完全2部グラフK _1,3は同型ではありませんが、どちらも線グラフとしてK _{3 を}持ちます。ホイットニーグラフ定理はハイパーグラフに拡張できます。^[7]

グラフ同型性は、ホイットニーの定理に例示されるように、古典的な数学的方法で研究されることもありますが、アルゴリズム的アプローチで取り組むべき問題であることが認識されています。2 つの有限グラフが同型であるかどうかを判断する計算上の問題は、グラフ同型性問題と呼ばれます。

その実際の応用としては、主に化学情報科学、数理化学（化合物の識別）、電子設計自動化（電子回路設計のさまざまな表現の同等性の検証）などがあります。

グラフ同型性問題は、計算複雑性理論における数少ない標準的な問題の1つであり、 NPに属しているが、そのよく知られた（そして、P ≠ NPの場合は互いに素な）部分集合であるPとNP完全のどちらにも属さないことが知られている。これは、Garey & Johnson（1979）にリストされている合計12の問題のうち、複雑性が未解決のままであるわずか2つの問題のうちの1つであり、もう1つは整数因数分解である。ただし、問題がNP完全である場合、多項式階層は有限レベルに崩壊することが知られている。 ^[8]

2015年11月、シカゴ大学の数学者でコンピュータ科学者のラスロー・ババイは、グラフ同型性問題が準多項式時間で解けることを証明したと主張した。^{[9] [10]}彼はこれらの結果の予備版を2016年の計算理論シンポジウム[ ^11]と2018年の国際数学者会議^[12]の議事録で発表した。2017年1月、ババイは準多項式性の主張を一時的に撤回し、代わりに指数関数的時間計算量以下の限界を述べた。彼は5日後に元の主張を復活させた。^[13] 2024年現在^{[アップデート]}、ババイの論文の完全版はまだ出版されていない。

その一般化である部分グラフ同型性問題はNP 完全であることが知られています。

この問題の主な研究分野は、一般的な問題と特殊なグラフのクラスの両方に対する 高速アルゴリズムの設計と計算の複雑さの理論的調査です。

ワイスファイラー・レーマングラフ同型性テストは、グラフ同型性をヒューリスティックにテストするために使用できます。^[14]テストに失敗した場合、2つの入力グラフは非同型であることが保証されます。テストが成功した場合、グラフは同型である場合もそうでない場合もあります。同型性を確実に検出できるテストアルゴリズムの一般化がありますが、実行時間は指数関数的に長くなります。

グラフ同型性のためのもう1つのよく知られたアルゴリズムは、2001年にCordellaらによって開発されたvf2アルゴリズムです。^[15] vf2アルゴリズムは、2つのグラフ間の同型性を段階的に構築しようとする深さ優先探索アルゴリズムです。一連の実行可能性ルールを使用して探索空間を整理し、数千のノードを持つグラフを効率的に処理できるようにします。vf2アルゴリズムは、パターン認識、コンピュータービジョン、バイオインフォマティクスなど、さまざまなアプリケーションで広く使用されています。最悪の場合、指数時間の計算量になりますが、実際には多くの種類のグラフで良好なパフォーマンスを発揮します。

• グラフ準同型
• グラフ自己同型問題
• グラフ同型性問題
• グラフの正規化

• ゲーリー、マイケル R. ;ジョンソン、デビッド S. (1979)。コンピュータと扱いにくさ: NP 完全性理論ガイド。数学科学シリーズ (第 1 版)。ニューヨーク: WH フリーマン アンド カンパニー。ISBN 9780716710455. MR  0519066. OCLC  247570676.