近似度が3/2以下である証明
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/04/14 10:13 UTC 版)
「クリストフィードのアルゴリズム」の記事における「近似度が3/2以下である証明」の解説
このアルゴリズムによって生成された解の重みは最適な解の重みに対し3/2以下である。証明のため、Cを巡回セールスマン問題の最適解とする。最適解Cから辺を1つ削除すると全域木となり、その全域木の重みは（最小全域木の定義より）最小全域木の重みより小さくならないため、w(T) ≤ w(C)である。次に、Oの頂点に対し、最適解の経路Cの順に番号を付け、Cの順で奇数番目の辺の集合と、偶数番目の辺の集合の、2つの辺集合に分割する。それぞれの辺の集合はOの最適マッチングに対応し、それぞれの経路の2つの端点と一致する。そして、その最適マッチングの辺の重みは最適解Cによるものであるため、マッチングの重みは最適解の対応する辺の重み以上である。これらの2つの経路の集合はCの辺を2分割するため、経路の集合の1つはCの重みの半分以上であり、それに対応するマッチングはCの重みの半分以下である。最小重み最適マッチングは最小の重みを選択するアルゴリズムであるため、w(M) ≤ w(C)/2が保証される。そしてTとMの重みを足すことで、オイラー回路の重みが3w(C)/2以下であることがわかる。点を飛ばす処理（近道）によって、重みは増えないため、このアルゴリズムによって生成された経路の重みは最大3w(C)/2である。
※この「近似度が3/2以下である証明」の解説は、「クリストフィードのアルゴリズム」の解説の一部です。
「近似度が3/2以下である証明」を含む「クリストフィードのアルゴリズム」の記事については、「クリストフィードのアルゴリズム」の概要を参照ください。
- 近似度が3/2以下である証明のページへのリンク
