Loading article…
グラフ理論という数学分野において、グラフ準同型写像とは、2つのグラフの構造を尊重する写像のことである。より具体的には、2つのグラフの頂点集合間の関数であり、隣接する頂点を隣接する頂点に写像するものである。
準同型写像は、グラフ彩色に関するさまざまな概念を一般化し、特定のスケジューリング問題や頻度割り当て問題などの重要なクラスの制約充足問題の表現を可能にします。[ 1 ] 準同型写像を合成できるという事実は、グラフの順序、分配束、およびカテゴリ（無向グラフ用と有向グラフ用）といった豊富な代数構造につながります。[ 2 ]与えられたグラフ間の準同型写像を見つける 計算複雑性は一般には法外ですが、多項式時間で解ける特殊なケースについては多くのことが知られています。扱いやすいケースと扱いにくいケースの境界は、活発な研究分野となっています。[ 3 ]
本稿では、特に断りのない限り、グラフは有限無向グラフであり、ループは許容されるが、多重辺（平行辺）は許容されないものとする。グラフ準同型[ 4 ] f は、グラフから得られる。グラフへ、f : G → Hと表記される関数は、にエッジを保持する。正式には、
暗示するすべての頂点のペアについてで。
GからHへの準同型写像が存在する場合、GはHと準同型である、またはH彩色可能であると言われます。これはしばしば単に と表記されます。
上記の定義は有向グラフにも拡張されます。すると、準同型f : G → Hに対して、( u , v ) が G の弧であるとき、( f ( u ) , f ( v ) )はHの弧(有向辺)となります。
GからHへの単射準同型写像(すなわち、Gの異なる頂点をHの異なる頂点に写像する写像)が存在するのは、G がHの部分グラフと同型である場合に限る。準同型写像f : G → Hが全単射であり、その逆関数f −1もグラフ準同型写像である場合、fはグラフ同型写像である。[ 5 ]
被覆マップは、トポロジーにおける被覆マップの定義と多くの性質を反映する特殊な準同型写像です。[ 6 ] これらは、全射準同型写像（つまり、何かが各頂点に写像される）であり、かつ局所的に全単射、つまり各頂点の近傍での全単射であると定義されます。例として、各頂点v をv 0とv 1に分割し、各辺u、vを辺u 0、v 1とv 0、u 1に置き換えることによってグラフから形成される二部グラフの二重被覆があります。被覆内のv 0とv 1を元のグラフのvに写像する関数は、準同型写像であり、被覆マップです。
グラフ同相写像は、準同型写像とは直接関係のない、別の概念です。大まかに言うと、単射性が必要ですが、辺をパスにマッピングすることも（辺だけにマッピングすることも）可能です。グラフマイナーは、さらに緩やかな概念です。
2 つのグラフGとH は、 G → HかつH → Gの場合 、準同型である。[ 4 ]マップは必ずしも全射でも単射でもない。たとえば、完全二部グラフK 2,2とK 3,3は準同型である。各マップは、ドメイン グラフの左半分 (または右半分) を取り、イメージ グラフの左半分 (または右半分) の 1 つの頂点にマッピングすることで定義できる。
引き継ぎとは、グラフGからGの部分グラフHへの準同型写像rであり、 Hの各頂点vに対してr ( v ) = vとなるものである。この場合、部分グラフHはGの引き継ぎと呼ばれる。[ 7 ]
コアとは、どの真部分グラフにも準同型を持たないグラフのことである。言い換えれば、コアはどの真部分グラフにも縮約されないグラフとして定義できる。[ 8 ] すべてのグラフGは、 Gのコアと呼ばれる一意のコア (同型を除いて) と準同型である。[ 9 ]ただし、これは一般に無限グラフには当てはまらない。[ 10 ] しかし、同じ定義は有向グラフにも適用され、有向グラフも一意のコアと同値である。すべてのグラフとすべての有向グラフは、縮約および誘導部分グラフとしてそのコアを含む。[ 7 ]
例えば、完全グラフK nと奇数サイクル (奇数長のサイクルグラフ) はすべてコアです。三角形を含む (つまり、完全グラフK 3を部分グラフとして持つ) 3 彩色可能なグラフGはすべて、 K 3と準同型です。これは、一方では、Gの 3 彩色は、後述するように準同型G → K 3と同じであるためです。他方では、Gのすべての部分グラフは、自明にGへの準同型を許容し、K 3 → Gを意味します。これはまた、 K 3がそのようなグラフGのコアであることを意味します。同様に、少なくとも 1 つのエッジを持つすべての二部グラフは、 K 2と同型です。[ 11 ]
k彩色とは、ある整数kに対して、グラフGの各頂点にk個の色のうちの 1 つを割り当て、各辺の端点が異なる色になるようにすることです。Gのk彩色は、 Gから完全グラフK kへの準同型写像に正確に対応します。[ 12 ]実際、 K kの頂点はk個の色に対応し、2 つの色がK kの頂点として隣接しているのは、それらが異なる場合に限ります。したがって、関数がK kへの準同型写像を定義するのは、 Gの隣接する頂点を異なる色にマッピングする場合（つまり、 k彩色である場合）に限ります。特に、Gがk彩色可能であるのは、G がK k彩色可能である場合に限ります。[ 12 ]
2 つの準同型写像G → HとH → K kが存在する場合、それらの合成G → K kも準同型写像になります。[ 13 ]言い換えれば、グラフHがk色で彩色可能であり、 GからHへの準同型写像が存在する場合、Gもk彩色可能です。したがって、G → Hはχ( G ) ≤ χ( H ) を意味します。ここで、χはグラフの彩色数( k彩色可能な最小のk )を表します。[ 14 ]
一般準同型は一種の彩色と考えることもできます。固定グラフHの頂点が使用可能な色であり、 Hの辺がどの色が互換性があるかを記述する場合、GのH彩色とは、隣接する頂点が互換性のある色を取得するようにGの頂点に色を割り当てることです。グラフ彩色の多くの概念はこのパターンに当てはまり、さまざまなグラフ族へのグラフ準同型として表現できます。 円形彩色は、円形完全グラフへの準同型を使用して定義でき、通常の彩色の概念を洗練します。[ 15 ]分数彩色とb重彩色は、クネーザー グラフへの準同型を使用して定義できます。[ 16 ] T 彩色は、特定の無限グラフへの準同型に対応します。[ 17 ]有向グラフの有向彩色は、任意の有向グラフへの 準同型です。[ 18 ] L (2,1)彩色とは、パスグラフの補グラフへの準同型写像であり、局所的に単射である。つまり、すべての頂点の近傍で単射であることが求められる。[ 19 ]
もう1つの興味深い関連性は、グラフの向きに関するものです。無向グラフGの向きとは、各辺に対して可能な 2 つの向きのうちの 1 つを選択して得られる任意の有向グラフのことです。完全グラフK kの向きの例としては、頂点が 1,2,…, kで、 i < jのときにiからjへの弧がある推移的トーナメントT → kがあります。グラフGとHの向きの間の準同型は、向きを無視するだけで無向グラフGとHの間の準同型をもたらします。一方、無向グラフ間の準同型G → Hが与えられた場合、 Hの任意の向きH →をGの向きG →に引き戻すことができるため、 G →はH →と準同型になります。したがって、グラフGがk彩色可能である( K kと準同型である) のは、 Gの何らかの向きがT → kと準同型である場合のみです。[ 20 ]
民俗定理によれば、すべてのkに対して、有向グラフGがT → kへの準同型を持つのは、有向パスP → k +1からの準同型を持たない場合に限る。[ 21 ] ここでP → nは、頂点 1, 2, …, nとiからi + 1への辺を持つ有向グラフであり、 i = 1, 2, …, n − 1 である。したがって、グラフがk彩色可能であるのは、 P → k +1からの準同型を持たない向きを持つ場合に限る。この記述は、グラフが k 彩色可能であるのは、ある向きに長さkの有向パス(部分グラフとしてのP → k +1がない)が含まれていない場合に限ると少し強化できる。これがGallai–Hasse–Roy–Vitaver の定理である。
スケジューリングの問題の中には、グラフ準同型を見つける問題としてモデル化できるものがある。[ 22 ] [ 23 ]例えば、同じ学生が受講する 2 つのコースが時間的に近すぎないように、ワークショップ コースをカレンダーのタイムスロットに割り当てたい場合がある。コースはグラフGを形成し、共通の学生が受講する任意の 2 つのコース間にエッジが存在する。タイムスロットはグラフHを形成し、時間的に十分に離れている任意の 2 つのスロット間にエッジが存在する。例えば、各学生が連続しない日にワークショップ コースを受講するような、周期的な週単位のスケジュールが必要な場合、HはC 7の補グラフとなる。G からHへのグラフ準同型は、指定されたようにコースをタイムスロットに割り当てるスケジュールとなる。[ 22 ]例えば、どの学生も金曜日と月曜日の両方にコースを受講しないという要件を追加するには、 Hから対応するエッジを削除するだけで十分である。
単純な周波数割り当て問題は次のように定義できます。無線ネットワーク内の複数の送信機は、データを送信する周波数チャネルを選択する必要があります。干渉を避けるために、地理的に近い送信機は、周波数が大きく異なるチャネルを使用する必要があります。この条件を「地理的に近い」と「離れている」を定義する単一の閾値で近似すると、有効なチャネル選択は再びグラフ準同型に対応します。これは、地理的に近いペア間にエッジを持つ送信機のグラフGから、離れているチャネル間にエッジを持つチャネルのグラフHへの変換である必要があります。このモデルはかなり単純化されていますが、ある程度の柔軟性があります。地理的な特徴のために干渉する可能性があるが近くにない送信機ペアは、 Gのエッジに追加できます。同時に通信しないペアは、そこから削除できます。同様に、離れているが高調波干渉を示すチャネルペアは、 Hのエッジセットから削除できます。[ 24 ]
いずれの場合も、これらの単純化されたモデルは、実際に対処しなければならない多くの問題を示しています。[ 25 ]グラフ準同型問題を一般化した制約充足問題は、さまざまな追加タイプの条件（個人の好みや、同時割り当ての数の制限など）を表現できます。これにより、モデルをより現実的かつ実用的にすることができます。
グラフと有向グラフは、関係構造と呼ばれるはるかに一般的な概念（関係のタプルを持つ集合として定義される）の特殊なケースと見なすことができます。有向グラフは、ドメイン（頂点集合）上に単一の二項関係（隣接関係）を持つ構造です。[ 26 ] [ 3 ]この見方では、このような構造の準同型写像は、まさにグラフ準同型写像です。一般に、ある関係構造から別の関係構造への準同型写像を見つける問題は、制約充足問題（CSP）です。グラフの場合、より複雑なCSPを理解するのに役立つ具体的な第一歩となります。バックトラッキング、制約伝播、局所探索など、グラフ準同型写像を見つけるための多くのアルゴリズム的手法は、すべてのCSPに適用できます。[ 3 ]
グラフGとHの場合、 G がHへの準同型を持つかどうかという問題は、次のような1 種類の制約のみを持つ CSP インスタンスに対応します[ 3 ] 。変数はGの頂点であり、各変数のドメインはHの頂点集合です。評価は、各変数にドメインの要素を割り当てる関数、つまりV ( G )からV ( H ) への関数f です。G の各エッジまたはアーク ( u、v ) は、制約(( u、v ) 、 E ( H )に対応します。これは、評価がアーク ( u、v )を関係E ( H ) にあるペア ( f ( u ) 、f ( v ) ) にマッピングする必要があることを表す制約です。つまり、Hのアークにマッピングする必要があります。CSP の解は、すべての制約を尊重する評価であり、GからHへの準同型です。
準同型の合成は準同型です。[ 13 ] 特に、グラフ上の関係 → は推移的（そして自明に反射的）なので、グラフ上の前順序です。 [ 27 ]グラフGの準同型同値性による同値類を[ G ] とし ます。同値類は [ G ]の一意のコアによっても表すことができます。関係 → はこれらの同値類上の半順序であり、半順序集合を定義します。[ 28 ]
G < Hは、 GからHへの準同型写像が存在するが、HからGへの準同型写像は存在しないことを意味する。関係 → は稠密順序であり、 G < Hとなるすべての (無向) グラフG、Hに対して、 G < K < HとなるグラフKが存在することを意味する(これは、自明なケースG = K 0またはK 1を除いて成り立つ)。[ 29 ] [ 30 ] 例えば、任意の 2 つの完全グラフ( K 0、K 1、K 2を除く) の間には、自然数の間の有理数に対応する無限個の円形完全グラフが存在する。 [ 31 ]
準同型によるグラフの同値類の順序集合は分配束であり、[ G ] と [ H ] の結合は、互いに素な和集合 [ G ∪ H ]の同値類として定義され、 [ G ] と [ H ]の交わりは、テンソル積[ G × H ]として定義されます(同値類 [ G ] と [ H ]を表すグラフGとHの選択は重要ではありません)。[ 32 ]この束の結合既約要素は、連結グラフです 。これは、準同型が連結グラフを対象グラフの 1 つの連結成分に写像するという事実を使用して示すことができます。[ 33 ] [ 34 ]この束の交わり既約要素は、乗法グラフです 。これらは、積G × HがKに準同型を持つのは、 GまたはHのいずれかが準同型を持つ場合のみであるようなグラフKです。乗法グラフの識別は、ヘデトニエミ予想の中核をなすものである。[ 35 ] [ 36 ]
グラフ準同型もまた、グラフを対象、準同型を矢印とする圏を形成する。[ 37 ] 初期対象は空のグラフであり、終点対象は頂点が1つでその頂点にループが1つあるグラフである。グラフのテンソル積は圏論的積であり、指数グラフはこの圏の指数対象である。 [ 36 ] [ 38 ] これらの2つの演算は常に定義されているため、グラフの圏はデカルト閉圏である。同じ理由で、準同型によるグラフの同値類の束は実際にはハイティング代数である。[ 36 ] [ 38 ]
有向グラフの場合も同じ定義が適用されます。特に → は有向グラフの同値類上の半順序です。これは無向グラフの同値類上の順序 → とは異なりますが、部分順序としてそれを含んでいます。これは、すべての無向グラフは、すべての弧 ( u , v ) がその逆弧 ( v , u ) とともに現れる有向グラフと考えることができ、これにより準同型の定義が変わらないためです。有向グラフの順序 → は、以前と同様に結合および出会い演算が定義される分配束およびハイティング代数です。ただし、稠密ではありません。また、有向グラフを対象、準同型を矢印とする圏があり、これもまたデカルト閉圏です。[ 39 ] [ 38 ]
準同型順序に関して比較不可能なグラフは多数存在する。つまり、一方のグラフから他方のグラフへの準同型が存在しないグラフのペアが存在する。[ 40 ] それらを構成する1つの方法は、グラフGの奇数周長、すなわち最短の奇数長サイクルの長さを考えることである。奇数周長は、g個の頂点を持つサイクルグラフからGへの準同型が存在する最小の奇数gと同等である。このため、G → Hの場合、 Gの奇数周長はHの奇数周長以上となる。[ 41 ]
一方、G → Hの場合、 Gの彩色数はHの彩色数以下になります。したがって、G がHより厳密に大きい奇数周を持ち、かつ厳密に大きい彩色数を持つ場合、GとHは比較できません。[ 40 ] 例えば、Grötzsch グラフは 4 彩色で三角形フリー (周が 4 で奇数周が 5 ) なので、[ 42 ]三角形グラフK3とは比較できません。
奇数周と彩色数が任意に大きな値をとるグラフの例としては、クネーザーグラフ[ 43 ]や一般化ミシエルスキアン[ 44 ]がある。 両方のパラメータの値が同時に増加するようなグラフの列は、無限に多くの比較不可能なグラフ (準同型前順序の反鎖) を与える。[ 45 ]準同型前順序の密度 などの他の性質は、このようなファミリーを使用して証明できる。[ 46 ] 奇数周だけでなく、彩色数と周の値が大きいグラフの構成も可能だが、より複雑である (周とグラフ彩色を参照)。
有向グラフでは、比較不可能なペアを見つけるのははるかに簡単です。たとえば、頂点が1、2、…、n で、辺がi からi + 1 ( i = 1、2、…、n − 1) と n から1までである有向サイクルグラフC → n を考えます。C → nからC → k ( n、k ≥ 3)への準同型が存在するのは、 n がkの倍数である場合のみです。特に、n が素数である有向サイクルグラフC → nはすべて比較不可能です。[ 47 ]
グラフ準同型問題では、インスタンスはグラフのペア ( G、H ) であり、解はGからHへの準同型です。解が存在するかどうかを問う一般的な決定問題はNP 完全です。[ 48 ]しかし、許容されるインスタンスを制限すると、さまざまな異なる問題が生じ、その中にははるかに簡単に解決できるものもあります。左側の Gを制限する場合に適用される方法は、右側のHの場合とは大きく異なりますが、いずれの場合も、二分法 (簡単なケースと難しいケースの間の明確な境界) が既知であるか、または推測されています。
各インスタンスの右側に固定されたグラフHを持つ準同型問題は、 H彩色問題とも呼ばれます。H が完全グラフ K k の場合、これはグラフk 彩色問題であり、k = 0、1、2の場合は多項式時間で解けますが、それ以外の場合はNP 完全です。[ 49 ] 特に、グラフGのK 2彩色可能性は、 Gが二部グラフであることと同等であり、これは線形時間でテストできます。より一般的には、Hが二部グラフであるときはいつでも、H彩色可能性はK 2彩色可能性 (またはHが空/辺なしの場合はK 0 / K 1彩色可能性)と同等であり、したがって同様に簡単に判定できます。[ 50 ] Pavol HellとJaroslav Nešetřil は、無向グラフの場合、他のケースは扱いにくいことを証明しました。
これは、H彩色問題をNP完全問題またはP問題に分割し、中間ケースがないため、（無向）グラフ準同型に対する二分定理としても知られています。有向グラフの場合、状況はより複雑で、実際には制約充足問題の複雑さを特徴付けるというはるかに一般的な問題と同等です。[ 53 ]有向グラフのH彩色問題は、他の種類の制約を持つCSPと同じくらい一般的で多様であること がわかります。 [ 54 ] [ 55 ]形式的には、（有限）制約言語（またはテンプレート）Γは、有限ドメインと、このドメイン上の有限個の関係の集合です。CSP( Γ )は、インスタンスがΓ内の制約のみを使用することが許される制約充足問題です。
直感的に言えば、これは、有向グラフHのH彩色問題に適用されるすべてのアルゴリズム的手法または複雑性の結果が、一般的な CSP にも同様に適用されることを意味します。特に、Hell–Nešetřil の定理を有向グラフに拡張できるかどうかを問うことができます。上記の定理により、これは CSP 二分法に関する Feder–Vardi 予想 (別名 CSP 予想、二分法予想) と同等であり、すべての制約言語Γに対して、CSP( Γ ) は NP 完全または P に属すると述べています。 [ 48 ]この予想は、2017 年に Dmitry Zhuk と Andrei Bulatov によって独立に証明され、次の系が得られました。
入力インスタンスの左側に固定された単一のグラフGを持つ準同型問題は、総当たりで時間 | V ( H )| O(| V ( G )|)で解くことができ、これは入力グラフHのサイズに関して多項式時間です。[ 56 ]言い換えれば、この問題は、サイズが制限されたグラフGの場合、自明に P に属します。興味深いのは、サイズ以外に、 Gのどのような特性が多項式アルゴリズムを可能にするかということです。
重要な特性は、グラフがどれだけ木のような形をしているかを示す尺度である木幅であることが判明した。木幅が最大kのグラフGとグラフHの場合、準同型問題は標準的な動的計画法のアプローチで時間 | V ( H )| O( k )で解くことができる。実際、Gのコアの木幅が最大kであると仮定するだけで十分である。これは、コアが不明な場合でも成り立つ。[ 57 ] [ 58 ]
| V ( H )| O( k )時間アルゴリズムの指数は大幅に下げることはできません。指数時間仮説(ETH)を仮定すると、入力が無制限の木幅を持つ任意のクラスのグラフに限定されていても、実行時間 | V ( H )| o(tw( G ) /log tw( G ))のアルゴリズムは存在しません。[ 59 ] ETH はP ≠ NPに似た未証明の仮定ですが、より強力です。同じ仮定の下では、多項式時間アルゴリズムを得るために使用できる他の特性も実質的にありません。これは次のように形式化されます。
問題は、 Gに任意に大きく依存する時間で少なくとも解決可能であり、かつHのサイズに対しては固定多項式依存性を持つかどうかを問うことができる。Gを木幅が制限されたコアを持つグラフのクラスに限定すれば答えは再び肯定であり、他のすべてのクラスでは否定である。 [ 58 ]パラメータ化された複雑性 の言葉で言えば、これは、準同型問題がGのサイズ (エッジ数) によってパラメータ化されたグラフは二分法を示します。コアは木の幅が制限されており、それ以外の場合はW[1]完全である。
制約充足問題（あるいは関係構造）についても、同様のことがより一般的に当てはまります。必要な仮定は、制約が有限個の変数のみを含むことができるということだけです（すべての関係は有限のアリティを持ち、グラフの場合は2です）。関連するパラメータは、主制約グラフのツリー幅です。[ 59 ]
