[习题] 今天习题课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