じぶん更新日記・隠居の日々
1997年5月6日開設
Copyright(C)長谷川芳典



08月のインデックスへ戻る
最新版へ戻る



※クリックで全体表示。

　龍ノ口グリーンシャワーの森で見かけたゴマダラチョウ。翅の一部が欠けているが、どうにかこうにか飛んでいた。

2023年8月3日（木）




【連載】笑わない数学(5)四色問題(5)地図から平面グラフへの置き換え

　少し空いてしまったが、7月28日に続いて、 笑わない数学の#3『四色問題』についての感想・考察。

　まず、前回の日記の終わりのところで「すべての地図には少なくとも1つ五辺国以下の国が存在する｣に関連してオイラーの多面体定理の話題を取り上げたが、その後、重大な誤解をしていたことに気づいた。私は、二辺国、三辺国、．．．五辺国などと言われている時の「グラフ」と、『グラフ理論』で扱われている「グラフ」が同じものだと思っていたが、関連サイトやYouTube動画をいくつか視聴してみると、違った形で定義されていることが分かった。
　ウィキペディアの概説にも記されているように、四色問題をグラフ理論で捉えるためには、

●まず、地図の境界線をグラフの辺、境界線が接続する点をグラフの頂点としたグラフを作る。その双対グラフにおける頂点の彩色が、元の地図の塗分けと同じ問題となる。

というように置き換えが置き換えられる。例えば2つの国が国境で接している場合に上記の置き換えを行うと、2つの国はそれぞれ点、国境は線で表される。また例えばチェコの国旗のように3つの領域に分かれた国があった場合、上記の置き換えを行うと3つの点、「国境」は線となり、三角形ができあがる。
　なぜ、もとの地図のままではなく、「国を点」、「国境を線」に置き換えて考えるほうが良いのか？　根本的な理由はよく分からない。また置き換えた場合に発生する「面」が何を意味するのかも、考えれば考えるほど分からなくなってきた。

　1つ言えるのは、グラフ理論で扱われるグラフには、閉路のない「木」と、閉路つまり「面」を含むグラフがあるらしいということ。こちらの解説動画によれば、閉路の無い「木」では、

頂点の数−辺の数＝1

という関係が成り立つ。これは、どのような「木」であっても、辺（線）を1つずつ減らしていくと、同じだけ点も減ることになり簡単に証明できる。
　いっぽう、閉路を含む平面上のグラフでは、

頂点の数−辺の数＋面の数＝1

という関係が成り立つ。この場合も、閉路から辺を除いていっても等式関係は保たれ、いつかは「木」のグラフとなることで証明できる。
　同様にして、球面上のグラフを考えた場合、

頂点の数−辺の数＋面の数＝2

という関係（オイラーの多面体定理）が成り立つ。ここで右辺が1ではなく2となるのは、球面上では外側の領域も1つの面として数えているためである。

　なお、こちらの解説動画によれば、平面グラフの特徴として、
  • 辺に交差が無い。
  • ループが無い（同じ点にループするような辺はない）
  • 多重辺が無い（2つの点を結ぶ辺は1本のみ）
という3点が挙げられる。

　ということで元の地図問題の、

●すべての地図には少なくとも1つ五辺国以下の国が存在する

という定理は、平面グラフに置き換えると、

●平面グラフには必ず次数が5以下の頂点が存在する

ということになる。この証明を大ざっぱに記すと、
  • オイラーの定理から、v-e+f=2が成り立つ（但し、vは頂点数、eは辺数、fは面数）
  • e≦3ｖ−6を証明する
  • すべての頂点の次数が6以上となるような平面グラフが存在したと仮定すると、e≧3vとなるがこれは
    3v≦e≦3v−6
    となって矛盾する
  • このうち「e≦3v−6」は証明された結果なので正しい。よって、仮定のほうが間違っていた
ということになる。

　なぜ、元の地図のままではなく平面グラフに置き換えて考えるたほうが良いのかはよく分からないが、おそらく平面グラフのほうが、閉路ばかりでなく閉路の無い「木」までを含んだ拡張世界で考えることができるため都合がよいためではないかと思われる。

　次回に続く。