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