グラフ理論におけるオイラーの公式とは、証明、多面体定理

どうも、木村(@kimu3_slime)です。

今回は、グラフ理論におけるオイラーの公式を紹介します。

 

オイラーの公式とは

オイラーの公式(Euler’s formula)は、平面グラフの頂点、辺、面の個数に関する恒等式です。

\(G\)を連結な平面グラフ、\(\mathrm{card}(V),\mathrm{card}(E),\mathrm{card}(F)\)をそれぞれ頂点、辺、面の個数とする。次の等式が成り立つ。

\[\mathrm{card}(V)-\mathrm{card}(E)+\mathrm{card}(F)=2\]

(複素解析におけるオイラーの公式\(e^{i\theta}= \cos \theta + i \sin \theta\)とは別物です。)

 

オイラーの公式が正しいかどうか、具体例で確かめてみましょう。

上のグラフでは、\(\mathrm{card}(V)=4\)、\(\mathrm{card}(E)=3\)、\(\mathrm{card}(F)=1\)なので、\(4-3+1=2\)は成り立っています。平面グラフの面とは、グラフによって囲まれる「内側」の部分だけでなく、外側もカウントすることに注意しましょう。

このグラフは、サイクルを持たず、です。木では\(\mathrm{card}(V)=\mathrm{card}(E) +1\)が成り立つことを確かめました。面の数が\(1\)個なので、木に関してはオイラーの公式\(\mathrm{card}(V)-\mathrm{card}(E)+\mathrm{card}(F)=2\)は確かに成り立っています。

他のグラフを考えましょう。

上のグラフでは、\(\mathrm{card}(V)=4\)、\(\mathrm{card}(E)=6\)、\(\mathrm{card}(F)=4\)なので、\(4-6+4=2\)で、オイラーの公式は成り立ちます。

このグラフでも、\(\mathrm{card}(V)=8\)、\(\mathrm{card}(E)=12\)、\(\mathrm{card}(F)=6\)なので、\(8-12+6=2\)でオイラーの公式は成り立ちます。

 

グラフが木であるときには、オイラーの公式は成り立っています。今回知りたいのは、それが木でなくなるとき、サイクルを持つときどうなるか、ということです。

木にひとつ辺を加えて、サイクルができたとします。1個辺が増えて、それによって面が1個増えるので、\(\mathrm{card}(V)-\mathrm{card}(E)+\mathrm{card}(F)=2\)という関係式は保たれ続けますね。つまり、辺の数を1つずつ増やしていく帰納法によって、一般の場合も証明できそうです。

 

オイラーの公式の証明

では、オイラーの公式の証明をしましょう。

グラフ\(G\)の頂点の数\(\mathrm{card}(V)\)を任意とし、辺の数\(n=\mathrm{card}(E)\)に関する数学的帰納法で示します。また、サイクルを持つか持たないかで場合分けします。

\(n=0\)のときは、(空でない)連結なグラフを考えているので、\(\mathrm{card}(V)=1\)です。このとき面は1つです。したがって、\(\mathrm{card}(V)-\mathrm{card}(E)+\mathrm{card}(F)=2\)は成り立ちます。以降では、\(n=k-1\)のときの主張の成立を仮定し、\(n=k\)で成立するかどうかを確かめましょう。

\(G\)がサイクルを持たない、すなわち木のときは\(\mathrm{card}(V)=\mathrm{card}(E) +1\)が成り立つことを以前示しました。木では面の数が1個なので、\(\mathrm{card}(V)-\mathrm{card}(E)+\mathrm{card}(F)=2\)が成り立ちます。

\(G\)がサイクルを持つときを考えます。そのサイクルに含まれる辺のひとつを\(e\)とし、\(G\)から\(e\)を除いたグラフを\(G^{\prime}\)とします。

\(G\)は連結なので、サイクルから1つの辺を除いた\(G^{\prime}\)も連結です。帰納法の仮定より、\(\mathrm{card}(V(G^{\prime}))-\mathrm{card}(E(G^{\prime}))+\mathrm{card}(F(G^{\prime}))=2\)が成り立ちます。

