ケンペチェーン

数学において、ケンペ連鎖は主に四色定理の研究に用いられる手法である。直感的には、グラフ上の交互の色 の頂点が連結した連鎖である。

ケンプ連鎖は、アルフレッド・ケンプが四色定理の証明を試みた際に初めて使用されました。 ^[1]彼の証明は不完全であることが判明しましたが、ケンプ連鎖の方法は、ケネス・アペルとヴォルフガング・ハーケンによる最初の成功した証明など、有効な現代の証明の成功に不可欠です。^{[2] [3]さらに、この方法は}、パーシー・ジョン・ヒーウッドによる五色定理の証明にも使用されています。これは、四色定理のより弱いバージョンですが容易に証明されました。^[1]

「ケンペ連鎖」という用語は、2 つの異なるが関連する意味で使用されます。

G が頂点集合 V を持つグラフであり、与えられた色付け関数

${\displaystyle c:V\to S,}$

ここで、S は色の有限集合であり、少なくとも 2 つの異なる色aとbを含みます。v が色aの頂点である場合、 vを含むGの( a , b )-ケンペ連鎖は、 v を含み、頂点がすべてaまたはb に色付けされているVの最大連結部分集合です。

上記の定義は、ケンペが取り組んだものです。通常、集合Sには 4 つの要素 (4 色定理の 4 色) が​​あり、cは適切な色付け、つまり、V内の隣接する頂点の各ペアに異なる色が割り当てられます。これらの追加条件により、aとb は使用可能な 4 色のうちの 2 つとなり、( a , b )-ケンペ連鎖の各要素は、連鎖内の他の色の要素のみに隣接します。

現代のコンピュータベースの4色定理の証明で使用されている、より一般的な定義は次の通りである。再び、Gがグラフであり、辺集合がEであると仮定し、今度は色付け関数が

${\displaystyle c:E\to S.}$

e が色aが割り当てられた辺である場合、 eを含むGの( a , b )-ケンペ連鎖は、 e を含み、辺がすべてaまたはbに色付けされているEの最大連結部分集合です。

この 2 番目の定義は、通常、Sに 3 つの要素、たとえばa、b、c があり、Vが立方体グラフ、つまりすべての頂点に 3 つの接続辺がある場合に適用されます。このようなグラフが適切に色付けされている場合、各頂点には 3 つの異なる色の辺が必要であり、ケンペ チェーンはパスになり、これは最初の定義の場合よりも単純になります。

4色定理において、ケンペはすべてのグラフが必ず5以下の頂点を持つか、または隣接する頂点と呼ばれる他の5つの頂点に接する頂点を持つことを証明することができた。したがって、4色定理を証明するには、5以下の頂点はすべて4色可能であることを証明すれば十分である。ケンペは次数4​​の場合を証明し、ケンペ連鎖を使用して次数5の部分的な証明を与えることができた。^[4]

この場合、ケンペ連鎖は、次数 4 のどの頂点も、それ自体とは異なる 4 つの異なる色に接してはならないという考え方を証明するために使用されます。まず、頂点vと 4 つの頂点を隣接頂点として持つグラフを作成できます。頂点vを削除すると、残りの頂点を 4 色にすることができます。色は (時計回りの順序で) 赤、黄、青、緑に設定できます。この状況では、赤と青の隣接頂点を結ぶケンペ連鎖、または緑と黄色の隣接頂点を結ぶケンペ連鎖が存在できますが、両方が存在することはありません。これは、これら 2 つのパスが必ず交差し、交差する頂点を赤または青と緑または黄色の両方で同時に着色することはできないためです。ケンペ連鎖が緑と黄色の隣接頂点を接続していると仮定すると、赤と青の間には必然的にケンペ連鎖が存在しないことになります。したがって、元の頂点v をグラフに戻すときは、赤い頂点とその隣接頂点 (赤い頂点を含むので、赤い頂点は青になります) の色を反転するだけで済みます。これにより、頂点vの隣接頂点は青が 2 つ、緑が 1 つ、黄色が 1 つになります。つまり、頂点v の隣接頂点は 3 つの異なる色のみであり、頂点v を赤に色付けできることになります。これにより、4 色のグラフが作成されます。^[5]

ケンペ連鎖は、カラーリング拡張の問題を解決するために使用されてきた。^{[6] [7]ケンペ連鎖は}レジスタ割り当てにも使用できる。^[要出典]

• 四色定理
• 五色定理
• グラフの色付け