Loading [MathJax]/jax/output/CommonHTML/jax.js

組合せとグラフの理論（塩田）第11回 (1)　点彩色・彩色数の定義
戻る / 次へ

点彩色の定義

　まずは定義から。
Def.1　G をループを持たない無向グラフとする。 G の頂点に色を割り当て、隣接する頂点同士は別の色になるようにすることを「G の点彩色」という。
Ex.2　次のグラフに点彩色を施してみましょう。 ( 今は色を塗りますが、実際に色を塗るのは大変なので、次からは単に色の番号を振って表します。)
　全ての頂点に異なる色を使えば当然点彩色になります。
　もっと少ない色で点彩色してみましょう。 隣接していなければ同じ色を塗ってもよいので
  とか  
でもOKです。

彩色数の定義

　色をたくさん使えば色は塗り易くなります。 しかし 色が多いほどコストは増えます（インクをたくさん買わなければならない、とか）。 そこで、なるべく使う色を少なくしよう、というのが次の定義です。
Def.3　
  1. G が k 色で点彩色できるとき「 G は k-彩色可能である」という。
  2. G が点彩色できる 最少の色数 を「 G の彩色数」と呼び、χ(G) と表す。
彩色数の示し方　χ(G)=k であることを示すには
  1. G を点彩色するには k 色以上必要であることを示し、かつ
  2. G が本当に k 色で点彩色できることを示す。
　1° は、G が k−1 色以下では点彩色できないことを示すことと同じです。

※　必要最小限と言わないといけないので 1° を忘れてはいけません。 こことても大事！！ （毎年口を酸っぱくして教えているのですが ... ）
Ex.4　χ(C5)=3.
  1. 2 色で点彩色しようとすると互い違いに色を使うしかなく、5 つ目の頂点にはどちらの色も使えなくなります。
  2. 次のように塗れば 3 色で点彩色できます。

戻る / 次へ