コア（グラフ理論）

グラフ理論という数学の分野において、コアとはグラフ準同型性に関するグラフの振る舞いを記述する概念である。

すべての準同型が同型である場合、つまり の頂点の全単射である場合、グラフ はコアです。 ${\displaystyle C}$${\displaystyle f:C\to C}$${\displaystyle C}$

グラフのコアとは、次のような グラフである。${\displaystyle G}$${\displaystyle C}$

1. からへの準同型が存在する。${\displaystyle G}$${\displaystyle C}$
2. からへの準同型が存在し、${\displaystyle C}$${\displaystyle G}$
3. ${\displaystyle C}$このプロパティでは最小限です。

2 つのグラフが同型コアを持つ場合、それらのグラフは準同型同値または hom 同値であると言われます。

• 任意の完全グラフはコアです。
• 奇数の長さのサイクルはコアです。
• グラフがコアであるのは、 のコアが に等しい場合のみです。${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$
• 長さが偶数である 2 つのサイクル、およびより一般的には 2 つの 2部グラフはすべてhom 同値です。これらのグラフの核は、2 頂点の完全グラフK ₂です。
• ベックマン・クォールズの定理によれば、ユークリッド平面または任意の高次元ユークリッド空間上のすべての点上の無限単位距離グラフはコアである。

すべての有限グラフにはコアがあり、同型性を除いて一意に決定されます。グラフGのコアは常にGの誘導サブグラフです。 および の場合、グラフと は必然的に準同型的に同値です。 ${\displaystyle G\to H}$${\displaystyle H\to G}$${\displaystyle G}$${\displaystyle H}$

グラフが適切なサブグラフへの準同型性を持つかどうかをテストすることはNP 完全であり、グラフがそれ自身のコアであるかどうか (つまり、そのような準同型性が存在しないかどうか) をテストすることは共同 NP 完全です (Hell & Nešetřil 1992)。

• Godsil, Chris、およびRoyle, Gordon。 代数的グラフ理論。Graduate Texts in Mathematics、Vol. 207。Springer-Verlag、ニューヨーク、2001年。第6章セクション2。
• 地獄、パボル。Nešetřil、Jaroslav (1992)、「グラフの核心」、離散数学、109 (1–3): 117–126、doi : 10.1016/0012-365X(92)90282-K、MR  1192374。
• Nešetřil, Jaroslav ; Ossona de Mendez, Patrice (2012)、「命題 3.5」、Sparsity: Graphs, Structures, and Algorithms、Algorithms and Combinatorics、vol. 28、Heidelberg: Springer、p. 43、doi :10.1007/978-3-642-27875-4、ISBN 978-3-642-27874-7、MR  2920058。