2014/11/19

平面グラフとオイラーの定理の応用

分野: グラフ理論  レベル: マニアック

完全グラフ $K_5$ および完全二部グラフ $K_{3,3}$ は平面的グラフでない(平面に交差なしで書けない)。

平面的グラフとは

頂点以外の点で辺が交差しないように平面に書けるようなグラフを平面的グラフといいます。(交差しないように実際に書いたものを平面グラフといいます)

なお,グラフ理論では平面に「書く」と言わずに「埋め込む」と言うので,以下でも「埋め込む」という言葉を使います。

平面への埋め込み

例えば,完全グラフ $K_4$ は左上図のように埋め込むと頂点以外で交差してしまっていますが,工夫すれば右上図のように交差なしで埋め込むことができるので平面的グラフです。

同様に,完全二部グラフ $K_{3,2}$ も左下図ではダメですが,右下図のように交差なしで埋め込めるので平面的グラフであることが分かります。

※完全グラフ,完全二部グラフなどの意味が分からない方はグラフ理論の基礎の下の方を参照してください。

本記事の目標は $K_5$,$K_{3,3}$ が平面的グラフでないことを証明することです。 $K_5$ や $K_{3,3}$ はどう頑張っても平面に交差なしで埋め込めないのです!

オイラーの定理

$K_5$ や $K_{3,3}$ が平面的グラフでないことを証明するためにオイラーの定理を用います。

オイラーの定理:平面的グラフを平面に交差なしで埋め込んだとき,頂点の数を $v$,辺の数を $e$,面の数を $f$(一番外側の領域も一つの面とみなす)とすると $v-e+f=2$ が成立する。

例えば,先ほどの $K_4$ の例(右上図)では $v=4,e=6,f=4$ となりオイラーの定理が成立しています。

証明は,空間図形(凸多面体)におけるオイラーの多面体定理と同様です。オイラーの多面体定理の証明のstep2以降を参照して下さい。

完全グラフ $K_5$ が平面的グラフでないことの証明

方針:オイラーの定理を用いて,「平面的グラフなら辺の数は多過ぎない」という不等式を導きます。そして,$K_5$ は辺の数が多すぎてその制約を破っていることを示します。

完全グラフK_5

証明

平面的グラフは平面に交差なしで埋め込める。そのとき,各面には最低三本以上の辺が境界として使われている。よって,述べ $3f$ 本以上の辺が境界として使われている。また,一つの辺は二つの面の境界として使われている。
よって,$2e\geq 3f$ が成立する(わからない人は →補足)。

これにオイラーの定理:$f=2-v+e$ を用いて $f$ を消去すると,
$2e\geq 3(2-v+e)$
よって,$e\leq 3v-6$ を得る。

平面的グラフなら上の不等式を満たしていないといけない。しかし,$K_5$ は $v=5,e=10$ であり上の不等式を満たしていないので平面的グラフではない。

補足:
$2e=\displaystyle\sum_{F_0\in F}e(F_0)\geq\displaystyle\sum_{F_0\in F}3=3f$
ただし,$F$ は面全体の集合,$e(F_0)$ は $F_0$ に隣接する枝の数です。

完全グラフ $K_{3,3}$ が平面的グラフでないことの証明

大筋は先ほどと同じですが,$K_{3,3}$ の場合には $e\leq 3v-6$ ではうまくいきません。二部グラフであることを使ってより強い不等式を導きます。

証明

完全二部グラフK_3,3

平面的二部グラフは平面に交差なしで埋め込んだときに,一つの面の境界として使われる辺の数は偶数である(奇数角形が存在すると頂点を二グループに分けられない)。よって,各面には最低四本以上の辺が境界として使われている。

したがって,先ほどと同様に $2e\geq 4f$ を得る。
オイラーの定理と合わせて,
$e\geq 2(2-v+e)$,つまり $e\leq 2v-4$ 。

平面的二部グラフなら上の不等式を満たしていないといけない。しかし,$K_{3,3}$ は $v=6,e=9$ であり上の不等式を満たしていないので平面的グラフではない。

クラトフスキーの定理

最後に,非常に発展的ですがクラトフスキーの定理を紹介しておきます。与えられたグラフが平面的グラフかどうか判定するために使える偉大な定理です。

クラトフスキー(Kuratowski)の定理:
グラフ $G$ が平面的グラフ $\iff$ $G$ は $K_{5}$ および $K_{3,3}$ をマイナーとして含まない。

  • 「マイナーとして」という部分は厳密に説明するのはやや大変です,気になる人は調べてみてください。
  • $K_5$ や $K_{3,3}$ は平面的グラフではないということから $\Rightarrow$ は上記の議論でなんとなく納得できるでしょう。
  • $\Leftarrow$ がすごい結果です。証明はかなり難しいです。
$K_5$ や $K_{3,3}$ は平面的グラフではありませんが,実はドーナツの表面には交差なしで埋め込めます。
分野: グラフ理論  レベル: マニアック