平面グラフとオイラーの定理の応用
完全グラフ および完全二部グラフ は平面的グラフでない(平面に交差なしで書けない)。
平面的グラフとは
平面的グラフとは
頂点以外の点で辺が交差しないように平面に書けるようなグラフを平面的グラフといいます。交差しないように実際に書いたものを平面グラフといいます。
なお,グラフ理論では平面に「書く」と言わずに 「埋め込む」と言うので,以下でも「埋め込む」という言葉を使います。
例えば,完全グラフ は左上図のように埋め込むと頂点以外で交差してしまっていますが,工夫すれば右上図のように交差なしで埋め込むことができるので平面的グラフです。
同様に,完全二部グラフ も左下図ではダメですが,右下図のように交差なしで埋め込めるので平面的グラフであることが分かります。
※完全グラフ,完全二部グラフ,連結などの意味が分からない方はグラフ理論の基礎の下の方を参照してください。
この記事の目標は , が平面的グラフでないことを証明することです。 や はどう頑張っても平面に交差なしで埋め込めないのです!
オイラーの定理
オイラーの定理
や が平面的グラフでないことを証明するためにオイラーの定理を用います。
連結な平面的グラフを平面に交差なしで埋め込んだとき,頂点の数を ,辺の数を ,面の数を (一番外側の領域も一つの面とみなす)とすると が成立する。
例えば,さきほどの の例(右上図)では となりオイラーの定理が成立しています。
証明は,空間図形(凸多面体)におけるオイラーの多面体定理と同様です。オイラーの多面体定理の意味と証明のstep2以降を参照して下さい。
完全グラフ が平面的グラフでないことの証明
完全グラフ が平面的グラフでないことの証明
オイラーの定理を用いて,「平面的グラフなら辺の数は多過ぎない」という不等式を導きます。そして, は辺の数が多すぎてその制約を破っていることを示します。
平面的グラフは平面に交差なしで埋め込める。
が平面に交差なしで埋め込めたとする。このとき,以下の2つが成立する。
1. 各辺はちょうど2つの面の境界である
理由:平面に埋め込まれたグラフにおいて,各辺には「両側」があるため,2つ以下の面の境界となる。ある辺が閉路に含まれている時,閉路によって辺の「両側」は分断されるので,2つの異なる面の境界になる。そして, ではすべての辺が閉路に含まれている。
2. 各面は3つ以上の辺に囲まれる
理由:平面に埋め込まれたグラフにおいて,各面の境界は閉路を含む(そもそも閉路が存在しないグラフは例外だが, は閉路を含む)。そして,単純グラフでは閉路の長さは3以上である。
上記の1と2より, が成立する(→補足)。
これにオイラーの定理: を用いて を消去すると,
よって, を得る。
しかし, は であり,上の不等式を満たしていないので,背理法により平面的グラフではない。
補足:
ただし, は面全体の集合, は に隣接する辺の数です。
完全グラフ が平面的グラフでないことの証明
完全グラフ が平面的グラフでないことの証明
大筋はさきほどと同じですが, の場合には ではうまくいきません。二部グラフであることを使ってより強い不等式を導きます。
が平面に交差なしで埋め込めたとする。このとき,さきほどと同様に考えると,以下の2つが成立する。
1. 各辺はちょうど2つの面の境界である
2. 各面は4つ以上の辺に囲まれる
(2については,単純二部グラフの閉路の長さが 4以上になることからわかる)
したがって,さきほどと同様に を得る。
オイラーの定理と合わせて,
,つまり 。
しかし, は であり上の不等式を満たしていないので平面的グラフではない。
クラトフスキーの定理
クラトフスキーの定理
最後に,非常に発展的ですがクラトフスキーの定理を紹介しておきます。与えられたグラフが平面的グラフかどうか判定するために使える偉大な定理です。
グラフ が平面的グラフ は および をマイナーとして含まない。
- 「マイナーとして」という部分は厳密に説明するのはやや大変です,気になる人は調べてみてください。
- や は平面的グラフではないということから は上記の議論でなんとなく納得できるでしょう。
- がすごい結果です。証明はかなり難しいです。
や は平面的グラフではありませんが,実はドーナツの表面には交差なしで埋め込めます。