見出し画像

グラフ理論について(3)

みなさん、こんにちは。

今回はオイラーの多面体定理について紹介していきたいと思います。

オイラーの多面体定理は高校1年生の教科書で出てくる定理です。
しかし、大学入試ではほとんど出題されることがないため、影が薄い定理であると私は感じています。

ということで、今回はこのオイラーの多面体定理を主役に記事を書いていこうと思います。

【1】オイラーの多面体定理とは?

まずは、オイラーの多面体定理について紹介します。

V、E、F をそれぞれ凸多面体の頂点、辺、面とするとき、
V-E+F=2という式が成り立ちます。

V、E、F は頂点(vertex)、辺(edge)、面(face)の頭文字からとっています。

では、この式がなぜ成り立つのかについて証明していきたいと思います。

【2】オイラーの多面体定理の証明

※今回は単純グラフについて考えます。
 なぜなら、凸多面体において、ループや多重辺は存在しないからです。

グラフの「ループ」や「多重辺」などの用語については上の記事でまとめているので、そちらを参考にしてみて下さい。

空間を考える前に、まずは、平面について考えてみましょう。

平面のグラフについて、このような定理が成り立ちます。

V、E、F をそれぞれ平面のグラフの頂点、辺、面とするとき、
V-E+F=1という式が成り立ちます。

オイラーの多面体定理の右辺である「=2」の部分が、「=1」というように変わっていますが、それ以外は一緒ですね。

①木について

木とは閉路をもたない連結なグラフのことをいいます。下のようなグラフが木とよばれるグラフです。

木には、面が存在しないので、頂点と辺を数えてみましょう。
左のグラフは頂点の数が4、辺の数が3であるので、4-3=1
真ん中のグラフは頂点の数が7、辺の数が6であるので、7-6=1
右のグラフは頂点の数6、辺の数が5であるので、6-5=1
よって、V-E+F=1 という式が成り立つことが分かります。

〈証明〉
●(頂点)と ー(辺)をそれぞれ1個ずつ取り除く。
すると、●(頂点)が1つ余るので、V-E+F=1が成り立つ。□

②閉路のある平面上のグラフ

今度は閉路のあるグラフについて考えてみましょう。
閉路があるとき、頂点と辺のほかに面も数えます。

頂点の数が5、辺の数が7、面の数が3であるので、5-7+3=1
よって、閉路がある場合も V-E+F=1 が成り立つことが分かります。

〈証明〉
まず、閉路がなくなるように ー(辺)を取り除く。
すると、面の数が1減り、辺の数も1減る。
閉路がなくなると、木のグラフになるため、あとは①と同様の作業を行う。
よって、V-E+F=1が成り立つ。                 □

③空間のグラフ

空間のグラフでは、V-E+F=2 が成り立ちます。
では、この式がなぜ成り立つのか考えてみましょう。

まずは、上の図で示されている立方体(正六面体)について考えてみます。
空間図形で考えるのは大変であるので、平面で考えてみます。
青で示された面を取り除き、広げて上から下に押しつぶします。
すると、右のようなグラフができます。

頂点の数は8、辺の数は12、面の数は5より、8ー12+5=1となる。
また、取り除いた1つの面をたすと、V-E+F=2 が成り立ちます。

正八面体のときも考えてみましょう。
立方体(正六面体)のときと同様に考えます。
赤で示した面を取り除き、広げて上から押しつぶします。
すると、右のようなグラフができます。

頂点の数は6、辺の数は12、面の数は7より、6-12+7=1となる。
また、取り除いた1つの面をたすと、V-E+F=2 が成り立ちます。

〈証明〉
まず、1つの面を選び、取り除く。
次にその面を広げて押しつぶし、平面上のグラフを作る。
②より、平面上のグラフでは V-E+F=1 が成り立つ。
はじめに、1つの面を取り除いているので、1つの面をたすと、
V-E+F=2 が成り立つ。

【3】正多面体はなぜ5種類しかないのか

①正多面体の定義について

まず、正多面体の定義について確認しましょう。

凸多面体で、
(ⅰ)すべての面が合同な正多角形
(ⅱ)各頂点に集まる辺の数が一定
となるものを正多面体(プラトンの多面体)という。

上の5つ図形が正多面体になります。
左から、正四面体、正六面体、正八面体、正十二面体、正二十面体です。
他にも色々ありそうですが、この5種類しかありません。

②正多面体に関する定理とその証明

正多面体は正四面体、正六面体、正八面体、正十二面体、正二十面体
の5種類しか存在しない。

では、上の定理を証明していきましょう。

〈証明〉
多面体の頂点の数を V,辺の数を E,面の数を F とする。
立体の面が正 n角形,1つの頂点に集まる辺が k 本であるとする。( n , k ≧ 3 )

そのとき、それぞれの頂点にk本の辺が集まり、一つの辺は二つの頂点に集まるから kV=2E ・・・① 
それぞれの面には辺がn本あり、一つの辺は二つの面に含まれるから 
Fn=2E ・・・② が成り立つ。
また、オイラーの多面体定理より、V-E+F=2 ・・・③ 

①、②、③より、2E/k−E+2E/n= 2  
            2/k+2/n=2/E+1>1
                (k−2)(n−2) < 4

これを満たす組  (n , k) は (n , k )=( 3 , 3 ),( 3 , 4 ),( 3 , 5 ),( 4 , 3 ),( 5 , 3 )

したがって、正多面体は5種類しか存在しない。
そして、それらの組は正四面体、正六面体、正八面体、正十二面体、
正二十面体と対応している。                   □

【4】最後に

今回は、オイラーの多面体定理と正多面体が5種類しか存在しないことについて紹介しました。

次回は、パーティー問題について紹介していきたいと思います。

最後まで読んでいただき、ありがとうございました。


この記事が気に入ったらサポートをしてみませんか?