名古屋大学 情報学研究科 数理情報学専攻 2017年8月実施 問題4 グラフ理論

Author

祭音Myyura

Description

頂点 (vertex) 集合 、辺 (edge) 集合 をもつ無向グラフ (undirected graph) を考える。

• を平面上に辺が交差することなく描画できるとき (non-crossing drawing exists)、そのように描画したものを平面グラフ (plane graph) と呼び、辺によって分割された領域のそれぞれを面 (face) と呼ぶ。平面グラフの外側の領域も面の一つである (外面 (outer face))。例えば図１は平面グラフであり から までの面がある。
• 頂点の列 が であるとき、このような列のことを閉路 (cycle) という。図１の は閉路である。
• 木 (tree) とは閉路のない連結 (connected) グラフのことをいう。例えば、図２は木である。木は平面グラフでもある。
• 頂点完全 (complete) グラフ とは、 を満たすようなグラフのことをいう。例えば図３のグラフは である。

以上を踏まえた上で、以下の各問に答えよ。

(1) 図１, 図２のグラフのそれぞれの頂点数、辺数、面数を答えよ。

(2) 平面グラフにおいて、一つの面は一つの閉路と (一対一) 対応するか。する場合、証明を与えよ。しない場合、そのような例を一つ挙げよ。

(3) 連結な平面グラフにおいてはオイラーの公式 (Euler's formula) が成立する。ただし、 は面数である。これを利用し、平面グラフにおいては、 が成立することを示せ。(ヒント：どの面も3本以上の辺に囲まれている)

(4) は平面グラフであるかどうかを、根拠と共に述べよ。

(5) (3) で取り上げたオイラーの公式 を証明せよ。必要ならば、木においては が成立することを用いて良い。

Kai

(1)

• 図１: 頂点数 , 辺数 , 面数
• 図２: 頂点数 , 辺数 , 面数

(2)

平面グラフにおいて、一つの面は一つの閉路と(一対一)対応しない。例えば、以下のような平面グラフ（四角形）を考える：

  v1----v2
   |    |
   |    |
  v4----v3

閉路は１つ（）ですが、面の２つ（内側の面と外側の面）あるので、一対一の対応は成立しない。

(3)

（ヒント：どの面も３本以上の辺に囲まれている）

外部領域も含め全ての領域が３本以上の辺に囲まれている。 そして、各辺は２つの領域を分けているから、各領域を囲む辺を全て数え上げると各辺を２度数えることになるので

が成り立つ。(i) とオイラーの公式から

即ち、

(4)

と は平面グラフ。（証明は略）

は平面グラフではない。 は 、 なので、もし平面グラフの形に書けたとすると、(3) により

でなければならない。それは に矛盾する。

は を含むので、平面グラフではない。

(5)

辺数 に関する数学的帰納法により証明する。

が一番少ないのは が木のときで であり、面は外側のひとつだけなので 。 よって となって成り立ちます。

が木でないときは、 内の閉路 と、 上の辺 を 本選んで

を考えます。 は の部分グラフゆえ平面グラフで、そのパラメータを , , とおくと

• 頂点は消していないので
• 辺は 1 本除去したので
• の表側の 2 つの面が 1 つにつながったので

よって

ここで に帰納法の仮定を使いました。