第8回 - Donald Home Page

4.2 点彩色と4色定理
グラフ彩色に関する二つの問題
H27 グラフ理論
点彩色
辺彩色
隣接している点同士を
別々の色で塗り分ける．
接続している辺同士を
別々の色で塗り分ける．
ー第8回ー彩色問題
1
点彩色に関する用語の定義
2
点彩色の応用(化学薬品の保管問題)
グラフ G が k 種類の色で塗り分けられるとき，
G は k 彩色可能であるという．
G が k 彩色可能でかつ (k-1) 彩色可能でないとき，
G は k 染色的であるといい，k を染色数 (χ(G)) と呼ぶ．



[例]
2色で彩色可能であるが
1色では不可能
(χ(G) = 2 )
3色で彩色可能であるが
2色では不可能
( χ(G) =3 )
3
n 種類の化学薬品(例えば n=5)を安全に保管したい
薬品によっては化学反応を起こすため同じ場所に
保管できない(酸性とアルカリ性の薬品など)
これらを安全に保管するには何カ所の保管場所が
必要か？
4
1
薬品の対応関係
1
1
2
3
4
5
2 3
×
×
×
× ×
× × ×
×
[グラフ表現]
同じ場所に保管できない
ものに辺が定義される
4 5
× ×
× ×
×
×
×
染色数の基本定理
(1)位数 p のグラフ G に対してχ(G) ≦p.
証明：色の数は頂点数以下
2
1
3
5
4
すべての頂点を異なる色で着色すれば
かならず塗り分けることができる。
すなわち、χ(G) ≤ p
組み合わせ(x,y)が× ⇔ x,yが隣接(辺がある)
⇔ x,y を別々の色に塗る
右のグラフの彩色数を求めれば
必要な保管場所数がわかる．
図のように彩色数は4なので4つの保管場所が最低必要．
5
染色数の基本定理
(2) H を G の部分グラフとすると，χ(H) ≦χ(G).
6
染色数の基本定理
(3) χ(Kp)=p.
証明：Hの頂点はGに含まれるから
証明：任意の二点に辺があるから
ここを赤で塗ると
隣り合う頂点は別の色
H は G の部分グラフであるので
G の彩色が H の彩色でもある
H
K5
任意の頂点は他のすべての
頂点と隣接する
G の彩色(染色数3)
7
K5
K5
それまで使った色は
二度と使えない
8
2
染色数の基本定理
(4) Kn が G の部分グラフのとき，χ(G) ≧ n.
染色数の基本定理
(5) G1,…,Gk を G の連結成分とすると，
χ(G)=max{χ(G1),…,χ(Gk)}.
証明：上の(2)と(3)より
証明：(2)より
G1
G2
χ(G) =
max{χ(G1),χ(G2)}= 3
二つの連結成分からなる
グラフ G
9
定理4.15
(1) χ(G)=1 ⇔ G=Np.
10
定理4.15 つづき
(2) χ(G)=2 ⇔ G は2部グラフであり，G≠ Np.
証明： χ(G)=1 ならば G は辺を持たないから G=Np ．
逆もあきらか．
証明：(⇐)G が Np でない2部グラフのときは χ(G)=2 は
あきらか．(⇒)また G を彩色するのに1色では不足なら
G は Np でない．さらに2彩色されていれば，
同色同士は辺で接続されていないので2部グラフとなる．
辺を持つグラフは2色以上必要
2部グラフ
辺を持たない位数 p のグラフは
空グラフ Np
11
2色で塗り分けることができる
⇕
辺で結ばれていない２つのグループ
に分割できる
⇕
2部グラフ
12
3
染色数と次数の関係
定理4.17 つづき
χ(G)≧3 ⇔ G は奇閉路を含む．
定理4.18: χ(G) ≦Δ(G)+1.
証明： (⇐)奇閉路を彩色するには３色以上必要．
(⇒)逆に，Gが奇閉路を含まないならばGは2部グラフ
になるのでχ(G)=2になり条件に矛盾する．
奇閉路を含まないグラフは，
偶閉路のみを含むか，閉路を含まない木
であり，図のようにどちらも二分グラフ
奇閉路
(3色必要)
1
2
1
2
1
2
1
1
2
このような辺は
存在しない
1
2
次数の最大値+1
証明 [位数 p に関する帰納法]
v を次数 Δ(G) の頂点とすると，G-v は帰納法の仮定により，
Δ(G-v)+1 色で彩色可能である．
Δ(G-v) ≦ Δ(G) なので，G-v は Δ(G)+1 彩色可能．
その色のなかに v の隣接点に現れない色が存在するので，
その色で v を塗れば G は Δ(G)+1 彩色可能．
×
2
v
1
vの隣接点はΔ(G)+1以下で塗られていて
vの次数はΔ(G)以下なので少なくとも１色余る．
13
定理4.25: V(G)={v1,…,vp} とし，
deg v1 ≧ …≧ deg vpとする．このとき，
証明：v1,…,vk からなるGの誘導部分グラフが，
max 1≦ i≦ k {min{i, deg vi +1 }}色あれば
塗り分けられることを示す．(k に関する帰納法)
v1
この定理の意味
v3
v5
v4
頂点を次数の高い順に
v1,v2,...と名前を付ける
v2
χ(G) ≦ max{
min{1,deg v1 +1}, min{2,deg v2 +1},
min{3,deg v3 +1}, min{4,deg v4 +1},
min{5,deg v5 +1}
} = max{1,2,3,4,3} = 4
14
k = 1 のときは1色で塗れるのであきらか．
そこで最初の k 個の点が n 色で塗られており，
n ≦ max 1≦ i≦ k {min{i, deg vi +1 }}と仮定する．(n ≦k)
vk+1 の隣接点でその n 色で塗られていない点が
あれば vk+1 をその色で塗れば色数は増えない．
そうでないとき n+1 色目で vk+1 を塗る．
15
16
4
（証明のつづき）
したがって n+1≦ max 1≦ i≦ k+1 {min{i, deg vi +1 }} ― (1)
を示せばよい．(頂点がひとつ増えると染色数もひとつしか
増えないので)
（証明のつづき）
ここで(2)⇒(1)が成り立つことを示す．
αi= min{i, deg vi +1 }と表すと，(1), (2)式は以下のようになる．
n+1≦ max{α1, α2, ... , αk+1} ― (1)
n +1 ≦ αk+1 ― (2)
常に n≦ k (頂点の数だけ色があれば彩色できる)であるので，
両辺に1を足して n +1≦ k +1 である．
(a) αk+1 ≦∃(αi) であるときは，
n +1≦ αk+1 ≦ αi ≦ max{α1, α2, ... , αk+1}
また，n ≦ deg vk+1であるので，(そうでなければ色が増えない)
両辺に1を足して n+1 ≦ deg vk+1+1.
(b) ∀(αi) < αk+1 であるときは，
n +1≦ αk+1 = max{α1, α2, ... , αk+1}
以上により， n +1 ≦ min{k +1, deg vk+1 +1} ― (2)
となる.
以上によって (2)⇒(1) が成立し，n +1のときも正しい．
17
グラフ彩色を得る比較的よい手法
染色数χ(G)とサイズqに関する定理
定理：
証明： k=χ(G) として，G を k 色で塗り分ける．このとき，異なる
同色集合の頂点間には少なくとも一本の辺がある．そうでない
ならば，それら2つの同色集合を同じ色に塗ることができるから．
したがって，q ≥ k(k-1)/2 となり，これを k=χ(G) について解く．
このような集合をまたぐ辺が
ないならば，2頂点は同色で
塗れるはず
18
同色集合
D.J.A ウェルシェ，M.B.パウェル
入力：グラフ G
出力：G の点彩色
方法：
ステップ１：まだ塗っていない頂点から最大次数
の頂点 v を選ぶ．
ステップ２：これまでに使った色で，v に隣接する
頂点に使われていないものがあったらその色で
v を塗り，そうでないなら新しい色で v を塗る．
ステップ３：まだ塗られていない頂点があるときは
ステップ１へ戻る．
※一般のグラフに対して染色数を計算する良い方法は
知られていない (NP-困難：おそらく不可能)
19
20
5
平面グラフの彩色問題
４色予想：平面グラフは4彩色可能である．
４色予想：平面グラフは4彩色可能である．

