📂グラフ理論

平面グラフとクラトフスキーの定理

定義

平面グラフ

グラフを平面に描いた時、エッジが重ならずに描けるなら、そのグラフを平面グラフと言う。

説明

平面グラフが描かれると、平面上で区切られる領域をフェース^faceと呼ぶ。次の平面グラフ $K_{4}$ は四つのフェース $f_{1}, f_{2}, f_{3}, f_{4}$ を持ち、その中でも特にバウンドされていない $f_{4}$ を無限フェース^{infinite Face}と呼ぶ。

平面グラフはその名前の通り、適合する部分なしに平面に描けるグラフのことを言う。理解を深めるためには、平面グラフではないグラフが何かを見る方がいい。例えば、完全グラフ $K_{5}$ と二部グラフ $K_{3,3}$ は平面グラフではないが、どのようにしても重なるエッジがあるためだ。

数学者なら当然、グラフが平面グラフになる条件が何かが気になるだろう。これについては、上の例で一般化された定理が知られている。

定理

クラトフスキーの定理 ¹

グラフが平面グラフであることと、そのグラフのサブグラフが $K_{5}$ や $K_{3,3}$ とホメオモーフィックなものがないことは同値である。

意義

簡単に言えば、$K_{5}$ に似ているものや$K_{3,3}$ に似ているものが含まれていれば平面グラフではなく、なければ平面グラフであることを保証してくれる定理だ。一見すると、この定理で平面グラフについて全てが解決されるように見えるが、グラフ理論は平面グラフを根に数多くの概念や問題を生み出してきた。最も簡単な一般化として、$k \in \mathbb{N}$ 個のエッジが重なることを許すことから始め、数学全般でよく見られるデュアル、点と線と面などを扱う証明幾何学の領域はもちろん、空間の構造自体に関心を持つ組み合わせ位相幾何学にも続く大旅行の始まりである。

だからと言って、グラフを専攻していない人が平面グラフに関する様々な定理を覚えて証明に慣れる必要はないが、もっと広い数学の世界を見るために必ず知っておくべき概念だと言えるだろう。定義を見ればわかるが、そもそも平面グラフを理解するために広い数学的基盤が必要なわけではない。だから、少なくとも知っておこう。

自閉症テスト

古いインターネットのミームの一つで、上のような問題を自閉症テスト^{autism test}と言う。問題では、水道と電力、ガスを三つの家に供給しなければならないが、その線が交差してはならないという制限をかけ、「難しいが可能だ」と言う。これを純粋な数学問題として考えれば、クラトフスキーの定理によって不可能だと反論できる。これらの切り抜きが’自閉症テスト’と呼ばれる理由は、‘不可能なのに解答にこだわり、全ての可能性を検討する様子が自閉症に似ている’という種類の軽蔑的、侮辱的なジョークであるためだろう。

数学問題でない形でアプローチすると、上のような解決策もある。実際、自閉症テストの健全な楽しみは、このように問題の条件を破る強引または斬新な反則にある。