グラフ準同型

数学のグラフ理論分野において、グラフ準同型（グラフじゅんどうけい、テンプレート:Lang-en-short）は、二つのグラフの間の構造を保つ写像である。より具体的には、二つのグラフの頂点集合の間の関数であって、隣接する頂点を隣接する頂点に写すもののことである。

準同型は各種のグラフ彩色の概念を一般化し、特定のスケジューリングや周波数割り当てなどの重要なクラスの制約充足問題を表現することを可能にするテンプレート:Sfn。準同型は合成可能であるため、豊かな代数的構造をもたらす。すなわち、グラフ上の前順序、テンプレート:仮リンク、および圏（無向グラフの圏と有向グラフの圏の二つ）であるテンプレート:Sfn。二つのグラフ間の準同型を求めることの計算量は一般には過大であるが、多項式時間で解ける特殊な場合について多くのことが知られている。扱いやすい場合と扱いにくい場合の境界は活発な研究領域となっているテンプレート:Sfn。

定義

本記事において特に断らない限り、「グラフ」は有限、無向、ループを許容、多重辺（並行辺）は不許容とする。グラフ $G = (V (G), E (G))$ からグラフ $H = (V (H), E (H))$ へのグラフ準同型 テンプレート:Math（テンプレート:Math と書く）は、辺を保存する $V (G)$ から $V (H)$ への関数である。形式的には次のように定義される。

$V (G)$ の任意の頂点対 $u, v$ について、 $(u, v) \in E (G)$ ならば $(f (u), f (v)) \in E (H)$ である。

G から H への準同型が少なくとも一つ存在するとき、G は H に準同型的である（あるいはH-彩色可能）といい、しばしば単に

テンプレート:Math

と書かれる。

上の定義は有向グラフに拡張される。すなわち、準同型 f : G → H について、(u,v) が G の弧（テンプレート:仮リンク）であるとき、(f(u),f(v)) は H の弧となる。

G から H への単射準同型（すなわち G の異なる頂点を H の異なる頂点へ写す準同型）が存在するのは、G が H のある部分グラフと同型である場合に限る。準同型 f : G → H が全単射であり、その逆写像テンプレート:Math もグラフ準同型であるとき、f はグラフ同型であるテンプレート:Sfn。

テンプレート:仮リンクは特別な種類の準同型であり、位相幾何における被覆写像の定義と多くの性質を反映するものであるテンプレート:Sfn。それは全射準同型（すなわち各頂点に写されるものが存在する）であって、局所的にも全単射、つまり各頂点のテンプレート:仮リンク上で全単射であるものとして定義される。

グラフ同相は準同型とは直接関係のない別概念で、大まかにいえば単射性を要求するが、辺を（辺だけでなく）路に写すことを許す。テンプレート:仮リンクはさらに緩やかな概念である。

コアとリトラクト

テンプレート:Main

グラフ G と H が準同型的に同値とは、G → H かつ H → G が成り立つことである。写像は必ずしも全射でも単射でもない。たとえば完全二部グラフ K_2,2 と K_3,3 は準同型的に同値である。

リトラクションとは、グラフ G からその部分グラフ H への準同型 r であって、H の各頂点 v に対して r(v) = v を満たすものである。この場合、部分グラフ H は G のリトラクトと呼ばれるテンプレート:Sfn。

コアとは、真の部分グラフへの準同型を持たないグラフである。同値な定義として、真の部分グラフへリトラクトしないグラフともいえるテンプレート:Sfn。あらゆるグラフ G は、（同型を除いて）ただ一つのコアと準同型的に同値であり、これを G の「コア」と呼ぶ。ただし、無限グラフについては一般には成立しないテンプレート:Sfn。同じ定義は有向グラフにも適用され、有向グラフもまた一意なコアと同値である。

たとえば、すべての完全グラフ K_n とすべての奇長の閉路はコアである。3彩色可能で三角形（すなわち部分グラフとして完全グラフ K₃）を含むすべてのグラフ G は K₃ と準同型的に同値である。同様に、少なくとも1本の辺を持つあらゆる二部グラフは K₂ と同値であるテンプレート:Sfn。

彩色との関係

ある整数 k についてのk-彩色は、グラフ G の各頂点に k 色のうちの一つを割り当てるものであって、各辺の両端が異なる色となるようにしたものである。G の k-彩色は、G から完全グラフ K_k への準同型と正確に対応するテンプレート:Sfnm。実際、K_k の頂点は k 色に対応し、K_k の頂点として二つの色が隣接するのは、それらが異なる場合に限る。したがって、ある関数が K_k への準同型を定義するのは、それが G の隣接頂点を異なる色に写す場合、すなわち k-彩色である場合に限る。特に、G が k-彩色可能であるのは K_k-彩色可能である場合に限る。

準同型 G → H と H → K_k が存在すれば、それらの合成 G → K_k もまた準同型であるテンプレート:Sfn。言い換えれば、グラフ H が k 色で彩色可能で、G から H への準同型が存在するならば、G もまた k-彩色可能である。したがって、G → H は χ(G) ≤ χ(H)（ここで χ はグラフの彩色数を表す）を含意するテンプレート:Sfn。

