巡回セールスマン問題（ＴＳＰ）とはｎ頂点の完全グラフＫnのすべての頂点を回って戻ってくる最短ハミルトン経路を問う問題である．

　巡回セールスマン問題（ＴＳＰ）は特殊な数学パズルではなく，半導体チップの穿孔，遺伝子情報の染色体上の配置，データのＤＶＤ上の配置，など実際への応用がたくさんある．

　それまで解かれていない難問を解くと大々的に報じられ、研究者の間で騒ぎになる．しかしながら，ＴＳＰについては多項式時間のアルゴリズムは知られていない．これまでの最善の結果は１９３２年に発表されたＯ（ｎ^2２^n）で計算する解法である．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【１】巡回セールスマン多面体

　置換行列が完全２部グラフＫn,nと対応するのに対して，巡回セールスマン多面体は完全グラフＫnに対応している．

　この多面体は（ｎ−１）！／２個の頂点をもつnＣ2−ｎ＝ｎ（ｎ−３）／２次元の多面体である．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