[習題] 今天習題課3.19

作者: averageman (In average sense)   2007-11-06 23:01:52
我是今天習題課上去解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)",就可能掉進無窮迴圈。

Links booklink

Contact Us: admin [ a t ] ucptt.com