ドーナツ面上でのn個の都市連結

≪1≫ 平面上にn個に点があって、どの2点も直接(ほかの線と交わらずに)線で結ぶということを考えます。点の数が3個とか4個の場合はこれらは直接、線で結べます。

    

     

 点が5個になると、どうやっても交点が発生してしまうので、その地点では交わりを回避する必要があります。トンネルを掘って、下をくぐるとかです。(下図で、赤いトンネルのところ)

      

つまり、トンネルを掘る=穴が1個のドーナツ面上では、5点を結べることになります。

 

 

≪2≫ 穴の数をa個として、この曲面上における点の最大配置個数をf(a) としますと、上記のことは、

    

    

と表せるというわけです。

 

 これはたとえば、都市計画上、各都市間を直結するにはどれだけのトンネル(または高架)が必要か?といったインフラ整備面でも役立ちます。

 実のところ、a=1のドーナツ面では、下図のように、7個の都市を配置できます。

     

    【構成方法】
     1.n1から、となりのn2へは直結する。

     2.n3とn4へは、トンネルをくぐって直結する。

     3.以上をn2以下にも同様に施す。

 

 

≪3≫ つぎのステップは、さて8点は配置可能か?という点です。

 ここでいきなりですが、地図の彩色問題に登場するヒーウッドの公式;

     (式はWikiより引用)

で、g=1のときは必要彩色数が7っていう事実があります。これはつまり、7色で十分で、8番目の都市をもってきてもすべてを直結できない、仮に直結できるなら8色が必要となり、公式に矛盾。7都市の全直結は、上図の構成例で必要性がある。

 つまり、

    

が確定される。・・・さて、こんな論法で、合っていますかね?