グラフ同型性

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

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

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

2つのグラフ間に同型性が存在する場合、それらのグラフは同型であるとされ、しばしば と表記されます。同型性がグラフのそれ自身への写像である場合、つまりGとHが同一のグラフである場合、同型性は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 つの同型グラフでは異なる場合があります。

ホイットニーの定理

ホイットニーの定理の例外: これら 2 つのグラフは同型ではありませんが、同型の線グラフを持ちます。

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

グラフ同型の認識

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

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

グラフ同型性問題は、計算複雑性理論における数少ない標準的な問題の一つであり、 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年現在^[update]、ババイの論文の完全版はまだジャーナルに掲載されていない。

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

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

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

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

参照

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

注記

1. Grohe, Martin (2020年11月1日). 「グラフ同型性問題」 . Communications of the ACM . 63 (11): 128– 134. doi :10.1145/3372123 . 2023年3月6日閲覧。
2. Klarreich, Erica (2015年12月14日). 「画期的なアルゴリズムが30年間の行き詰まりを打破」. Quanta Magazine . 2023年3月6日閲覧。
3. 424ページ
4. Hsieh, Shu-Ming; Hsu, Chiun-Chieh; Hsu, Li-Fu (2006). 「ラベル付きグラフの同型性テストを効率的に実行する手法」.計算科学とその応用 - ICCSA 2006.コンピュータサイエンス講義ノート. 第3984巻. pp.  422– 431. doi :10.1007/11751649_46. ISBN 978-3-540-34079-9。
5. ピエール・アントワーヌ・シャンパン、クリスティン・ソルノン、「ラベル付きグラフの類似度の測定」『 コンピュータサイエンス講義ノート』第2689巻、80～95ページ
6. ホイットニー、ハスラー（1932年1月）「合同グラフとグラフの連結性」アメリカ数学誌. 54 (1): 150– 168. doi :10.2307/2371086. hdl : 10338.dmlcz/101067 . JSTOR  2371086.
7. Dirk L. Vertigan, Geoffrey P. Whittle: ハイパーグラフの2同型定理. J. Comb. Theory, Ser. B 71(2): 215–230. 1997.
8. Schöning, Uwe (1988). 「グラフ同型性は低階層にある」. Journal of Computer and System Sciences . 37 (3): 312– 323. doi :10.1016/0022-0000(88)90010-4.
9. Cho, Adrian (2015年11月10日)、「数学者が複雑性理論のブレークスルーを主張」、Science、doi :10.1126/science.aad7416。
10. エリカ・クラライヒ（2015年12月14日）「画期的なアルゴリズムが30年間の行き詰まりを打破」Quanta Magazine
11. Babai, László (2016)、「準多項式時間におけるグラフ同型性 [拡張概要]」、STOC'16—第48回ACM SIGACTコンピューティング理論シンポジウムの議事録、ACM、ニューヨーク、pp.  684– 697、doi :10.1145/2897518.2897542、ISBN 978-1-4503-4132-5、MR  3536606、S2CID  17118954
12. Babai, László (2018)、「群、グラフ、アルゴリズム：グラフ同型性問題」、国際数学者会議リオデジャネイロ2018の議事録、第4巻、招待講演、World Sci. Publ.、ハッケンサック、ニュージャージー州、pp.  3319– 3336、MR  3966534
13. Babai、László (2017 年 1 月 9 日)、グラフ同型性の更新
14. Huang, Ningyuan Teresa; Villar, Soledad (2021). 「Weisfeiler-Lehman検定とその変種に関する短いチュートリアル」. ICASSP 2021 - 2021 IEEE 国際音響・音声・信号処理会議 (ICASSP) . pp.  8533– 8537. arXiv : 2201.07083 . doi :10.1109/ICASSP39728.2021.9413523. ISBN 978-1-7281-7605-5. S2CID  235780517。
15. Cordella, LP; Foggia, P.; Sansone, C.; Vento, M. (2001). 「大規模グラフのマッチングのための改良アルゴリズム」.第3回IAPR-TC15 パターン認識におけるグラフベース表現ワークショップ: 149–159 .

参考文献

• ゲイリー、マイケル・R.、ジョンソン、デイビッド・S. (1979). 『コンピュータとイントラクタビリティ：NP完全性理論へのガイド』 数学科学シリーズ（第1版） ニューヨーク：WHフリーマン・アンド・カンパニーISBN 9780716710455. MR  0519066. OCLC  247570676.