🕴️

グラフが無向木である場合の巡回セールスマン問題

2023/12/13に公開

この記事は「木 Advent Calendar 2023」の13日目です。
きのうの記事はまぐふらいさんの「Link Cut Treeの紹介」でした。
あしたの記事はそすうぽよさんの「木曜日」です。

主張

木上の巡回セールスマン問題（TSP）は $O(N)$ で解ける。
答えはすべての辺の重みの和×2となる。

頂点ひとつのグラフに葉を追加していくことを考えます。

頂点ひとつのグラフにおける巡回セールスマン問題の解は、空の閉路です。

あるグラフについて巡回セールスマン問題の答えが求まっているとき、そのグラフに辺と頂点（ー・）を追加したときの答えは、元のグラフの答えにその辺の重み×2を足したものになります。

どのような木も頂点ひとつのグラフに辺と頂点を追加することで作れるため、どのような木でも巡回セールスマン問題の答えは、すべての辺の重みの和×2となります。