Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
Graph is Fun
Search
Catupper
August 30, 2013
0
130
Graph is Fun
ぐらふつよい
JOIss2013グラフ理論班かつっぱ氏発表
辺彩色
Catupper
August 30, 2013
Tweet
Share
More Decks by Catupper
See All by Catupper
ants' roots
catupper
1
2.4k
Trianguler
catupper
0
190
sort conference
catupper
2
97
計算量の話
catupper
0
1.1k
About累積和
catupper
0
1.6k
For You
catupper
1
140
Featured
See All Featured
A Modern Web Designer's Workflow
chriscoyier
692
190k
Fantastic passwords and where to find them - at NoRuKo
philnash
50
2.8k
Designing for Performance
lara
604
68k
The Language of Interfaces
destraynor
154
24k
Faster Mobile Websites
deanohume
304
30k
Designing for humans not robots
tammielis
249
25k
10 Git Anti Patterns You Should be Aware of
lemiorhan
654
59k
Art, The Web, and Tiny UX
lynnandtonic
296
20k
Intergalactic Javascript Robots from Outer Space
tanoku
268
27k
How GitHub (no longer) Works
holman
311
140k
Refactoring Trust on Your Teams (GOTO; Chicago 2020)
rmw
31
2.7k
Rails Girls Zürich Keynote
gr2m
93
13k
Transcript
グラフ理論-catupper 辺彩色
問題です • プロジェクトがN個、生徒がM人います • 各生徒はいくつかのプロジェクトに参加し ています • プロジェクトは、それに参加している生徒 全員の課題が終われば完了します –
進捗はダメダメです
問題です • プロジェクトがN個、生徒がM人います • 各生徒はいくつかのプロジェクトに参加し ています • プロジェクトは、それに参加している生徒 全員の課題が終われば完了します –
進捗はダメダメです
問題です • 生徒たちはアイドルに励まされるとやる気を出して、一 つだけ課題を終了できます。 – 課題は励ましたアイドルがプロジェクトに提出します • 飽きぽいので二度目はやる気が出ません • プロジェクトリーダーも飽きっぽいので同じアイドルか
ら1個しか課題を受け取りません。 • アイドルは何人必要でしょうか。
迫真 とけましたか?
本題 辺彩色
本題
辺彩色とは • 与えられたグラフの辺に色を付ける • ただし、隣接する辺は同じ色で塗ってはいけない – 隣接する:=頂点を共有する • 使う色種を小さくしたい •
右の例は5-辺彩色 • 実は4色でも可能
強力な定理 • Vizingの定理 – 任意のグラフの辺彩色数は グラフの最大次数Dに一致するか、 D+1に一致する • つよい!
ちなみに • 頂点彩色は上界として最大次数が与えられるが、下界は どんなときでも2だったりする – 二部グラフは好きなだけ次数をあげることができる • それにくらべれば値が二通りに絞れる辺彩色の定理は強 い –
さいきょう
例 D = 4 4-辺彩色
さらにおもしろい定理 • Konigの定理 – 任意の二部グラフの辺彩色数はその最大 次数と一致する
さらにおもしろい定理 • Konigの定理 – 任意の二部グラフの辺彩色数はその最大 次数と一致する • 一致する • 一致する
• 一致する • 一致する
帰納法で 証明しよう!
証明 • グラフの辺の数が n 未満の時に定理が成立してると仮定 • 辺の数が n のグラフ G
についてひとつの辺 e を選ぶ – 最大次数はDとする • G – eはD色で辺彩色可能 • とりあえずG - eをD色でぬりわける
This is G(二部グラフ) • 辺eは頂点XとYを結ぶ • 最大次数D = 3
適当に塗ってみる
eのまわりに注目 • XもYもD-1色以下で彩色使われてない色がある • 共通の使われてない色があ ったら、eはその色 • 無いと仮定して証明を続ける • Xにない色を黄色
• Yにない色を青色 • とする
Xからてくてく歩く • Xには必ず青色があるので, Xからはじまる青黄青黄...と なる最長のパスを探す
Xからてくてく歩く • Xには必ず青色があるので, Xからはじまる青黄青黄...と なる最長のパスを探す
このパスは閉路でない • Xには黄色がつながっていないので閉路にはならない
このパスはYで終わらない • 二部グラフなのでYに入る辺は黄色でないといけない – Yに黄色はつながっていないので矛盾
パスの青と黄色を入れ替えても良い • パスが通る頂点に接続している青と黄色はこのパスに使 われている(再長性より). よって入れ替えても問題ない
いれかえるとうれしい! • XとYのつながってない色が異なる
いれかえるとうれしい! • XとYのつながってない色が等しい!
青い線がひけるんだなぁ • 元のグラフ
青い線がひけるんだなぁ • いれかえたあと
完成! • G-eがD辺彩色可能なら Gも可能!
Q.E.D. • 辺の数がDのときとかは自明にD辺彩色可能なので • 帰納法による題意は示された! • Q.E.D. !
ところで 冒頭の問題はどう解くのか?
進捗はダメダメです • プロジェクトリーダーと生徒を頂点として二部グラフを 作る • 辺をアイドルとする • 問題は二部グラフにおける辺彩色となる • さっきの定理を証明済みとすると
– 最大次数をもとめるだけ
進捗はダメダメです • プロジェクトリーダーと生徒を頂点として二部グラフを 作る • 辺をアイドルとする • 問題は二部グラフにおける辺彩色となる • さっきの定理を証明済みとすると
– 最大次数をもとめるだけ • ✌('ω' ) ✌ 三✌('ω')✌三( 'ω') ✌ ✌
わかりやすい例 プロジェクトリーダー 生徒ども
辺がブラック....(察し 課題たち
正義のアイドルたち
正義のアイドルたち
ご清聴ありがとうございました
グラフ楽しい グラフ楽しい!! ✌('ω'✌ )三✌('ω')✌三( ✌'ω')✌