ToDo:
http://twitter.com/alohakun/status/5506693038
これで思い出して前に啓蒙書を貸してもらって読んだけど、証明をさっぱり忘れつつあるので記憶を再構成しておこうと思う。うぃっきぺたんを参考にしつつ俺メモ…
http://en.wikipedia.org/wiki/Four_color_theorem
まず一つの点から4本以上線がのびるような頂点があるグラフは考えなくてもいい。
×
があったら
v | ^
に変換しちゃえば3本のびるグラフに還元できるから。
2本しかのびてない頂点はつまり、単純に領域数増やしに関わってのは無視できて、孤立した円みたいなヤツも自明に関係なくて、全体を囲むやつとかも外っかわの色のせいで4色じゃ塗れなくなっているとすると、中もどうせ4色で塗れませんよね〜ということで忘れていい。でまぁこのケース忘れることから、隣国が1つしか無い国っていうのもいないとしていい。
次はオイラーの多面体公式
http://ja.wikipedia.org/wiki/%E5%A4%9A%E9%9D%A2%E4%BD%93
頂点の数(V) - 辺の数(E) + 面の数(F) = 2
を使う。なんかしらんけど色をぬる領域が頂点として、隣国との国境が辺、でまぁ地図上の頂点が面として考えている。ややこしいな…
3本線が生えてる頂点しか無いことから、 2E = 3F 。 6V - 6E + 6F = 12 につっこむと、
6V - 2E = 12
頂点から出てる線の数を i とした時に、そういう頂点の数を vi とすると、
6Σvi - Σi*vi = Σ(6-i)*vi = 12
ということは i<6 のものが最低一個無いと左辺が正にならないので、最低一つは隣国の数が5以下の国があるわけだ。そこを攻める。
攻める前に、背理法の準備。ここに4色で塗れない地図があったとして、その中で最小の国数となる地図 G を考える。つまり G から国を 1 つ取り除いたら4色で塗れるようになってしまうようなもの。
さて G は隣国2つしかない国を持てない。その隣国2つの国を取り除いて隣国同士をくっつけた地図も依然として4色で塗ることは不可能で、 G が最小という仮定を壊す。
G は隣国3つしか無い国も持てない。これも隣国3つを取り除いて頂点にしちゃった地図も依然として4色彩色不可能だから。
隣国4つもちょっと賢い理由で無理。隣国4つがそれぞれ全部違う色でかつ自分の色とも違ったとして、赤青黄緑の順でぐるりとまわっているのが隣国で自分が紫とかする。赤の国から出発して、黄→赤→黄→赤→…と交互にたどっていけるパスがあるはず。無いなら黄は赤でいいことになってしまう(はしょりすぎだが)。同じ理由で青と緑を交互にたどるパスもある。さてそれらはどうやって交差してるのでしょうかー無理ー。ということで隣国4つも無理。
5色定理はこの論法で隣国5つのケースも潰せるので、証明できる。ここまではそんなにむつかしくないというか、とても綺麗な論法だったわけだ。
で、5つがむずい。というかその、「隣国5つの国が1つはいるよね〜」という条件だけからではどう考えても矛盾が導けなかったので、「隣国 X の国の回りに隣国 Y の国があるようなパターンか、ほげほげなパターンか、あるいはふがふがなパターンか…のどれかは絶対あるよね〜」とかそんな感じで、パターンをどんどん増やしていって、一個一個潰していく感じでやっていった。でまぁ証明難しげなパターンがあったらそのパターンの中でまたパターン増やして…みたいなことをやって、片っ端からこんぴゅーた様で証明した、っていうような感じだったらしい。
でまぁそいうパターンが証明時で2000近くとかあったんだから、泥臭いことこの上ないという。
最後の部分なんかわかりやすいパターンの例とか本に載ってた気がする。今度立ち読みして再構成しよう…
(10:09)
TODO
(16:38)
をやろうとしたけどうまくいかんな…
とりあえず background.html にフラッシュ置いたら SEGV した :( まぁ置けないのはいいのかもしれんが SEGV はどうなんだと思ったので 報告するか今度眺めておこうと思う。
次に content script 側でページにフラッシュを つっこむ実装にしてみようとやってみた。 でもどうもうまくいかない。 なんでだろ。
(16:42)
おもしろかった。
BulletSML を聞いていて、 何か jsdmkun 作ってる時にコンパイルするアプローチだと アレが難しいよなーと思っていた、アレは何だっただろう… とひたすら思い出していたけど思い出せなかった。 その後一瞬で思い出したんだが単に継続だ。 BulletSML では普通に継続使ってるから問題ないのであった。
(17:20)
んで Shibuya.lisp 終わってから行ったら遅れてた。
というかそもそも今思い出したけど Shibuya.lisp 自体存在をきっちり忘れていて、 というか登録した記憶がきっちり無くて、 masa_edw さんの twitter を見て 「あー今日 Shibuya.lisp かー俺も行きたかったなぁ」 と思ってサイト見たら何か登録されていて 焦って飛んでいったとかいうそんなこんな。
で chrome の方はまぁなんかみんなよく知ってるなぁとかそんなこんな。 extension はやっぱこうまだ API 全然足りないよなぁ。
(17:29)
はまぁ悪くはなかったんだけど、 コードが無闇に長いしもう毎回クッキー読み書きする実装でいいんじゃね? と当たり前のことを思ったのでそいう実装を作ってみた。
http://github.com/shinh/w3m/commit/abcedbb2d7222f97157221cf52b00b3b600c6431
これでしばらく使ってみて良さげなら w3mcooksrv はもう捨てよう。
(20:03)
なんだ JS だけでできるんじゃないか… Linux でもすごくよく動いてるので、 もう chrome linux の omnibox とか忘れていい。
TODO がちまちまと消えていってうれしい
(22:25)
| 前 | 2009年 11月 |
次 | ||||
| 日 | 月 | 火 | 水 | 木 | 金 | 土 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 15 | 16 | 17 | 18 | 19 | 20 | 21 |
| 22 | 23 | 24 | 25 | 26 | 27 | 28 |
| 29 | 30 | |||||
全てリンクフリーです。 コード片は自由に使用していただいて構いません。 その他のものはGPL扱いであればあらゆる使用に関して文句は言いません。 なにかあれば下記メールアドレスへ。
