13.1 グラフの描画

図 \(\text{13.1}\) に示すように、三匹の犬と三軒の家があるとしよう。それぞれの犬とそれぞれの家を結ぶ全部で \(9\) 個の道を作るとき、どの道も交わらないようにできるだろうか？

同様の問題は quadrapusクアドラパスと呼ばれる希少な動物が握手をしようとしたときにも生じる。タコに似た海洋生物である quadrapus は、\(8\) 本ではなく \(4\) 本の伸縮自在な腕を持つ。図 \(\text{13.2}\) のように \(5\) 匹の quadrapus が海底にいるとしよう。それぞれが他の \(4\) 匹と同時に握手をするとき、どの腕も交わらないようにできるだろうか？

5 匹の quadrapus (4 本の腕を持つ海洋生物) — 図 13.2\(5\) 匹の quadrapus (\(4\) 本の腕を持つ海洋生物)

これら二つのパズルはグラフを平面に描画する問題と解釈できる。犬と家を頂点に置き換えれば、一つ目のパズルは「\(6\) 個の頂点を持ち、最初の \(3\) 個の頂点それぞれと最後の \(3\) 個の頂点それぞれの間に辺が存在するグラフは平面に描画できるか？」と言い換えられる。このグラフは完全二部グラフ (complete bipartite graph) \(K_{3,3}\) と呼ばれる。\(K_{3,3}\) を図 \(\text{13.3}\) \(\text{(a)}\) に示す。同様に、quadrapus のパズルは「完全グラフ \(K_{5}\) は平面に描画できるか？」と言い換えられる。\(K_{5}\) を図 \(\text{13.3}\) \(\text{(b)}\) に示す。

K_{3,3} と K_{5}: 辺が交差しないように描画できるか？ — 図 13.3\(K_{3,3}\) と \(K_{5}\): 辺が交差しないように描画できるか？

パズルの解答はいずれも「できない ── あと一歩で！」である。実は、\(K_{3,3}\) または \(K_{5}\) から任意の辺を \(1\) 本だけ除去したグラフは辺の交差なく平面に描画できる (図 \(\text{13.4}\))。

K_{3,3} および K_{5} から \langle u\\text{---}\v \rangle を除去したグラフの平面描画 — 図 13.4\(K_{3,3}\) および \(K_{5}\) から \(\langle u\>\text{---}\>v \rangle\) を除去したグラフの平面描画

グラフの平面描画に関する理論は例えば回路のレイアウトで利用される。他にもプログラムのフローチャート、組織図、スケジュールの衝突といったデータを視覚的に表現するとき有用となる。こういった応用では、辺の交差を最小限にしつつグラフを平面に描画することが目標になる。