グラフ彩色電卓

無向グラフの彩色数と有効な頂点彩色を求めます。エッジまたは隣接リストを入力すると、最小の色数、色の割り当て、DSATURアルゴリズムによるステップバイステップの解決策、およびインタラクティブな SVG グラフ可視化を表示します。

グラフ彩色電卓

⚡ 例を試す:

4-サイクル C₄ 三角形 K₃ 完全グラフ K₅ 五角形 C₅ 車輪グラフ W₆ 二部グラフ K₃,₃ 隣接リストのサンプル試験のスケジューリング

入力形式

⬌ エッジリスト

⧇ 隣接リスト

グラフデータ

エッジ形式: A-B または A B、カンマまたは改行で区切ります。最大 60 頂点および 600 エッジまで。

隣接形式: A: B, C, D — 1行に1頂点、その後に隣接する頂点を記述します。

アルゴリズム

自動設定では、小さなグラフには厳密なバックトラッキング、大きなグラフには DSATUR を選択します。

Embed グラフ彩色電卓 Widget

グラフ彩色電卓

グラフ彩色電卓は、任意の無向グラフの彩色数 χ(G) と有効な頂点彩色を計算します。グラフをエッジリストまたは隣接リストとして入力すると、隣接する2つの頂点が同じ色を共有しないために必要な最小の色数が、インタラクティブな SVG 可視化、アニメーション化された DSATUR トレース、および各頂点にどの色が割り当てられたかの詳細な内訳とともに表示されます。

グラフ彩色とは何ですか？

グラフ G = (V, E) の適正な頂点彩色とは、すべてのエッジの端点が異なる色になるように、各頂点に色を割り当てることです。このような彩色が存在する最小の色数を彩色数（χ(G)と記述）と呼びます。χ(G) の計算は一般に NP 困難ですが、この問題は美しい数学的理論を持ち、試験のスケジューリング、無線周波数の割り当て、コンパイラのレジスタ割り当て、平面地図に関する有名な四色定理など、多くの実用的な応用があります。

彩色数の定義

χ(G) = min { k : G が適正な k-彩色を許容する }

主要な定理と境界

自明な境界: 任意のグラフについて 1 ≤ χ(G) ≤ |V|。
クリーク下限: χ(G) ≥ ω(G)。ここで ω(G) は最大クリークのサイズ。
二部グラフの特性: χ(G) ≤ 2 であるための必要十分条件は、G に奇サイクルが含まれないこと（ケーニヒの定理）。
ブルックスの定理: G が完全グラフまたは奇サイクルでない限り、χ(G) ≤ Δ(G)。ここで Δ(G) は最大次数。
四色定理: すべての平面グラフは 4-彩色可能。
グリーディ上限: いかなるグリーディアルゴリズムも、高々 Δ(G) + 1 色しか使用しない。

この電卓で使用されているアルゴリズム

DSATUR (飽和度に基づく彩色)

1979年に Daniel Brélaz によって導入された DSATUR は、グラフ彩色において最も強力な実用的ヒューリスティックの1つです。彩色済みの隣接頂点が最も多く、異なる色を使用している未彩色の頂点（飽和度が高い頂点）を繰り返し選択し、隣接頂点が使用していない最小の色を割り当てます。DSATUR は二部グラフや多くの構造化されたグラフ群において最適であることが証明されており、数百の頂点を持つグラフでもミリ秒単位で高品質な彩色を生成します。

Welsh-Powell

Welsh-Powell アルゴリズムは、頂点を次数の降順にソートし、グリーディに彩色します。計算時間は O(|V|²) で、高々 Δ(G) + 1 色を保証します。非常に高速で、多くの場合において優れた第一近似となりますが、局所的な構造が多様なグラフでは DSATUR に劣ることがあります。

グリーディ (入力順)

最も単純なアルゴリズムです。入力された順序で頂点を走査し、既に彩色された隣接頂点が使用していない最小の色を各頂点に割り当てます。出力は入力順序に左右されますが、ランダムな順序にすることで、よりスマートなヒューリスティックと比較するためのベースラインを提供します。

厳密なバックトラッキング

小さなグラフ（最大約18頂点）の場合、電卓は k = 2, 3, 4, ... を試し、深さ優先バックトラッキングでグラフを k-彩色しようとすることで、真の彩色数を見つけることができます。検索では頂点を次数の降順に並べ替え、使用可能な色がない場合に枝刈りを行います。厳密アルゴリズムが成功した場合、結果には「厳密な結果」と表示されます。

入力形式

エッジリスト

各エッジを、ハイフン、スペース、または矢印で区切られた2つの頂点ラベルとして記述します。エッジ間はカンマまたは改行で区切ってください。頂点ラベルには英字、数字、アンダースコアが使用可能です。例:

A-B, B-C, C-D, D-A
A-C

隣接リスト

各頂点、コロン、そしてカンマ区切りの隣接頂点リストを記述します。例:

A: B, C, D
B: A, D
C: A
D: A, B

自己ループは、頂点を自分自身と異なる色にすることができないため拒否されます。重複するエッジは自動的に除去され、グラフは無向グラフとして扱われます。

この電卓の使い方

