V + F - E = 2
ここのページの説明が分かりやすかったです。
説明の概略は以下のとおり。
- 多面体の一つの面を取り外して平面に押しつぶして平面グラフを作る。
- グラフが木になるまで、枝をとりのぞいていく。（枝を1つ減らすと面の数も1つ減るのでV+F-Eは不変）
- 木の場合は、V+F-E=2が分かっている。
外側の無限の広さを持った空間も一つの面として考えることで、取り外した面との整合性をとっているのが面白いと思いました。
上記のページにはもう一つ面白い関係が紹介されていました。任意の平面グラフにおいて
2E ≧3F
が成り立つ。
この説明が分かりづらかったので調べてみました。以下のページの説明が分かりやすいかったです。
V=2, E=1の連結グラフの場合は上の関係は成り立たないので、正しくは「V≧3の連結な平面グラフ」という条件のもと、
2E ≧3F
証明の概略は以下のようになります。まず大きくi)平面グラフGの辺の数が3未満の場合、ii) それ以外の場合で場合分けします。
i)のとき、V≧3という条件と合わせると、V=3、E=2、F=1の場合しかありえません。このとき、2E > 3Fなので成り立つ。
ii)のとき、すべての面において境界となる辺の数の和（以下ではSum(|e(f)|)と書きます。）を考えます。ある面の境界となる辺の数は3以上です。（ii)の条件より無限に広がる外側の面の境界辺の数も3以上であることに注意。）面はF個あるので、Sum(|e(f)|)は3F以上です。
次に辺の観点から考えます。一つの辺は多くても面の境界として数えられるのは2回だけです。（一つの辺が3つ以上の面の境界とは成りえないから。）よって、Sum(|e(f)|)は2E以下です。
以上から、2E ≧ Sum(|e(f)|) ≧3Fとなります。
等号成立は、すべての枝が2つの面の境界となっていて、かつ、すべての面が3辺によって境界づけられる場合なので、V=3のときの完全グラフだけかと思います。参照元のページには"equality holds if and only if every face is a triangle."とありましたが、三頂点の完全グラフ意外にそれを満たすグラフってあるんでしょうか。。
0 件のコメント:
コメントを投稿