巡回セールスマン問題の多項式時間で解けるクラスへの計算幾何学からの取り組み

点击翻译按钮获取中文摘要

巡回セールスマン問題(以下、TSP)とは与えられた複数の都市をすべて1回ずつ通り、出発点に戻ってくるような最短経路を見つける問題である。この問題はNP困難のクラスに属し、都市数が増えたとき実用的な時間(多項式時間)で最短経路(最適解)を求めるのは不可能と予想される代表例になっている。そこで、実社会での応用の観点から、実用的は時間で最適解に近い解を求める近似解法の研究がさかんに行われてきた。TSPの近似解法を考える際、木は重要な概念の1つである。この木は、グラフ理論においてもさまざまな研究がなされている。例えば、与えられたグラフG_1,…,G_k,Hに対し、HがG_1,…,G_kを辺素に含むことができるかどうかを判定する問題はNP完全に属しており、一般にその判定は難しい。そこで、さまざまなグラフのクラスに関する十分条件について研究されてきた。この問題に対し、特にHを平面グラフにした場合どのようなグラフを辺素に含むことができるかに興味を持っている。今年度は2つの木の平面グラフへの埋め込みに関する研究を行った。Garciaら(2002)は、2つのスターでない木はある平面グラフに辺素に埋め込むことができると予想した。同じ論文で、Garciaらは、スターでない木とパスはある平面グラフに辺素に埋め込めることを示している。予想の解決を目標に、より広い木のクラスについて考えた。まず、スターのいくつかの辺を1回細分して得られるグラフとスターでない木に、2つのキャタピラ、について榎本,太田,神田,枡井とともに示した。また、直径5以下のキャタピラとスターでない木に関して構成的に証明し、最終的にスターでないキャタピラとスターでない木について太田とともに示した。この証明方法が予想の解決の糸口にならないかを考察することが今後の課題である。