アッペルとハーケンによる証明のアイディア
 どのような平面グラフにも必ず含まれるような部分グラフ
の集合を考える (不可避集合と呼ぶ)
 例えば頂点ひとつだけからなる集合は不可避集合
 うまい不可避集合を作れる：その不可避グラフを取り除い
たグラフが4色で塗れるなら，グラフ全体も4色で塗れる．
(不可避集合の可約性)
不可避集合に含まれるグラフ：これを取り除いて
4色で塗れるならば、Gは4色で塗れる
ロシア連邦の塗り分け
G’
G
人工的な地図の塗り分け
21
4色定理の証明は非常に複雑であるが，その基本的アイディアは
より易しい命題の証明に現れている
４色定理：証明の概略

22
定理: 平面グラフは6彩色可能である．
アッペルとハーケンによる証明
 不可避集合のすべてのグラフ(およそ2000種類)がすべて
4色で塗り分けることができることを証明
 5色必要な平面グラフが存在すると仮定し，そのようなグ
ラフで最小のものを G とする．
 G は不可避グラフを含み，それを取り除いたものを G’ と
すると，G’ は4色で彩色できない．(なぜならば，可約性の
対偶も成り立つから)
 しかしながら，G は4色で彩色できない最小のグラフであ
ることに反する(それより小さい G’ が存在する)
 よって仮定は誤りである
