Re: [理工] 100中央(DS&ALGO)

[Byzantin (拜占庭)]

純分享第五題

5.1

ETSP的cycle C*即為weight最小之hamiltonian cycle

而hamiltonian cycle去掉任一邊即為spanning tree

所以

weight of minimum spanning tree T* <= weight of minimum hamiltonian cycle C*

即w(T*) <= w(C*)

得證

5.2

先找出一MST T*，接著繞一圈(每個edge走兩遍，類似將tree包起來)

                 A
                / \
               B   C

舉上圖為例來說就是A→B→A→C→A

這樣的weight為2w(T*)

接著轉換成hamiltonian cycle C

即若有重複走過之noded則跳過 以上圖來說即為A→B→C→A

根據triangle inequality，這樣的cost一定比較小

所以w(C) <= 2w(T*) , 且w(C*) <= w(C)

由5.1知w(T*) <= w(C*)

因此w(C*) <= w(C) <= 2w(C*) , 得證




--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.169.104.205
※ 編輯: Byzantin        來自: 118.169.104.205      (01/12 20:44)
推 RdMax:推一個
推 cancj06:推