バリアント

一般の準同型は一種の彩色として考えることもできる。固定されたグラフ H の頂点を利用可能な「色」、H の辺をどの色が互いに「両立可能」であるかを記述するものと解釈すれば、G の H-彩色は、隣接頂点が両立可能な色を持つように G の頂点に色を割り当てることになる。多くの彩色概念はこのパターンに当てはまり、様々なグラフ族へのグラフ準同型として表現できる。テンプレート:仮リンク、分数・b-重彩色、テンプレート:仮リンク、有向グラフのテンプレート:仮リンク、テンプレート:仮リンクなどがこの枠組みに入る。

長い経路のない有向化

テンプレート:Main

もう一つの興味深い関係が、グラフの有向化に関するものである。無向グラフ G の有向化とは、各辺に対して二つの可能な方向のうち一つを選んで得られる有向グラフのことである。完全グラフ K_k の有向化の一例は、頂点 1,2,…,k と i < j なる各対に対する i から j への弧を持つ推移的テンプレート:仮リンク T_k である。有向化どうしの準同型は無向グラフ G と H の間の準同型を与える。逆に、無向グラフ間の準同型 G → H が与えられれば、H の任意の有向化を G の有向化に引き戻せる。したがって、グラフ G が k-彩色可能である（K_k への準同型を持つ）のは、G のある有向化が T_k への準同型を持つ場合に限るテンプレート:Sfn。

民間伝承的な定理によれば、任意の k について、有向グラフ G が T_k への準同型を持つのは、有向経路 P_k+1 からの準同型を許さないときに限るテンプレート:Sfn。したがって、グラフが k-彩色可能であるのは、有向化のあるものが P_k+1 からの準同型を許さない場合に限る。この主張はやや強めることができ、あるグラフが k-彩色可能であるのは、ある有向化が長さ k の有向経路（部分グラフとしての P_k+1）を含まない場合に限る、と述べられる。これがガライ–ハッセ–ロイ–ヴィタヴェルの定理である。

制約充足問題との関係

例

非連続の曜日のグラフ H。C₇ の補グラフおよび円状クリーク K_7/2 と同型。

一部のスケジューリング問題はグラフ準同型を求める問題としてモデル化しうるテンプレート:Sfn テンプレート:Sfn。例として、複数のワークショップ講座を、同一学生が受講する二つの講座が時間的にあまり近くならないようにカレンダーの時間枠に割り当てたい場合を考える。講座はグラフ G を成し、共通の学生が受講する二講座間には辺がある。時間枠はグラフ H を成し、十分時間的に離れた二枠間には辺がある。たとえば、各学生がワークショップ講座を非連続の日に受けられる週次スケジュールを希望するならば、H は C₇ の補グラフとなる。G から H へのグラフ準同型は指定通り講座を時間枠に割り当てるスケジュールを与える。

単純な周波数割当問題も同様にモデル化しうる。すなわち、無線ネットワーク内の複数の送信機がデータ送信に用いる周波数チャネルを選ぶ場合、干渉を避けるため地理的に近い送信機は周波数の離れたチャネルを用いるべきである。この条件を一定の閾値で近似すれば、有効なチャネル選択は送信機グラフ G からチャネルグラフ H へのグラフ準同型に対応するテンプレート:Sfn。

いずれの場合も、制約充足問題（グラフ準同型問題を一般化する）は個々の選好や割当数の上限といった追加条件の表現を可能にするテンプレート:Sfn。

形式的な見方

グラフや有向グラフは、関係的な構造（集合とその上の関係の組として定義される）のはるかに一般的な概念の特殊な場合とみなせる。有向グラフは定義域（頂点集合）上の唯一の二項関係（隣接）を持つ構造である。この見方の下、そのような構造の準同型はまさにグラフ準同型である。一般に、ある関係的構造から別の関係的構造への準同型を求める問題は制約充足問題（CSP）である。グラフの場合はより複雑な CSP を理解する具体的な出発点となる。グラフ準同型を求める多くのアルゴリズム手法（バックトラック、テンプレート:仮リンク、局所探索など）はすべての CSP に適用されるテンプレート:Sfn。

準同型の構造

準同型の合成は準同型であるテンプレート:Sfn。特に、グラフ上の関係 → は推移的（かつ自明に反射的）なので、グラフ上の前順序をなすテンプレート:Sfn。準同型的同値のもとでの G の同値類を [G] とする。同値類は [G] 中の一意なコアで代表することもできる。関係 → はこれらの同値類上の半順序をなすテンプレート:Sfn。

G から H への準同型は存在するが H から G への準同型は存在しないことを G < H と表す。関係 → は稠密順序である。すなわち、G < H を満たす任意の（無向）グラフ G, H に対して、G < K < H なるグラフ K が存在する（自明な場合 G = K₀ または K₁ を除く）。

