グラフ理論 #9
第9回講義 6月18日--- 双対グラフ、グラフの点彩色 --情報科学研究科 井上純一
http://chaosweb.complex.eng.hokudai.ac.jp/~j_inoue/

演習問題8 の解答例
考える平面グラフの点数、次数と辺数の間には次の関係式が成り立つ

2m∑ n = n, ∑ kn =握手補題
k =3kkk =3

三角形が最小の面辺は必ず面を2分する

3 f ≤ 2m

オイラーの公式より

3n − m ≤ 6

既に得られた関係式を代入して

3n3 + 2n4 + n5 ≥ 12 + n7 + 2n8 + 3n9 + ⋅⋅⋅幾何学的双対グラフ
幾何学的双対グラフの作り方(1)グラフGの各面 f の内側の点 v* を選ぶ ⇒ 双対グラフG *の点となる(2)グラフGの各辺 e に対応させて、e に交差する線 e* を描いて、eに接する2つの面f の点 v* を結ぶようにする ⇒ 双対グラフG *の辺となる破線と白丸からなるグラフが実線と黒丸からなるグラフの幾何学的双対グラフになっている

幾何学的双対グラフの例
完全グラフK 4の幾何学的双対グラフは完全グラフK 4である

同形なグラフとして書き直すと

補題15・1とその証明
平面グラフGには n 個の点、m 本の点、f 個の面がある。
幾何学的双対グラフG *には n* 個の点、m*本の辺、f *個の面があるならば
n* = f , m* = m, f * = nが成り立つ

補題15.1（証明）

双対グラフの作り方から、n* = f , m* = m は明らか。
オイラーの公式より
n* − m* + f * = 2、f * = 2 − n* + m* = 2 − f + m = n
従って、f * = n定理15・2
グラフGが連結平面ならば、G **はグラフGと同形である
（例）

G≅G

**同形写像が存在する
ことは講義ノート参照

定理15・3
平面グラフGの幾何学的双対をG *とする。グラフGの各辺のある集合がグラフGにおいて閉路であるための必要十分条件は、それに対応する双対グラフG *の辺集合が、グラフG *においてカットセットになっていることである

閉路C{v*a, v*b, v*c, v*d , v*e, v* f }はG *においてカットセットになっている
V*からCの各辺を横切る辺を描く

系15・４グラフGのある辺集合がGのカットセットであるための必要十分条件は、対応する幾何学的双対グラフG *の辺集合がG *の閉路となることである
Gのカットセット:{17, 28,39, 410,511, 612}

対応する幾何学的双対グラフG *の辺集合{ fa, ab, bc, cd , de, ef }G*においては閉路となっている（証明のアウトライン)

定理15・3をG→G*、G*→G**として読みかえると、定理15・2からG**とGは同形であるから題意が言える。

例題8.8の(1)車輪の幾何学的双対は車輪例題8.8の(2)非連結化グラフで幾何学的双対を作る

両者は同型でない
できあがる
双対グラフ

例題8.8の(3)
Gの全域木

同型
G* の全域木

補グラフ

グラフの彩色 : 点彩色
k-彩色可能 :k個の色の一つをGの各点に割り当て、隣接するどの2つの点も異色にできること

k-彩色的 :
グラフGがk彩色可能であるが、(k-1)彩色不可能であるとき⇒ グラフGの彩色数はkである

χ (G ) = kδ「彩色数はkである」、というのをこのように表記する

いくつかの代表的グラフに対する例：

χ ( K n ) = n, χ (N n ) = 1, χ ( K r , s ) = 2

定理17・1
単純グラフGの最大次数がΔならば、グラフGは(Δ + 1)彩色可能である（証明）
点数に関する帰納法で示す。
任意の点vとその接続辺を除去してできるn − 1個の点、最大次数Δのグラフは(Δ + 1)彩色可能であると仮定する
vを元に戻し、vに隣接するΔ個以下の点と異なる色でvを彩色すれば、n個の点からなるグラフGの(Δ + 1)彩色が得られる
最大次数の点定理17・3全ての単純平面グラフは6彩色可能である（証明)「n-1個の点をもつ全ての単純平面グラフは6彩色可能である」と仮定
定理13・6より、「全ての単純平面グラフには次数5以下の点がある」
点ｖを除去すると、n-1個の点からなるグラフができあがるので、仮定より、これは6彩色可能。
点ｖを元に戻し、ｖに接続する5個以下の点以外の色でｖを彩色すれば、n点からなるグラフの6彩色が得られる

ｖ

定理17・4全ての単純平面グラフは5彩色可能である（証明)「n-1個以下の点をもつ全ての単純平面グラフは5彩色可能である」と仮定する
定理13・6より、Gには次数5以下の点がある

仮定より、5彩色可能2本の辺vv1、vv3を縮約する
点vに当てられた色でv1、v3を彩色し、点vを元々割り当てられた色以外で彩色しなおせばGの5彩色が完成する
点v1,v3は同色だから、v1-v5の中にはまだ使われていない色が存在する

例題9.1 (点彩色の応用例)
表の関係をグラフ化

講義 c, e は α講時に開講
講義 a, f は β講時に開講
講義 d, g は γ講時に開講
講義 b だけは δ講時に開講

a b c d e f g
a - * * * - - *b * - * * * - *c * * - * - * d * * * - - * e - * - - - - f - - * * - - *g * * - - - * -＊は同じ時間帯にあってはならない講義

例題9.2の1
ここで考えるグラフ

GaGaG*bbccedde

グラフGとG**は同型同型写像の存在については講義ノートを参照

G **
123

定理15.245

例題9.2の１の(1)G に含まれる任意の点 v についてδ ≤ deg(v) と仮定するとnδ ≤ ∑ deg(v) = 2m
ぎりぎり次数δの点が含まれると仮定する v∈V ( G )G には三角形はないので
4 ≤ deg( F ) ∴ 4 f ≤握手補題より∑ deg( F ) = 2m

F∈F ( G )オイラーの公式 : f = 2 − n + m よりf を消去してm ≤ 2n − 4∴ nδ ≤ 2m ≤ 2(2n − 4)つまり、δ ≤ 4−8nnは8以上なので（講義ノート参照）題意が成立する。

例題9.2の１の(2)
G
v2

v1

v3

v2
αv

v1

点vを元に戻し、α、βと異なる色で塗ればグラフＧの3彩色が完成

3色で彩色可能βα

辺vv3を縮約してできるグラフv3 (v)例題9.3 (プラトン・グラフの彩色）α(a)彩色数4β(d)β立方体(c)

αα

δβ

ββααα

彩色数2

δβ

δα

β

γ

β

α(E)

β

彩色数3γ

αα

δβγ

ββ

正八面体γ

γ

α
γ

彩色数4α

βγ

αγ(b)

正20面体

彩色数4γ

正四面体
δαβγ
α

β

αβαγ

正12面体β例題9.4辺が現れるのは異なるグループに属する点の間のみ同じ色で彩色されたグループ内の点どうしは結ぶことはできない

従って、考えるグラフ G の辺 m はm ≥ χ ( G ) C2 = 12 χ (G )( χ (G ) − 1)が成り立つべき。

これをχ ( G )について解いてχ ( G ) ≤1+ 8 m +12

演習問題9