Document

Mathematics that the professor loved
徳山 豪
東北大学
Coloring that professors love
博士たちの愛する彩色
彩色問題
• 有限集合Vを種別(色塗り)する。
–
–
–
–
色塗りはVに対して与えられた離散構造に依存
グラフの彩色
平面の三角形分割の頂点彩色 (今日のテーマ)
地図の領域の彩色: 四色問題
• グラフ G=(V, E) 頂点と辺からなる離散構造
– 様々な情報構造を記述できる
• 計算構造、VLSI、WEB、ネットワーク、データベース
• グラフの頂点彩色: 頂点に色を与える
–
–
通常の条件: 隣り合った頂点には違う色を塗る
今日は、ちょっと変わった彩色問題を利用します。
トピック 1: 組合せ論の美の典型
• Brouwerの不動点定理(1912)
– 「中間値の定理」 の一般化
– 幾何、解析、プログラム基礎理論、情報理論な
どの基本定理
• D次元の球BからBへの連続写像fは必ず不
動点(f(x)=xである点x)を持つ。
• オリジナルの証明:高等な解析と幾何を利用
• 天才Sperner(23歳)の初等的証明(1928)
– 二次元の場合を講義で紹介
不動点定理(1次元)
• [0,1]上で定義され、[0,1]に値を取る任意の連
続関数 y = f(x) は、y=xと必ず交わる
不動点定理とトポロジー
• 単位円周上で定義され、単位円周に値を取
る連続関数で不動点を持たないものがある
しかし、円の内部まで考えて、円盤から円盤への写像は、必ず不動点を持つ。
Spernerの彩色定理
3
三角形分割の頂点を3
色に塗る。 (1,2,3)
の数字をつける。
ただし、辺上は対頂点
の色はつけない
すみません、
先週のプリント
で条件が抜け
ていました
1
2
Spernerの彩色定理
3
3色を頂点に持つ三角形
が無いように出来るか?
3
1
出来ない!
1
2
3
1
1
1
(証明は黒板で)
1
3
1
3
1
2
1
3
2
2
2
1
2
Brouwerの定理(二次元)の証明
•
•
•
•
•
BからBへの連続写像 F
三角形TからTへの連続写像Fとしてよい。
T: 3次元空間で(1,0,0), (0,1,0), (0,0,1)を頂点とする正三角形
Tの三角形分割を考える
p=(x,y,z), f(p)=(x’,y’,z’)とすると: x’>x なら1、x’≦x, y’>yなら2、
x’≦x, y’≦y,z’>z なら3を塗る
– ぬれない点があれば、不動点である (なぜか?)
• どこかに1,2,3を頂点とする三色三角形が出来る
• 細分で三角形分割を無限に小さくする。
• 三色三角形の中心点の列は集積点を持つ。
–
Weierstrauss の定理: 有界な無限点列には集積点が存在する。 (注
意:点列が収束するとは言っていません)
• このとき、vが不動点になる。
三角形の細分
3
1
2
課題
• Spernerの定理をd次元に拡張し、証明せよ
• Brouwerの不動点定理をd次元で証明せよ
トピック2:美術館問題
(V. Klee, 1973)
• 美術館に警備員を数人配置する。
• 警備員は椅子に座って、動かない
• 各々の警備員は周囲を見回し(距離は問わな
い)、不審者がいれば警報を出す
• 警備員全員から影になる場所があると、まずい
• 美術館が穴のないN角形であるとき、何人の警
備員を雇えば良いか?
– なぜグラフや彩色と関係するのだろうか???
一人の警備員で済む美術館
• 凸N角形なら一人でOK
• 一人でOKなN角形: 星型N角形
沢山の警備員が必要な美術館
n/3 (端数切捨て)の警備員が必要
1
2
M
明らかな事実: どんな多角形もN人警備員がいればOK
(全ての頂点に配備する)
美術館定理(V. Chvatal 1975)
どんな(穴のない)N角形でもN/3人以下の警
備員で完全に警備できる。
証明の道具:
•N角形はN-2個の三角形に三角形分割できる
•N角形の三角形分割をグラフと思うと、これは3つ
の色に彩色し、全ての3角形が3つの色の頂点を持
つように出来る。
•どれかの色はN/3個以下の頂点に塗られている。
三角形分割と彩色
三角形分割と彩色
三角形分割と彩色
赤: 7点
青: 10点
黄: 8点
トピック3:リスト彩色(Dinitzの問題)
• N2個の小正方形からなる、正方格子を考える。
C(i,j)というN個の色からなる色リストから一つ
色を選んで、(i,j)位置の正方形に塗る。この
とき、同じ色が同列または同行に塗られない
ような配色を「適合配色」と呼ぶ。
• 問題: 必ず適合配色が存在するか?
– 注意:全てのC(i,j)が同一なら簡単:
• 最初の行を適当に塗って、後は循環させる
– (ラテン方陣という)
1 2 3
3 1 2
2 3 1
グラフのリスト彩色
• グラフとの関係
1 2 3
3 1 2
2 3 1
隣接頂点に
同色を塗ら
ない
リスト彩色の難しさ
赤
青
青
黄
赤
青
青
黄
赤
黄
青
黄
赤
黄
青
黄
赤
青
青
黄
赤
黄
青
黄