数学特別演習（第15回）

今日は、与えられたグラフに対し「巡回路」を直接作る代わりに、より条件を緩めた問題を解く「緩和法」を扱いました。

巡回路を直接求める問題に対して「より条件を緩めた問題」というのが「1-木」と呼ばれるグラフの計算です。1-木は、前回扱ったヒューリスティックで求めた巡回路からノードを1個取り除き、残ったノードに関する「最小全域木」を構成し、それに、先程取り除いたノードを辺でつないで加えることで作られます。

このとき、巡回路は1-木の集合に含まれるので、経路の長さが最小となる1-木が求まれば、その経路の長さは、経路の長さが最小の巡回路の長さの下界になります。ポイントは、最小1-木を求めるのにかかる計算量が、最小全域木を求めるのと同程度（＝多項式時間）の速さで、巡回路の長さの下界が求まるという点です。

さて、今日の最後の発表者は、来月卒業を控えた4年生の人で、今回、早く成績を出す必要もあり、発表してもらいましたが、最後に1年生の履修者にメッセージをもらいました。数学は1つ1つの理論の積み重ねであることや、いろいろな分野の関連性があること、そういったことを念頭に学習することの大切さを話してくれました。1年生にとっても、今回の話はよい刺激になったのではないかと思います。

次回は、巡回路を求める新しいアルゴリズムで、求めた巡回路の長さが、最適な巡回路に比べて高々1.5倍で抑えられるようなアルゴリズムを扱います。