グラフ彩色・色数と割当

有限無向グラフを指定した番号の色で頂点彩色し、使用色数の最小化を検討する。

頂点に色番号1~Kを割り当て、隣接頂点の色が異なることを条件にします。最適性は厳密探索が完了した場合に限り表示します。

項目を入力・選択してから「計算する」を押してください。

必要な入力・選択は2項目です。

頂点と色の制約必須
行頂点ID固定色 任意禁止色(例:1,3) 任意操作
1
2

3列を左端の欄へタブ区切りで貼り付けられます。50行まで。

頂点IDは英数字で開始(以降は_.:-も可)。色は1からの番号。固定色・禁止色を使わなければ空欄にします。

無向辺任意
行頂点ID 1頂点ID 2操作
1
2

2列を左端の欄へタブ区切りで貼り付けられます。1000行まで。

頂点表にあるIDを入力します。A–BとB–Aは同じ辺として扱い、自己ループは彩色不能です。辺がなければ空欄にします。

色番号1~上限の範囲で割当。空欄は頂点数を上限にします。禁止色・固定色もこの範囲から指定します。

DSATURだけでは最小色数や無解を証明できません。厳密探索は上限到達時、実行可能または未確定で終了します。

空欄時は20,000操作。探索ノードと候補色の検査を数えます。DSATUR方式では使いません。


計算結果

値を入力して計算してください。

お気に入り一覧

計算方法・適用範囲・出典

計算方法

無向辺{u,v}ごとにc(u)≠c(v)。各頂点の固定色・禁止色を守り、使用する異なる色番号の個数|{c(v)}|を最小にします。番号の範囲は1~Kです。DSATURは隣接する彩色済み頂点の色の種類数を優先して割り当てます。下界は実際に見つかったクリークの頂点数および異なる固定色数の大きい方です。上界は検証した割当の使用色数。厳密探索は下界・既知の実行可能解を利用して改善の余地がない枝を除外し、残りをすべて調べ終えた場合に限り最適とします。探索が停止した場合は上界を最適値とみなしません。

頂点別の色番号、使用色数、証明できる下界と実行可能解の上界、最適/実行可能/未確定/無解の判定。

計算例(架空の数値)

三角形A–B–C–Aは3色必要です。4頂点の輪C₄は2色、辺のない複数頂点は制約がなければ1色です。これらは無向グラフの基本例です。

適用対象と限界

頂点50件以下、辺1000行以下、色番号1~50の有限無向グラフ。有向グラフ、辺彩色、リスト彩色の無限色集合、複数頂点の同色指定以外の高度な制約、ドラッグ操作での描画、50頂点超、1000行超の辺、探索終了しない大規模インスタンスは対象外。。

採用した方式

  • 制約付きDSATUR(v1.0):対象範囲 任意の有限単純無向グラフ、色番号1~K、固定/禁止色/適用地域 global
  • 分枝限定による最小色数探索(v1.0):対象範囲 同じ制約と探索予算の範囲での完全性判定/適用地域 global

方法と出典

方法:E1220 DSATUR + exhaustive branch-and-bound v1.0 (2026-11-14)。データ記録日:2026-11-14。