23
証明：帰納法で示す．
n-1点以下で成り立つとするとき，n 点の平面グラフは
次数が5以下の点があるので，そのなかの1点を v とし，
v を取り除いたグラフを6色以下で塗り分ける．
v に隣接する点は5点以下なので，余った1色で v を塗ると
n 点のグラフ全体を6色で塗り分けられる．
v1
v5
v
v4
v2
v3
24
6
定理4.22: 平面グラフは５彩色可能である．
v1 から v5 までがそれぞれ１～５までの色で
塗られているとする．色1と3のみで塗られた
頂点からなる部分グラフ H13 を考える．
証明：グラフ G の位数に関する帰納法で示す．
位数が５以下についてはあきらかなので，
位数 p-1 以下について正しいと仮定し，G を位数 p
のグラフとする．G には次数が５以下の点 v がある．
仮定より G-v は５色で塗られている．
v の次数が４以下ならば１色余るのでその色で v を
塗ることができる．そこで，v の次数を５とし，
v に隣接している頂点を時計回りに v1,…,v5 とする．
v5
ケース１：v1 と v3 が H13 の
異なる連結成分に含まれるとき．(上図)
v3 が含まれる方の成分の
１と３を入れ替えることができ，
v1 と v3 は共に色１で塗られるので，
v を３で塗ることができる．(下図)
v4
v3
2
26
v1
v5
H13
1
1
v2
v
v4
v3
3
3
1
3
1
4
1
v1
v5
4
v
v2
v
3 3
2
3
v4
1
4
4
1
2
v2
3
v3
2
4
2
1
3
2
2
3
1
3
1
v4
3
1
1
3
4
v3
3
3
ケース２：v1 と v3 が H13 の同じ連結成分
に含まれるとき．
v1 から v3 への閉路が存在する．(右図)
v2 と v4 はこの閉路によって異なる
領域に分割されるので，前と同様に
色を入れ替えることで１色余り，その色で
v を塗ることができる．(下図)
(証明終)
v4
v4
H13
v2
1
25
1
v
1
1
v3
v2
v
v1
3
v1
v1
v5
v5
3
1
4
4
2
3
1
2
4
3
1
H24
27 3
7

Download Report