Kruskal证明

定理 对于任意给定的无向图G,克鲁斯卡尔算法构造G的一棵最小代价生成树。

证明

需要证明以下两点:(a)只要存在生成树,克鲁斯卡尔算法就能构造一棵生成树;(b)所构造的生成树代价最小。

(含义就是Kruskal算法能完成两件事情,第一个就是把生成树找到,只要这个连通图有生成树;第二就是,找出来的这个生成树会是最小生成树。接来下要证明的也就是这两个方面。)

对于(a),注意,克鲁斯卡尔算法只放弃形成环路的边,而删除一个连通图的环路中的一条边所得到的图仍然是连通的。因此,如果G一开始是连通的,则T和E的边总是构成一个连通图,算法不可能以E=空集且|T|<n-1终结。

(连接n个顶点至少需要n-1条边。这个可以使用归纳法来证明。由于T一定是连通的,进而来分析一个E是不是连通的。由于G一开始是连通的,E是G中的一部分,引入T后,可能把E分割成独立的几个连通的图,但几个独立的连通的图是通过T来连接的,T是连通的,所以T和E组成的图也会是连通的。由于克鲁斯卡尔算法得到的是一个连通的图,而且算法上是排除环路的,所以生成的连通图就是生成树。)

下面着重证明(b)。由于G只有有限生成树,所以一定有一棵代价最小的。设U是一棵最小代价生成树。T和U都恰好有n-1条边。如果T=U,则T就是最小代价生成树。这里假设T!=U。设k是在T中而不在U中的边的条数(k>0)。注意,k也是在U中而不在T中的条数。

(由(a)可以证明Kruskal算法可以构造生成树。下一步就是要证明得到的生成树是最小生成树。可以知道,连通图的生成树一定是有限的,因为所有边的挑选出n-1条来进行排列组合的结果也是有限的,而生成树是包含于这些排列组合的结果的,所以也是有限的。只要是有限的生成树,那么就一定存在一个最小生成树,可能不唯一,但一定存在。下面就是证明使用Kruskal算法找出来的生成树,要么与U一样,要么可以由U转换而来,还不会使代价改变。)

可以通过将U转换为T来证明T和U的代价相同,这种转换经过k个步骤。每经过一个步骤,在T中而不在U中的边的条数减少1,且转换后U的代价不变。最终,经过k步转换,U的代价和初始时相同,但已完全由T的边构成。这意味着T具有最小代价。

(如果我们能证明U确定可以转化为T,而且还可以保持代价不变,那么T就会是最小生成树了,要么U和T就是一样的,要么U和T不一样,但都是最小生成树,也就是图中包含有权值一样的边,导致了最小生成树的不唯一性。首先先确定出U和T中不一样的边,再将这些边一条一条替换掉,同时保持权值的不变。也就是替换和被替换的边的权值应该是一样的。)

每一步转换需要将T中的一条边e加到U中,并从U删除一条边f。边e和f按下列方法选择:

(1)设e是在T中、不在U中的代价最小的边。由于k>0,这样的边一定存在。

(2)e加入U后将形成惟一的环路。设f是该环路中不在T的边。由于T中无环路,此环路一定存在一条不在T中的边。

(这样可以确保你加入的是U中没有的边,而删除的是T中没有的边。那么问题就可以转化为为什么加入之后就会形成环路。我们可以考虑只有一条边不同的情况。由于生成树包含了所有的顶点,所以不同的这对边中包含着相同的顶点。当加入e之后,原来U中其余顶点(不包含相同的那个顶点)到相同顶点肯定是连通的,而加入的那条边的一端是相同的那个顶点,别一端是U中的其余顶点,这样两个连通的部分就会形成环路。)

按照e和f的选择方法,V=U+{e}-{f}是一棵生成树,且T有k-1条边不在V中。下面需要证明代价(V)=代价(U)。显然,代价(V)=代价(U)+代价(e)-代价(f)。代价(e)不会小于代价(f),否则生成树V的代价比U的还小,而这是不可能的。假设代价(e)>代价(f),则克鲁斯卡尔算法在e之前考察了f。由于f不在T中,算法在考察时一定放弃了f。因此,f与T中代价小于等于代价(f)的边一定形成了环路。由于e是T中而不是在U中的、代价最小的边,T中代价小于等于代价(f)的边都在U中,因而U中存在环路。但U是生成树,不可能有环路。可见,假设代价(e)>代价(f)导致矛盾。于是,惟一的可能就是代价(e)=代价(f)。因此,代价(V)=代价(U)。

(这一段话就是用来证明e的代价和f的代价肯定是一样的,如果不一样的话,会导致不可能与矛盾。如果小于的话,那就意味着原来假设的U是最小生成树不成立,这是不可能的。如果大于的话。就意思着使用Kruskal算法中f被放弃了,而f代价比e来得小,放弃的理由只可能是形成环路了,所以被放弃了。而配合f形成环路的所有边,权值肯定要比f来得小,因为Kruskal是从小到大找权值的,而e又是T中有,U中没有的权值最小的边,所以与f可以形成环路的边是T与U共有的边,所以f在U中也理应形成环路。但U假设时就是最小生成树,一棵生成树是不可能有环路的,产生了矛盾。所以e的权值只可能是与f相同才可以。这样的转换的k个步骤中,每一步都可以保持U的权值不变,而且U还可以转换为T,这样T的权值就会与U一样的,所以T也就是最小生成树,这样(b)就得到了证明。)

未经允许不得转载:TacuLee » Kruskal证明

赞 (0)

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址