グラフと地図：何が何とつながっているかだけを見る図
1652 年の版画に描かれたケーニヒスベルク。プレーゲル川、二つの島、七つの橋が見える。橋の問題を解くために、オイラーはこの絵が示すもののほとんどすべてを捨てた。Merian-Erben · Wikimedia Commons · パブリックドメイン プロイセンの町ケーニヒスベルクはプレーゲル川に貫かれ、川には二つの島があり、七つの橋が町の四つの部分を結んでいた。住民たちは、どの橋もちょうど一回ずつ渡る散歩ができるかどうかを知りたがった。1736 年、オイラーはそれができないことを証明した。歴史の本のケーニヒスベルクの橋の文章がその証明を語っている。ここで関心があるのは、オイラーが図に対して何をしたかである。
地図を捨てる 町の地図は、通り、家、距離、川の幅、島の形を示す。オイラーは、そのどれも問題には関係がないことに気づいた。大事なのは町のどの部分がどの橋で結ばれているかだけである。各部分は一つの点になり、各橋は二つの点を結ぶ一本の線になる。その結果が今日グラフと呼ばれるものである。四つの点と七本の線だ。
このグラフでは、大きさも距離も形も意味をもたない。線を伸ばしても、点を動かしても、全体を曲げてもかまわない。つながりが変わらないかぎり、グラフは同じグラフである。パースの言葉で言えば、グラフはごく特殊なイコンである。町に似ているのはつながりだけなのだ。何を写すかを厳しく選んだイコンである。
答えを浮かび上がらせたのは、まさにこの切り詰められた図だった。散歩の途中で、ある点に橋を渡って入るたびに、別の橋を渡って出ていかなければならない。だから道筋の途中にある点は、どれも偶数本の線につながっていなければならない。ケーニヒスベルクでは、四つの点はそれぞれ $5$、$3$、$3$、$3$ 本の線につながっている。すべて奇数である。そのような散歩は不可能だ。
地図であることをやめた地図 1931 年、ロンドン地下鉄の製図技師ハリー・ベックが新しい路線図を提案した。古い地図は地理に従っていたので、路線は都心でもつれ、郊外ではばらばらに広がり、誰にも読めなかった。ベックは、乗客が知る必要があるのは駅がどこにあるかではなく、駅がどんな順番で並び、どこで乗り換えるかだと気づいた。彼は水平、垂直、$45°$ の直線だけを使い、駅の間隔をすべて等しくした。
1933 年に発行されたベックの路線図は、地図ではなくグラフである。地理をすっかりゆがめているが、まさにそれが役に立つ理由なのだ。世界のほとんどすべての地下鉄――サンパウロ、東京、上海の地下鉄も含めて――が同じ原理を採用している。その代償として、観光客はときどき、歩けば五分の駅まで地下鉄に乗ってしまう。路線図の上では遠く見えるからである。
同じグラフ、違う描き方 つながりだけが大事なので、同じグラフをまったく違うふうに描くことができる。二本の対角線を引いた正方形と、上から見た三角錐は、同じグラフである。四つの点が、どの二つも結ばれている。二つの絵が同じグラフを表しているかどうかを判定するのは、大きなグラフでは驚くほど難しい問題であり、グラフ同型問題という名前がついている。
描き方が大事になることもある。どの二本の線も交差しないように描けるグラフは平面的である。たとえば、プリント基板を一層だけで作れるかどうかは、これで決まる。
三軒の家と三つの供給設備
古いパズルがある。三軒の家をそれぞれ三つの供給設備――水道、電気、ガス――につなぎ、どの二本の管も交差させないというものだ。挑戦した人は誰でも最後には交差にぶつかるが、それは腕が足りないからではない。片側に三つ、反対側に三つの点があり、九本の線ですべてを結んだグラフは $K_{3,3}$ と呼ばれ、平面的ではないのである。1930 年、ポーランドのカジミェシュ・クラトフスキは、グラフが平面的であるのは、その中に $K_{3,3}$ も、五つの点がどの二つも結ばれたグラフ $K_5$ も隠れていないとき、そしてそのときに限ることを証明した。 練習：八つ目の橋住民たちが川の両岸を結ぶ八つ目の橋を架けたら、散歩はできるようになるか。
両岸はもともとそれぞれ $3$ 本の線につながっていた。新しい橋で、それぞれ $4$ 本になる。次数は $5$、$4$、$4$、$3$ となり、奇数の点は二つだけになる。どの橋も一回ずつ渡る散歩ができるようになる。一方の奇数の点から出発し、もう一方の奇数の点で終わればよい。
練習：K₃,₃ が平面的でない理由平面グラフについてのオイラーの公式 $V-E+F=2$（頂点の数ひく辺の数たす面の数）を使って、$K_{3,3}$ が平面的でないことを示せ。
$K_{3,3}$ は $V=6$、$E=9$ である。もし平面的なら、面は $F=2-6+9=5$ 個ある。$K_{3,3}$ には三角形がない（どの線も家から設備へ向かう）ので、どの面も少なくとも $4$ 本の辺をもつ。各辺は高々 $2$ つの面の境界なので、$4F\leq2E$、つまり $20\leq18$ となり矛盾する。したがって交差のない描き方は存在しない。
章の目次 · ← アルガン平面：居場所を見つけた虚数 · 言葉のない証明 →
