← コンピューティング

グラフ彩色エクスプローラー

頂点をドラッグし、辺を描き、手動または貪欲法アルゴリズムでグラフを彩色しましょう — クリークによる下限が、本当に必要な色数を明らかにします。

インタラクティブシミュレーションを読み込んでいます...

本当に必要な色数はいくつか？

彩色数χ(G)は、どの辺も同じ色の2頂点を結ばないようにするために必要な最小の色数です。これを厳密に求めるのはNP困難です — 最良の一般的な保証は、クリークによる下限（サイズkのクリークは少なくともk色を要求する）と貪欲法による上限（次数の降順で彩色するWelsh-Powell法は、最大次数をΔとするとΔ+1色を超えて使うことはない）の間に収まります。平面グラフ（辺が交差せずに描けるグラフ）については、四色定理により常に4色で足りることが保証されています。これは1976年にコンピュータによって初めて証明され、網羅的な場合分けの計算機検証を必要とする数少ない重要な定理の一つとして今も残っています。グラフ彩色は現実の割り当て問題の基礎になっています。コンパイラのレジスタ割り当て、試験の時間割編成、無線周波数の割り当てはいずれも競合グラフの彩色問題に帰着します。

隣り合う頂点は違う色に — それがすべて

グラフ彩色はたった一つの規則に集約されます。どの辺も同じ色の2頂点を結んではならず、しかも使う色数はできるだけ少なくしたい。この条件だけがすべてを決めます。便利な目安として、偶数長の閉路は2色で塗れますが、奇数長の閉路は3色必要です — だから三角形(最小の奇数閉路)は決して2色では塗れません。ツールで両方を作り、衝突数を観察してみましょう。

貪欲彩色は派手に失敗しうる

頂点を一つずつ、常に空いている最小の色で塗るやり方は安全に思えますが、順序が決定的に効いてきます。クラウングラフと呼ばれる一群 — 2色で足りる2n個の頂点 — では、意地の悪い順序を選ぶと貪欲法はn色も使わされます。最悪の場合は際限なく悪化するため、ツールの自動彩色は次数の大きい順に頂点を並べ替え(Welsh-Powell法)、こうした罠を回避します。

