11月から始めたグラフ理論のゼミが終わりましたー。

グラフ理論は四色定理の証明に関係があるんですが、さすがにそこまで行けませんでした。

でも、一色多いですが、五色定理なるものを学べたので個人的には満足であります。



せっかくグラフ理論を勉強したんだし、忘れないように書き残しておこうかな。

五色定理じゃないけど、テキストのなかに面白い例があったのでそれを紹介します!






※英語のテキストで学んだので、便宜上英語表記のままにしている部分があります。
ここに、Jim Family がいます。子どもたちが喧嘩をしないように2部屋に分けたいのですが、どうすればいいでしょう?
Jim Family の家庭事情:
 Chris fights with Bob, Faye, and Eve.
 Eve fights with Al and Di.
 Al and Bob fight all the time.




簡単なクイズですが、解いてみましょう。



Al, Bob, Chris, Di, Eve, Faye を点で表し、喧嘩をする人同士を線で結んでみます。
Jim Family
(オレンジは最初の条件、青は2番目条件、緑が3番目の条件です。)
(簡略化のため、Jim Family を頭文字で表しました。)

喧嘩しないように2部屋に分けたいので、CとB、F、Eは別の部屋にしないといけません。

そして、AとDを、Cのいる部屋に移動させると・・・?
Jim Family2

We have an answer !
C・A・Dで一部屋、B・F・Eで一部屋入れてあげればよいことが分かりました。





じゃあこれはどうでしょう?

ここに、亀田ファミリーがいます。亀田三兄弟が喧嘩をしないように2部屋に分けたいのですが、どうすればいいでしょう?
亀田ファミリーの家庭事情:
 興毅, 大毅, and 和毅 fight all the time.
(注:実際のところは知りません。あくまで例えです。)



これを先ほどと同様な図を描くとこうなります。
亀田三兄弟
喧嘩しないように2部屋に分けたいのですが、どうも無理そうですね。大毅と和毅を2部屋に分けて、興毅の部屋を決めたいのですが、どっちに入れても喧嘩が勃発してしまいます。



どうやら、Jim Familyは2部屋に分けられますが、亀田三兄弟は2部屋に分けられません。

この2つの家族の違いは何でしょう?





ここでグラフ理論の登場じゃ!

グラフ理論には次のような定理があります:
定理
グラフ$G$が2色に塗り分けられる
⇔$G$が odd cycle をもたない。
・「グラフ」とは簡単に言うと、頂点とそれを結ぶ線の集まりのこと。まさに、さっきまで書いてきた図のこと!
・「odd cycle」というのは「$2n+1$角形のグラフ」のこと。
・「2部屋に分ける」が「2色に塗り分ける」という言葉に変わっています。


これはある意味、二色定理と言っていいかもしれませんね。

(数学に自信のある人は証明に挑戦してみてちょ。)





さて、この定理によると、$2n+1$角形のグラフをもってしまうと2色に塗り分けられないことが分かります。

亀田ファミリーには明らかに三角形があります。


Jim Family はどうでしょう:
Jim Family
$2n+1$角形のグラフはどうも見当たらないですね。

C-E-A-Bで cycle ができていますが、四角形なので問題ありません。



家族の部屋割りに応用できるとは、なかなか面白いじゃないか。グラフ理論。



気が向いたら五色定理の証明を紹介します。

気が向いたらね。

thank Q for your rEaDing.φ(・▽・ )