第9回 - Donald Home Page

4.3 辺彩色
同色の辺が互いに隣接しないようにグラフの
辺に色を塗ることをグラフの辺彩色という．
H26 グラフ理論
あるグラフの辺彩色が k 以下の色で可能なとき，
そのグラフはk-辺彩色可能であるという．
ー第9回ー辺彩色問題
あるグラフがk-辺彩色可能でかつ (k-1)-辺彩色
不可能であるとき，kを辺染色数χ’(G) と呼ぶ．
1
A～Dの頂点を持つグラフを考え，
ペアを頂点間の辺で表す
辺彩色の応用

2
スケジューリング問題
A
B
D
C
 何人か(A～D)がペアになって打ち合わせする
(異なる組み合わせ)
(A,B), (A,C), (A,D), (B,C), (B,D),(C,D)
 異なるペアが同じ時間帯に打ち合わせできない
 できるだけ短時間に時間割を組むには？
隣接辺を
異なる色で塗る
A
B
D
C
 打ち合わせの種類:
1
2
3
時間の流れ
3
同色辺は接続していないので,その辺が表す打ち合わせ
は同一時間帯に可能．よってこの場合3単位時間で可能．
3 ≤ χ’(G) ≤ 3 ⇒ χ’(G) = 3
4
1
定理5.11: (前半) 完全グラフKpに対して，
pが奇数ならば，χ’(Kp)=Δ(Kp)+1 = p.
定理5.11:(前半) 完全グラフKpに対して，
pが奇数ならば，χ’(Kp) =Δ(Kp)+1 = p.
1
c3
c4
2
5
c1
c5
証明：
まずχ’(Kp)≦Δ(Kp)+1=p を示す．
pが奇数のとき，図のように正p角形の周囲
の辺を色c1～cpで彩色し，それ以外の辺
(vi-1, vi+1)をそれと平行な辺と同色で彩色．
このときχ’(Kp)≦Δ(Kp)+1=p.
c2
3
c1
1
2
この2辺を同色に塗ることができ，
他も同様にすることで，周囲の色だけで
すべての辺を彩色できる．
4
5
3
4
これ以上選べない
証明：
次にχ’(Kp)≧Δ(Kp)+1=pを示す．
{v1,v2,…,vp}から互いに隣接しない辺は
最大で(p-1)/2以下しか選べない．
また，辺数はp(p-1)/2なので，
χ’(Kp)≧Δ(Kp)+1=p. 以上によりχ’(Kp)=p.
{1,2,3,4,5} から辺 (1,2) を選ぶと，それに接続して
いない残りの頂点は {3,4,5} となる．そこからさらに
辺 (3,4) を選ぶと残りは {5} でそれ以上選べない．
このとき同色に彩色できるのは (1,2 )と (3,4) の
2辺のみ．( 5(5-1)/2 = 2 )
5
6
定理5.11: (後半) 完全グラフKpに対して，
pが偶数ならば，χ’(Kp)=Δ(Kp)=p-1.
定理5.12: χ’(Kn,m)=max{n,m}
証明： p が偶数ならば，χ’(Kp)=Δ(Kp)=p-1を示す.
p が偶数のとき，全体を Kp-1 と K1,p-1 に分ける（下図）．
p-1 で Kp-1に p-1 彩色をする．
K1,p-1 の各辺に，それに未
接続の辺の異なる色を彩色
c1
1
でき，Kp全体は p-1．
したがってχ’(Kp)=p-1.
2
証明：一般的に m≧n としてよい．このとき以下のように
辺彩色すれば，隣接辺は異なる色で彩色可能．
m
5
Kp-1
c1
同じ色で彩色できる
3
4
6
K1,p-1
7
赤, 緑, 青, 紫
緑, 青, 紫, 赤
青, 紫, 赤, 緑
n
8
2
定理5.14: (V.G. ビジング)
空でない任意の単純グラフGに対して，
χ’(G) = Δ(G) または Δ(G)+1
定理5.15: G を位数3以上の奇閉路でない連結グラフ
とすると，G の2-辺着色で，次数2以上のすべての点で
2色が共に現れるものが存在する．
χ’(G) ≦ Δ(G)+1 を示せば十分．
そのためにいくつかの準備をする．
図形的に説明すると. . .
定義：グラフの辺に色を付けるとき，なんの制約
もない場合を，辺着色といい，k-色による着色を
k-辺着色という．
奇閉路
辺彩色
辺着色(辺彩色を含む)
9
定理5.15: G を位数3以上の奇閉路でない連結グラフ
とすると，G の2-辺着色で，次数2以上のすべての点で
2色が共に現れるものが存在する．
証明：Gがオイラーグラフの場合： (かつ, Gが偶閉路のとき)
図のように色を閉路に沿って
交互に色を塗れば，各点に
接続する少なくとも2辺は異なる
ように辺彩色できる．
11
奇閉路でないグラフ
(次数2以上の点(黒丸)で
2色が共に現れる)
10
定理5.15: Gを位数3以上の奇閉路でない連結グラフ
とすると，Gの2-辺着色で，次数2以上のすべての点で
2色が共に現れるものが存在する．
証明：Gがオイラーグラフの場合： (Gが偶閉路でないとき)
Gは次数4以上の点vを少なくともひとつは含む．
(奇点がないオイラーグラフだから)
vの次数が4以上 ⇒
v を開始点にして，
vは2回以上回路に現れる．
オイラー回路に
交互に色を塗れ
G のオイラー回路
ば必ずすべての
v
頂点が2色に接する．
v
12
3
定理5.15: G を位数3以上の奇閉路でない連結グラフ
とすると，G の2-辺着色で，次数2以上のすべての点で
2色が共に現れるものが存在する．
証明：G がオイラーグラフでないとき：
(奇点の個数は偶数) より，新たな v’ とすべての
奇点を結んでグラフG’を作る．(G’はオイラーグラフとなる)
v’からのオイラー回路に
2-辺着色し，そこからv’の
辺を取り除いても次数
2以上の点vで2色は残る．
Gのオイラー回路
v’
v
定義：あるグラフにk-辺着色が与えられているとする．
c(v)を点vに現れる色の個数とし,Σc(v)が最大になる
k-辺着色をそのグラフの最適なk-辺着色という．
Σc(v) = 11
Σc(v) = 12
最適でない3-辺着色
最適な3-辺着色
13
定理5.16: {E1, E2, …, Ek}をグラフGの最適なk-辺着色
とする．点uにおいてuに現れない色cnとuに２度以上現
れる色cmがあるとき， cnの辺集合Enとcmの辺集合Emか
ら誘導される部分グラフ< En∪Em>の成分でuを含む
ものは奇閉路である．
E2
E1
u
E5
E4
E3
E7
E6
Gの最適な3-辺着色 {E1,...,E7}
cn = {紫}
cm = {緑}
誘導部分グラフ H=< En∪Em>
={破線の紫と緑からなるグラフ}
=奇閉路
15
14
証明：< En∪Em>の成分でuを含むものを H とする．
H が奇閉路でないと仮定する. （背理法）
定理5.15より， 2色cn, cmによる H の2-辺着色γn，mで，
次数 2 以上の点に両方の色が現れるものが存在する．
Hの辺をこの着色で塗り替えるとGの新しいk-辺着色γ’
が得られるが，
（１）cγ’(u)=cγ(u)+1
（２）cγ’(v)≧c(v) (vはu以外)
したがって，Σcγ’(v) > Σcγ(v)となるが，
これはGが最適なk-辺着色であることに矛盾する．
16
4
定理5.14: (V.G. ビジング)
空でない任意の単純グラフGに対して，χ’(G) ≤ Δ(G)+1．
証明（つづき）
これを繰り返すと，点v1,… とその色c1,… の列は
以下を満たす．
証明（背理法）χ’(G)>Δ(G)+1を仮定する．
Gに最適な(Δ(G)+1)-辺着色γを施すと，
仮定からこれは辺彩色ではないので，
c(u)<deg uとなる点がある．(ある色がuで被っている)
u に現れない色をc0とし，2度以上現れる
色をc1とする．(u,v1)はc1で塗られた辺．
（１）(u, vj)は色 cj を持つ
（２） cj +1 は vj の色でない
(×がついた辺はない)
c3
u
u の次数は有限なので，
vk=vn+1かつck=cn+1を満たす
1≤ k < nが存在する．
v1
v3
c3
u
c1
c2
c1
c4
着色数は同じ
c3
v3
v2
v1
u
1≦ j ≦ k-1
ここをひとつ上の辺の
色と入れ替える
(赤は重複するので色数
は減らない)
c1
v2
c2
c1
v1
c3
c2
H’
×
証明（つづき）
つぎに辺 (u, vj) (k≦ j ≦ n-1) の色を cj+1 に塗り替え，
(u,vn) の辺を ck で塗り替えることにより，γ’から
さらに，最適な(Δ(G)+1)-辺着色であるγ’’が得られる．
ここでも ck は２度以上現れるので，< Ec0 ∪ Eck >の
u を含む成分 H ’’ も奇閉路である．
v3
v3
v4
c1
×
×
18
v3
c3
c3
c4
u
v3
17
証明（つづき）
辺 (u,vj) (1≦ j ≦ k-1) の色を cj+1 に塗り替え，
これによって得られた着色をγ’とすると，
これも最適な(Δ(G)+1)-辺着色である．
このとき，<Ec0∪Eck> の u を含む誘導部分グラフ H ’ は
定理5.16より，奇閉路である．(c0はなく，ckは2色以上)
c3
vk
c3
v2
c1
vn+1
v4
v3
c2
v1にも現れない色c2が存在し，γが最適
c1
であることより，c2はuの接続辺に現れる．
(そうでなければc1のどちらかをc2で塗ること
でより最適な着色を得るが，これは矛盾する)
v3
c3
c4
v4
c3
v3
u
v2
c1
v1
19
c3
c2
v4
v3
v2
v1
c3
k≦ j ≦ n-1
ここを入れ替える
c4
u
前回と同様に
c1
着色数は変化しない
c3
c2
H ’’
v4
v3
v2
v1
20
5
証明（つづき）
H ’は奇閉路なので，vk の H ’ での次数は2であるが，
H ’ の ck が ck+1 に置き換わったので(図ではc3がc4へ)
H ’’ で vk の次数は1となるが，H ’’ が奇閉路であることに
矛盾する．(証明終)
v3
v3
c3
c3
c4
c3
u
c1
c3
c2
c3
v4
v3
v2
v1
H ’を含むグラフ
c4
vk
u
c1
c3
c2
v4
v3
v2
vk
v1
H ’’を含むグラフ
vkで色が置き換わっているので，H’でvkの次数が2ならば，同じvkの次数は
H’’では1となり，vkが閉路の一部であることに矛盾する．
21
6

Download Report