読者です 読者をやめる 読者になる 読者になる

「オイラーの公式」島に例えた証明のしかた

オイラーの公式とは

任意の連結な平面グラフに対して領域の個数(f) + 位数(v) = 辺の本数(e) + 2,
             f + v = e + 2

これはオイラーの公式です。「オイラーの公式」で検索すると複素数の公式がでてきますが、グラフについての公式も作ってるんですね。領域の個数も位数も辺の本数も何のことかわからないと思うので図で説明したいと思います。

f:id:carrot_boy:20170217164252p:plain

この絵を島だと思ってください。水色の部分は海です。家みたいなものは見張り台だと思ってください。見張り台と見張り台をつなぐ線を島の堤防と思ってください。堤防は公式で言うところの辺です。領域は堤防で区切られたところを一つの領域とします。この絵の場合、海も一つの領域としますので、4個あります。堤防の数は12個あります。公式で言う位数は見張り台のことです。見張り台の個数は10個です。公式に当てはめてみると、

領域の個数(4) + 位数(10)  = 辺の本数(12) + 2

となりますので、成り立っていますよね。オイラーさんはどのパターンの島でもこの公式は成り立ちますよ、と言っています。ただし、「連結な平面グラフ」と言っています。これは、一つの島の話で、島が何個かある北海道の話ではないよ、という意味です。

上の島の絵をもっと簡単にします。

f:id:carrot_boy:20170217164323p:plain

数学で、こういう図をグラフと言います。

(証明)どうやって敵から島を守るのか

この島には海賊がよく襲ってきます。島の住人は海賊への対抗手段として、海賊が上陸している領域の海に面している堤防を破壊して、海賊に海水をかけます。この島は堤防以外は全て海面より低いということにします。海賊が撤退すると、壊した堤防を作り直します。島の住人はこのような生活を送っています。海賊が水浸しになっても懲りずに襲ってくるなら、次々と海に面している堤防を破壊して島を水浸しにしていきます。島を全て水浸しにすると、このような状態になります。

f:id:carrot_boy:20170217164233p:plain

見張り台の個数をv、堤防の個数をe、領域の個数をfとすると、破壊した堤防の個数は、海以外の島の中の領域の個数なので f - 1個です。上に示したグラフは、閉路がありません。閉路があれば、島全体が水浸しになりません。また、このグラフは連結グラフです。いつも閉路の一辺を破壊しています。閉路から一辺を取っても、グラフが分裂することはありません。残されたグラフ(島の状態)は数学の言葉で「木」になっています。

閉路を持たない連結なグラフを木という

木の性質には、位数 v(青丸の数)の木は v-1本の辺(黒棒の本数)を持つ、というものがあります。これは証明されている事実です。なので、

辺の総数 e = (v - 1) + (f - 1) = v + f - 2 なので、 e + 2 = v + f

になります。

 感想

この内容は、ラスロウ・ロバースさんの本「入門 組み合わせ論」に載っています。この本はハンガリーの高校生の教科書で使われてる内容だそうです。ちょっとした、ストーリーを作って、興味を持たせる工夫がされていて面白いと思いました。