準同型のもとでのグラフの同値類がなす半順序集合はテンプレート:仮リンクであり、[G] と [H] の結び（join）は非交和 [G ∪ H] の同値類、交わり（meet）はテンソル積 [G × H] として定義される。この束の結び既約元はまさに連結グラフである。交わり既約元はまさにテンプレート:仮リンクである。これらは、積 G × H が K への準同型を持つのは G または H の一方が持つときに限られるようなグラフ K である。乗法的グラフの同定はテンプレート:仮リンクの中核をなす。

グラフ準同型はまた圏をなす（グラフを対象、準同型を射とする）テンプレート:Sfn。始対象は空グラフであり、終対象は 1 頂点でその頂点にループを持つグラフである。グラフのテンソル積は圏論的な直積であり、指数グラフはこの圏の指数対象である。これらの操作は常に定義されるので、グラフの圏はデカルト閉圏である。同じ理由で、準同型のもとでのグラフの同値類の束は実はハイティング代数である。

有向グラフについても同じ定義が適用される。特に → は有向グラフの同値類上の半順序である。無向グラフの同値類上の順序 → とは異なるが、その部分順序として含む。有向グラフの → は再び分配束かつハイティング代数であるが、稠密ではない。

比較不能なグラフ

準同型前順序に関して比較不能なグラフの対は多く存在する（すなわち、いずれから他方への準同型も存在しない対）テンプレート:Sfn。それらを構成する一つの方法は、グラフのテンプレート:仮リンク――最短の奇数長閉路の長さ――を考えることである。同値的に、g 頂点の閉路グラフから G への準同型が存在する最小の奇数 g である。したがって、G → H ならば G の奇内周は H の奇内周以上であるテンプレート:Sfn。

他方、G → H ならば G の彩色数は H の彩色数以下である。したがって、G が H より真に大きな奇内周と彩色数を持つならば、G と H は比較不能である。たとえばグレッチュ・グラフは4彩色可能で三角形を持たない（内周 4、奇内周 5）ので、三角形グラフ K₃ と比較不能である。

奇内周と彩色数を任意に大きくとれるグラフの例にはクネーザーグラフや一般化テンプレート:仮リンクなどがある。

計算量

グラフ準同型問題では、入力は二つのグラフ (G,H) であり、解は G から H への準同型である。一般の決定問題（そもそも解が存在するか）はNP完全であるテンプレート:Sfn。しかし許容される入力を制限すると様々な問題が生じ、そのいくつかははるかに解きやすい。左側 G を制約する手法と右側 H を制約する手法は大きく異なるが、いずれの場合も二分性（易しい場合と難しい場合の間の明確な境界）が知られている、あるいは予想されている。

固定グラフへの準同型

入力の右側にグラフ H を固定した準同型問題は H-彩色問題とも呼ばれる。H が完全グラフ K_k の場合、これはグラフの k-彩色問題であり、k = 0, 1, 2 では多項式時間で解け、それ以外では NP完全であるテンプレート:Sfn。特に、K₂-彩色可能性はグラフの二部性と等しく、線形時間で判定可能である。

ヘルとネシェトジルは、無向グラフでは他の場合が扱いやすくないことを証明した。

ヘル–ネシェトジルの定理（1990年）: H-彩色問題は H が二部グラフのとき P に属し、そうでなければ NP完全であるテンプレート:Sfn。

これは（無向）グラフ準同型に対する「二分定理」とも呼ばれる。有向グラフの場合はより複雑で、実質的には制約充足問題の計算量を特徴づけるより一般的な問いと等価であるテンプレート:Sfn。フェダー・ヴァルディの定理（1998年）により、任意の制約言語 Γ に対して、CSP(Γ) は何らかの有向グラフ H に対する H-彩色問題と多項式時間帰着の下で等価である。この事実は、Dmitry Zhuk と Andrei Bulatov によって2017年に独立に証明された CSP 二分予想（フェダー・ヴァルディ予想）が正しいことを含意する。すなわち、固定 H に対する有向グラフ上の H-彩色問題は P か NP完全のいずれかである。

固定族からの準同型

入力の左側に単一の固定グラフ G を持つ準同型問題は、時間 |V(H)|^O(|V(G)|) で総当り探索で解くことができる。決定的な性質はテンプレート:仮リンク――グラフがどれほど木に近いかを測る指標――である。木幅が高々 k のグラフ G と任意のグラフ H に対して、準同型問題は時間 |V(H)|^O(k) の標準的な動的計画法で解ける。実際、G のコアが高々木幅 k であると仮定すれば十分である。

指数時間仮説（ETH）の下では、|V(H)|^O(k)-時間アルゴリズムの指数を著しく下げることはできない。同じ仮定の下では、グローエの定理により次が成り立つ。すなわち、計算可能なグラフ族 $𝒢$ に対して、 $G \in 𝒢$ なる入力についての準同型問題が P に属するのは、 $𝒢$ のグラフのコアが有界木幅を持つ場合、かつその場合に限る（ETH を仮定）。

脚注

テンプレート:Reflist

参考文献

一般書・解説

制約充足と普遍代数

束論と圏論

グラフ準同型

目次