グラフ彩色・色数と割当
バグ・不具合を報告
有限無向グラフを指定した番号の色で頂点彩色し、使用色数の最小化を検討する。
頂点に色番号1~Kを割り当て、隣接頂点の色が異なることを条件にします。最適性は厳密探索が完了した場合に限り表示します。
項目を入力・選択してから「計算する」を押してください。
必要な入力・選択は2項目です。
計算結果
—色
- 判定
- —
- 使用色数の下界
- —色
- 使用色数の上界
- —色
- 厳密探索の実行操作数
- —操作
値を入力して計算してください。
この計算機は使いやすかったですか?
回答はサイト改善のために保存します。入力値・計算結果は送りません。
ありがとうございます。よかったら、上の共有ボタンからこの計算機を紹介しませんか?
計算方法・適用範囲・出典
計算方法
無向辺{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。