形式を選択する: ラジオボタンでエッジリストと隣接リストを切り替えます。
グラフを入力する: データを貼り付けるか、クイックサンプル（三角形、完全グラフ K₅、ピーターセングラフ風の車輪グラフ、二部グラフ K₃,₃、試験スケジューリング）をクリックします。
アルゴリズムを選択する: 最適なデフォルト設定の「自動」のままにするか、Welsh-Powell、グリーディ、DSATUR、または厳密なバックトラッキングを強制的に指定します。
「グラフを彩色する」をクリック: 彩色数、色ごとのリスト、ドラッグ可能なノードを備えたインタラクティブな SVG、およびステップバイステップのアニメーショントレースが下に表示されます。
探索する: 「再生」を押してアルゴリズムが頂点を彩色する様子を観察したり、ノードをドラッグしてレイアウトを変更したり、「戻る/次へ」を使用して手動でトレースを確認したりできます。

グラフ彩色の実用的な応用

試験のスケジューリング

各試験を頂点とし、少なくとも1人の学生を共有する試験間にエッジを引きます。k 色による適正な彩色は、学生に競合が発生しない k 個の時間枠によるスケジュールを提供します。彩色数は、必要な最小の時間枠数となります。

無線周波数の割り当て

互いに干渉範囲内にある送信機は、異なる周波数で放送する必要があります。干渉グラフの彩色数は、必要な最小の周波数数となります。

レジスタ割り当て

コンパイラにおいて、変数の生存期間を頂点とし、2つの生存期間が時間的に重なる場合にエッジを引きます。k-彩色は、衝突なしに変数を k 個の CPU レジスタに割り当てます。

地図の彩色

境界を接する国々は異なる色にする必要があります。四色定理（Appel-Haken, 1976）は、いかなる平面地図においても4色あれば十分であることを証明しています。

数独と制約パズル

完成した数独は、81個のセルを頂点とし、同じ行、列、または 3×3 のボックス内のセル同士をエッジで結んだグラフの 9-彩色です。グラフ彩色は、多くの制約充足パズルの数学的な核となっています。

興味深い特殊なケース

完全グラフ K_n: χ(K_n) = n。すべての頂点のペアが隣接しているため、すべての色は異なっていなければなりません。
サイクル C_n: n が偶数の場合は χ(C_n) = 2、n が奇数の場合は 3。
木: 頂点数が2以上の任意の木は χ = 2（木は二部グラフです）。
二部グラフ: 少なくとも1つのエッジを持つ場合、χ = 2。
ピーターセングラフ: χ = 3 である有名な3-正則グラフ。
車輪グラフ W_n: n-サイクルに中心頂点が結合したもの。n が偶数の場合は χ = 3、n が奇数の場合は 4。

よくある質問

グラフの彩色数とは何ですか？

彩色数 χ(G) は、隣接する2つの頂点が同じ色を共有しないようにグラフの頂点を彩色するために必要な最小の色数です。二部グラフの彩色数は最大で2です。三角形を含むグラフの彩色数は少なくとも3です。また、ブルックスの定理により、完全グラフと奇サイクルを除いて、彩色数が最大次数を超えることはありません。

この電卓はどのアルゴリズムを使用していますか？

小さなグラフの場合、電卓は厳密なバックトラッキング検索を実行して真の彩色数を見つけます。大きなグラフの場合は、DSATUR ヒューリスティックを使用します。これは、彩色済みの隣接頂点が最も多い未彩色の頂点を繰り返し彩色する手法です。アルゴリズムのドロップダウンから Welsh-Powell や単純なグリーディを強制することもできます。

グラフをどのように入力すればよいですか？

エッジリストモードを使用して A-B のように1行に1つのエッジを入力するか、A-B, B-C, C-A のようにカンマ区切りで入力します。隣接リストモードを使用する場合は、各頂点の後にコロンとその隣接頂点を記述します（例: A: B, C）。自己ループは頂点を自分自身と異なる色に彩色できないため、入力できません。

なぜ DSATUR は常に真の彩色数を見つけるわけではないのですか？

グラフ彩色は NP 困難な問題であるため、常に最小の色数を見つけることができる高速な既知のアルゴリズムは存在しません。DSATUR は非常に優れた実用的なヒューリスティックであり、多くの場合で真の彩色数と一致しますが、特殊なグラフでは必要以上の色を使用することがあります。この電卓では、使用された色数と最大クリークから算出された下限の両方を報告するため、結果の精度を判断できます。

グラフ彩色の実世界での用途は何ですか？

グラフ彩色は、試験のスケジューリング（試験を頂点、競合をエッジ、色を時間枠とする）、無線周波数の割り当て（送信機を頂点、干渉をエッジとする）、コンパイラのレジスタ割り当て、地図の彩色、数独の解決、競合制約下でのジョブ割り当てなどのモデル化に使われます。

彩色数は常に最大クリークと等しいですか？

いいえ。クリーク数 ω(G) は常に彩色数 χ(G) の下限ですが、これらが等しくなるのは二部グラフ、木、区間グラフ、弦グラフなどのパーフェクトグラフに限られます。一般的なグラフでは、χ(G) は ω(G) よりも大きくなることがあり、典型的な例として三角形を含まないにもかかわらず任意の数の色を必要とする Mycielski グラフが挙げられます。

この電卓で扱える最大のグラフはどれくらいですか？

この電卓は最大60頂点、600エッジまで対応しています。厳密アルゴリズムについては、頂点数が約18個を超えるとバックトラッキングが遅くなりすぎるため、DSATUR にフォールバックする場合があります。実用上は、教室での例題、試験のスケジューリング問題、および小規模から中規模のアプリケーションのほとんどをカバーしています。