ジョルダンの曲線定理より、\(e\)は\(G\)の2つの面\(f_1,f_2\)の境界を含んでいます。そして、\(e\)は\(G^{\prime}\)の辺ではないので、\(e\)の内部を含むような\(G^{\prime}\)の面\(f_e\)が存在します。このとき、\(f_1,f_2,f_e\)以外の面は、\(G,G^{\prime}\)の間で変化しません。

したがって、面の個数に注目すれば、\(G\)は\(G^{\prime}\)より1個多くなります。\(G^{\prime}\)の定義より、辺も1個多いのでした。よって、帰納法の仮定と合わせれば、\(\mathrm{card}(V(G))-\mathrm{card}(E(G))+\mathrm{card}(F(G)=2\)が成り立つことがわかりました。

 

オイラーの多面体定理

今回紹介したのは平面グラフですが、立体的な図形、凸多面体についても同様の結果が成り立つことが知られています。

\(\mathrm{card}(V),\mathrm{card}(E),\mathrm{card}(F)\)を凸多面体の頂点、辺、面の個数とする。次の等式が成り立つ。

\[\mathrm{card}(V)-\mathrm{card}(E)+\mathrm{card}(F)=2\]

例えば上の平面グラフは、正四面体、立方体(正六面体)を平面グラフに落とし込んだものです。普通に立方体を平面上に描くと、面の影になって辺が交差する部分が生まれてしまいますが、「裏側」の面を外側の1つの面としてグラフで表すことはできます。このように、多面体の性質を平面グラフに落とし込んで、オイラーの公式を適用することができます。

多面体の例として有名なのは、正四面体、正六面体、正八面体、正十二面体、正二十面体といった正多面体です。これらはプラトン立体とも呼ばれています。

正多面体とは、平面グラフとして見れば、頂点の次数\(d\)、面に隣接する辺の数\(k\)がすべて一定のものです。例えば立方体なら、\(d=3,k=4\)です。正多面体であると、\(d,k \geq 3\)となり、この条件とオイラーの公式、握手の補題から、\(d,k \)が限られた5通りしかないことが示せます。詳しくは「離散数学への招待〈上〉」を参照。

 

以上、オイラーの公式と具体例、証明、多面体定理について紹介してきました。

オイラーの公式に登場する、頂点、辺、面の個数に関する交代和のようなものは、位相幾何学(トポロジー)においてオイラー標数として一般化されます。図形の性質を量として捉える、というのはとても便利な議論です。

オイラーの公式は、一見すると不思議な等式に見えますが、簡単なケースから考えれば確かに成り立つ内容です。木のケースと違って、面が生まれるケースも考慮に入れた等式なのがポイントですね。

木村すらいむ(@kimu3_slime)でした。ではでは。

 

離散数学への招待〈上〉

離散数学への招待〈上〉

posted with AmaQuick at 2021.03.10
マトウシェク,J.(著), ネシェトリル,J.(著), Matousek,Jir´i(原著), Nesetril,Jaroslav(原著), 生也, 根上(翻訳), 敦浩, 中本(翻訳)
シュプリンガー・フェアラーク東京 (2002-12T)
5つ星のうち3.7
¥1,773 (中古品)

 

離散数学への招待・下

離散数学への招待・下

posted with AmaQuick at 2021.03.10
J.マトウシェク(著), J.ネシェトリル(著)
丸善出版 (2012-07-17T00:00:01Z)
5つ星のうち5.0
¥11,800 (中古品)

 

Graph Theory (Graduate Texts in Mathematics)
Diestel, Reinhard(著)
Springer (2018-06-05T00:00:01Z)
5つ星のうち4.1
¥6,933

 

こちらもおすすめ

グラフ理論入門:グラフとは、グラフの同型

グラフ理論における木とは、判定法、オイラーの公式

平面グラフ、面とは何か、クラトフスキーの定理