[習題] 今天習題課3.19

[averageman (In average sense)]

我是今天習題課上去解3.19的同學，

對不起今天有些地方寫錯（還掛黑板...）

那個演算過程並不能保證每一次造出的
新minimum spanning tree T'=T+e-e'和E的共用邊會變多，
因為取e'時有可能e'屬於E(E)，這時候造出的T'=T+e-e'和E的共用邊數不變。
但即使如此，也不影響最終結果。

之所以取最早加入E(E)-E(T)的e（在第k步加入），
是因為這樣取e，使得e'若在E(E)∩E(T)，則一定在第k步之後加入，
亦即E(E)-E(T')中每個邊都是第k步之後加入，
所以仍然可以重複造T'，在有限次數內讓E(E)-E(T')=ψ。

假如任意取"e屬於E(E)-E(T)"，就可能掉進無窮迴圈。

--
補上e'的取法：
                _
在加入e之前的S和S，唯一存在path in T連接e的兩端
                       _
這條path上存在邊跨越S和S，取為e'

因此這個過程沒有保證e'屬於E(T)-E(E)。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.252.222
推 over::)
※ 編輯: averageman      來自: 140.112.252.222      (11/07 18:20)