全プロセスの詳細解説

  1. ピーターセングラフの真の彩色数 5 ステップ

    ピーターセングラフは 10 個の頂点、15 個の辺を持ち、三角形を含まない。したがってパネルは χ ≥ 2 と表示する。真の染色数を求めよ。これはピーターセングラフの状態である。

    この問題をツールで開く

    1. どのようなグラフからも 2 つの界が自明に得られる。すなわち、最大クリックの大きさ以上の色数が必要であることと、最大次数に 1 を加えた値を超える色数は決して必要としないことである。

      ω(G)≤χ(G)≤Δ(G)+1:Petersen has ω=2, Δ=3 ⟹ 2≤χ≤4\omega(G)\le\chi(G)\le\Delta(G)+1:\quad \text{Petersen has }\omega=2,\ \Delta=3\ \Longrightarrow\ 2\le\chi\le4

    2. ピーターセングラフの内周は 5 であるため、内部に三角形は一切存在せず、クリック数による下限は自明な 2 に潰れてしまう。それがパネルの報告する数値である。

      girth=5 ⟹ no triangle ⟹ ω=2, yet the graph is not bipartite\text{girth}=5\ \Longrightarrow\ \text{no triangle}\ \Longrightarrow\ \omega=2,\ \text{yet the graph is not bipartite}

    3. 2 色での彩色が可能なのはグラフが 2 部グラフである場合のみであり、2 部グラフであるとは奇サイクルが存在しないことを意味する。外側の五角形は 5 サイクルであるため、2 色での彩色は不可能である。

      bipartite  ⟺  no odd cycle; the outer 5-cycle is odd ⟹ χ≥3\text{bipartite}\iff\text{no odd cycle};\ \text{the outer 5-cycle is odd}\ \Longrightarrow\ \chi\ge3

    4. 三色で塗り分けられる。実際の塗り分けを一つ示せば、上界の証明として十分である。外側の五角形を一周する順に 1、2、1、2、3 と塗り、同じ順で五つの内側の頂点を 2、1、3、3、2 と塗る。それぞれ、同じスポーク上の外側の頂点と対応している。十五本すべての辺をたどると、どの辺でも両端の色は異なる。

      a 3-colouring exists ⟹ χ=3, strictly above the clique bound ω=2\text{a 3-colouring exists}\ \Longrightarrow\ \chi=3,\ \text{strictly above the clique bound } \omega=2

    5. ブルックスの定理は上限側から同じことを示している。完全グラフでも奇サイクルでもない連結グラフが必要とする色数は高々 Δ 色であり、ここでは Δ は 3 である。

      ∣V∣=10, ∣E∣=15, Δ=3: Brooks’ theorem gives χ≤3 for a connected non-complete graph|V|=10,\ |E|=15,\ \Delta=3:\ \text{Brooks' theorem gives }\chi\le3\ \text{for a connected non-complete graph}

    解答

    3 であり、これはパネルが証明できる下限を厳密に上回っている。ピーターセングラフにおける最大のクリックは単一の辺であるため、クリック数による下限は χ ≥ 2 しか与えず、真の値から 1 だけズレている。このギャップは見た目以上に重要である。ピーターセングラフは「彩色の難しさはクリックに由来する」という直感に対する標準的な反例であり、三角形を含まないにもかかわらず 4 色、5 色、あるいは希望する任意の色の数を必要とするグラフが存在する（ミシエルスキーの構成法を用いれば望む通りに作ることができる）。したがって、クリック数は任意に大きな誤差を生じ得る下限に過ぎず、これが三角形の検出は容易であるのに対して染色数を求める問題が NP 困難である理由である。ピーターセングラフの染色数が正確に 3 であることを決定づけるのは、下限としての奇サイクルと、上限としてのブルックスの定理である。

    χ(Petersen)=3>ω=2: the clique bound is not tight\chi(\text{Petersen})=3>\omega=2:\ \text{the clique bound is not tight}
  2. 完全グラフ K4 における χ の境界の比較 5 ステップ

    次は K₄ — 4 個の頂点と、全 6 本の辺が存在する。χ を求め、各界をピーターセングラフでの結果と比較せよ。これは完全グラフ K4の状態である。

    この問題をツールで開く

    1. 図を過信するのではなく辺を数えよ。4 個の頂点のすべてのペアが結ばれており、ペアは 6 つ存在する。

      K4: ∣V∣=4, ∣E∣=(42)=6, every pair adjacentK_4:\ |V|=4,\ |E|=\binom{4}{2}=6,\ \text{every pair adjacent}

    2. すべての頂点が他のすべての頂点と隣接しているため、どの 2 つの頂点も同じ色を共有することはできない。これは 4 という下限を与え、定義以上の議論を必要としない。

      all four vertices are mutually adjacent ⟹ ω=4 ⟹ χ≥4\text{all four vertices are mutually adjacent}\ \Longrightarrow\ \omega=4\ \Longrightarrow\ \chi\ge4

    3. 4 色で十分であることは明白であるため、下限は満たされる。同様の推論により、すべての n について χ(Kₙ) = n が導かれ、これが完全グラフを扱いやすいケースにしている。

      four colours suffice trivially ⟹ χ(Kn)=n\text{four colours suffice trivially}\ \Longrightarrow\ \chi(K_n)=n

    4. 2 つのグラフを並べて比較してみよ。同じ問い、同じ 2 つの界であり、それらの間のギャップこそがこの主題のすべてである。

      here ω=χ=4: the bound is tight, and Petersen showed it need not be\text{here }\omega=\chi=4:\ \text{the bound is tight, and Petersen showed it need not be}

    5. ここでブルックスの定理がどのような位置づけにあるかに注目されたい。その Δ = 3 という上限は K₄ に対しては誤りとなるため、完全グラフが名指しで例外として除外されているのである。

      Δ+1=4 as well — Brooks’ theorem excludes complete graphs for exactly this reason\Delta+1=4\ \text{as well — Brooks' theorem excludes complete graphs for exactly this reason}

    解答

    4 であり、ここではすべての界が同時にタイトになる。グラフ全体がクリックであるためクリック数は 4 であり、すべての頂点が他の 3 つの頂点と接続しているため Δ + 1 も 4 となり、真の解はその間に挟まれて逃げ場がない。これこそが人々が直感を形成する事例であり、そしてまさにブルックスの定理が除外している事例でもある。ブルックスの定理による Δ という上限は、完全グラフと奇サイクルを除くすべての連結グラフに適用され、これら 2 つの問題は双方の例外が存在する理由となっている。ピーターセングラフと K₄ は両極端を示している。一方はクリック数による下限が 1 だけ外れるケースであり、もう一方はまったく外れようがないケースである。

    χ(K4)=ω(K4)=Δ+1=4\chi(K_4)=\omega(K_4)=\Delta+1=4
参考文献 (2)

· 公表された資料と照合しています。訂正のご指摘を歓迎します。