グラフ彩色エクスプローラー
頂点をドラッグし、辺を描き、手動または貪欲法アルゴリズムでグラフを彩色しましょう — クリークによる下限が、本当に必要な色数を明らかにします。
本当に必要な色数はいくつか？ 🖖
彩色数χ(G)は、どの辺も同じ色の2頂点を結ばないようにするために必要な最小の色数です。これを厳密に求めるのはNP困難です — 最良の一般的な保証は、クリークによる下限（サイズkのクリークは少なくともk色を要求する）と貪欲法による上限（次数の降順で彩色するWelsh-Powell法は、最大次数をΔとするとΔ+1色を超えて使うことはない）の間に収まります。平面グラフ（辺が交差せずに描けるグラフ）については、四色定理により常に4色で足りることが保証されています。これは1976年にコンピュータによって初めて証明され、網羅的な場合分けの計算機検証を必要とする数少ない重要な定理の一つとして今も残っています。グラフ彩色は現実の割り当て問題の基礎になっています。コンパイラのレジスタ割り当て、試験の時間割編成、無線周波数の割り当てはいずれも競合グラフの彩色問題に帰着します。
隣り合う頂点は違う色に — それがすべて 🖖
グラフ彩色はたった一つの規則に集約されます。どの辺も同じ色の2頂点を結んではならず、しかも使う色数はできるだけ少なくしたい。この条件だけがすべてを決めます。便利な目安として、偶数長の閉路は2色で塗れますが、奇数長の閉路は3色必要です — だから三角形(最小の奇数閉路)は決して2色では塗れません。ツールで両方を作り、衝突数を観察してみましょう。
貪欲彩色は派手に失敗しうる 🖖
頂点を一つずつ、常に空いている最小の色で塗るやり方は安全に思えますが、順序が決定的に効いてきます。クラウングラフと呼ばれる一群 — 2色で足りる2n個の頂点 — では、意地の悪い順序を選ぶと貪欲法はn色も使わされます。最悪の場合は際限なく悪化するため、ツールの自動彩色は次数の大きい順に頂点を並べ替え(Welsh-Powell法)、こうした罠を回避します。