TSPの最短距離のパスのエッジは交差しない

　

　巡回セールスマン問題において、出発点から全ての都市（ノード）を巡って出発点に戻ったとき、そのパスを構成するいかなる道（エッジ）も交差しない。

　どのような問題でもそうなのかもしれませんが、巡回セールマン問題の解法アルゴリズムにおいても小さな論理（定理）の積み上げ（組み合わせ）が重要になってきます。

　場合によっては、条件も必要になりますが、条件によってはその解法（主張）を一般化できないものと考えます。

　さて、わたしは学会などで定説となっている定理または巡回セールスマン問題についての特性などを知りません。

　従って、ここで述べる内容（主張）は、全て検証されていないはずだと思いますし、重複しているかもしれません。

　このことが、市井（民間）の数学者の悲しいところであります。

交差しない道（エッジ）

　この定理は巡回セールマン問題の解法のための絶対条件ではありませんが、この定理を条件としてアルゴリズムを構築するとN！個存在するパスの多くを計算から除外することができます。

　エッジは線分なので始点と終点を持つ有限直線となります。

また、解法の初期の段階では線分は向きを持たないので２つの端点は始点と終点の区別を持ちません。

　著者の今回の主張は、ユークリッド２次元空間が条件となっていますが、必ずしもユークリッド空間である必要はなく、拡張する場合は直線ではなく測地線を用いればよいのではないかと考えています。

　ただし、３次元以上の空間に対してはいくつかの考慮が必要になるかもしれません。

　さて、「交差する」とは、２つの線分が有限線分の内部で交差するということです。有限線分の延長上で交差する線分は対象となりません。

証明

　この記事の最上部に図ー１を用意しました。

線分AとCを結ぶパスAーCや線分BとDを結ぶパスBーDがいかなるノードを含むパスであってもこの証明に影響を与えません。

　問題となるのは、A～D点の結線の組み合わせだけとなります。

　この４点の結線の組み合わせは次の３通りだけとなります。

①　A-BとC-D

②　A-CとB-D

③　A-DとB-C

　ここで、②の組み合わせは２つのパスに分解されてしまいますので除外したいと思います。

つまり、①と③の距離のどちらが短いかということが問題となります。

　この証明は、三角形の性質を用いれば簡単なので省略したいと思います。

結論として道（エッジ）は交差しないということです。

　尚、球面上の三角形でもこの性質は受け継がれます。