【Kruskal】求Kruskal算法正确性证明b

【Kruskal】求Kruskal算法正确性证明b

【答案】 证明：令G为任何一个与Kruskal算法产生的树F不同的树.考虑构造F的过程.令e为第一次选的一条不属于G的边.如果我们将e加入G,我们会得到一个圈C.这个圈不完全包含在F里面,因此在C中有一条不属于F的边f.如果我们将e加入G并删除f,我们就得到了一个新的树H.
　　我们想要证明H不比G贵.这意味着e不比f贵.用反证法.假设f比e便宜.
　　现在考虑这样一个问题：为什么Kruskal算法选择了f而不是e呢?唯一的原因只可能是f被排除了,即f与加入e之前被选入F的边会形成一个圈.但是所有这些已经被选的边都是G的边,因为e为第一次选的一条不属于G的边.又f本身属于G,所以G就包含了一个圈,这是不可能的（G是树）.这个矛盾证明了H不比G贵.
　　因此我们可以用H来代替G,而且H比G更接近F（即H与F有更多相同的边）.如果H不是F,重复以上步骤,我们得到一系列与H越来越接近的不比G贵的树.这个过程迟早会以F终结,这就证明了F不比G贵.
　　Kruskal算法的正确性也就得证.

这个问题的回答的对

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息