グラフ彩色

この計算機について

グラフ彩色計算機は、彩色数 χ(G) — 同じ色の 2 つの頂点を結ぶ辺がないようにグラフの頂点を彩色するのに必要な最小の色数 — を求め、最適な彩色の一例を示します。頂点数と辺のリストを入力すると、分枝限定法で χ を厳密に計算し、最大次数 Δ と最大クリーク ω(χ の下界)を報告し、二部グラフや完全グラフを判定し、彩色されたグラフを描画します。スケジューリング、レジスタ割り当て、地図の彩色、彩色数の研究に役立ちます。

グラフの彩色方法

1. 頂点数を入力します。頂点は 1 から n まで番号付けされます。
2. 辺を 1-2, 2-3 のようなペアで列挙します — 接続 1 つにつき 1 ペア。
3. 彩色数 χ(G) と各頂点に割り当てられた色を確認します。
4. χ を最大クリーク ω と比較して、なぜその色数が必要なのかを確認するか、プリセットを読み込んで探求しましょう。

一般的な例

• 三角形(K₃)は 3 色が必要 — すべての頂点のペアが隣接しています。
• 偶閉路は二部グラフで 2 色のみで済みますが、C₅ のような奇閉路は 3 色が必要です。
• 完全グラフ Kₙ はちょうど n 色が必要です。
• サイズ ω の最大クリークは少なくとも ω 色を必要とするため、χ(G) ≥ ω です。
• グレッチュグラフは三角形を含まないのに 4 色が必要なため、χ はクリーク数を上回ることがあります。