2006/01/18(水)ペテルセングラフー

はてブ数 2006/01/18 03:06 計算機な日記::算数学つーさ

綺麗なモノには目がないつーさです。

ある国にはいくつかの空港があります。
どの空港からも国内便は3本しか出ていません。
しかし、どの空港から出発しても、直行便または1回の乗り換えで、
他のすべての空港に行くことができます。
さて、最大で空港は何カ所設置できるでしょうか。

かのピーター・フランクル氏が書いた「頭のよくなる本」に出てた問題なのですが。

解答例としては……

直行便で行ける空港は3カ所。
そこから乗り換えていける空港は2カ所(戻らないから)。
そこに出発点の空港を足して、3+3*2+1 = 10 カ所。

これが答えなのですが、それはともかく、それを実現する空路マップの例として
ペテルセン・グラフ」というのがあるのです。

グラフの魅力、あなたにはわかってもらえますか?

で、本の答えの続きに書いてあったんですが。
国内便の本数を「3」から「7」にした時も、対象な構造が得られるそうなんです。
どんな接続を行えばいいのかも見えてこないのですが、一目見てみたいなと思った次第です。

(というわけで、つづくかも)