所谓破环法(破圈法)是指对 于一个每一条环上权值均不相同的无向连通图若图中有环则删掉环上权重最大的边。如果由此得到的新图仍然有环再删掉环上权值最大的边如此不断进行下去直到图中无环为止此时的图即为原图的最小生成树PS:该破圈法来自于2020年王道数据结构考研单科书p223,书上证明太简略实在看不懂于是自己思考了一下证明方法给出如下证明定理一每一条环上权值均不相同的无向连通图G的任意环上权值最大的边一定不在它的最小生成树中证明假如某一环R上权值最大的边E在G的最小生成树T中,在T中去掉E得到两个连通分支T1,T2,E的两端分别位于T1,T2中我们断言环R上从E的一个端点出发不经过E抵达E的另一个端点的路径L上一定存在这样一条边E’,E’的两个端点分别位于T1,T2中假如不是这样L上与E的一端关联的边(u1,u2)(u1与E的一端关联,且设u1位于T1,T2中的某个连通分支T’‘中)的两个端点u1,u2均位于T1T2中相同的连通分支T’‘中(如若不然由于u1位于T’‘中所以u2位于{T1,T2}-T’‘中,即u1和u2分别位于T1,T2或T2,T1中,这和之前反证法假设L上没有两个端点分别位于T1,T2的边矛盾),同理L上与u2关联的边(u2,u3)的两个端点v2,u3均位于T1T2中相同的连通分支T’‘中,(u3,u4)也是如此以此类推知L上与E的端点u1相对的E的另一端点um关联的边(um-1,um)的两个端点um-1,um均位于T1,T2中相同的连通分支T’‘中故u1,um均位于T1,T2中相同的连通分支T’中,这和E的两个端点分别位于T1,T2中矛盾。注意E’在R上,E为R上权值最大的边且R上边权值两两不等故E’权值小于E的权值在T中掉E后加入E’E’将T1T2两个连通分支连接起来得到生成树T’ T-EE’ ,T’的权值小于T的权值这和T为最小生成树矛盾证毕定理二在破圈法中如果删除无向连通图G中某一环R上某一边E前G是连通的那么删除E后得到的新图G’仍然是连通的证明对G中任意两个不同的顶点h,k(hk)如果h到k的某一路径p上不包含R上的边E那么在R中删除E后h,k仍有路径p相连故是连通的。否则设Rv1v2—vn,E(vi,vi1)1In-1或(vn,v1),则删除后有h到k的道路p1-(vi,vi-1,vi-2,—,v1,vn,vn-1,—,vi2,vi1)Or(vn,vn-1,vn-2,—,v2,v1)-p2 故h,k之间仍然连通,其中p1是路径p在顶点vi或vn之前的部分(包括vi或vn),p2是路径p在顶点vi1或v1之后的部分(包括vi1或v1)证毕定理三在破圈法中删除每一条环上权值均不相同的无向连通图G中某一环R上权值最大的边E前G的最小生成树和删除后得到的新图G’的最小生成树相同证明由定理二,G’连通故必然存在最小生成树,再由定理一对G的任意最小生成树T,E不在T中,但T是G的极小连通子图所以T同样是G’G-E的极小连通子图即生成树T必然是G’的最小生成树如若不然设G’的最小生成树为T’,由于T’为G’的极小连通子图,G’为G的子图故T’是G的极小连通子图即生成树从而T’的权值应当大于等于T的权值但由假设T不是G’的最小生成树故T的权值一定大于G’的最小生成树T’的权值这是一个矛盾故T必然是G’的最小生成树同样G’的最小生成树必然是G的最小生成树因为G’是G的子图故G’的任意最小生成树T’一定是G的生成树假若T’不是G的最小生成树,设G的最小生成树为T’‘,则T’的权值大于T’‘,但由上述证明知T’‘是G’的最小生成树故应有T’‘权值等于T’矛盾故G’的最小生成树都是G的最小生成树证毕定理四在破圈法中每一条环上权值均不相同的无向连通图G的任意环R中权值最大的边E必然会删去证明假设存在G某环R上权值最大的边E在破圈法中自始至终都不会被删去由于破圈法运行结束时没有环所以R上必然有不为E的若干边被先后删去设这些边按删除时间从早到晚排序为e1,e2,—,en。删除e1时e1必然在不为R的另一环R1中且e1是R1中权值最大的边显然E不在R1中否则因E的权值大于e1,这样e1不是R1中权值最大的边矛盾。设R1与R公共边的集合为S,这里e1属于S,E不属于S。于是我们从E的两个端点沿环R沿彼此相反方向延伸沿每一个方向延伸的过程中抵达S中某条边的端点时停止延伸记每一个方向停止延伸时抵达的端点分别为l和r.E在R上l到r不包含S中边的路径pl上,e1在R上l到r包含S中的边的路径pr上。设pr上包含e1,e2,—,en中的边em1,em2,—,emq, pl和pr将R1分为两部分其中有且仅有一部分包含边e1,记不包含e1的部分为路径p.我们将p和pl组合得到新环R1’,R1’上不包含e1但包含E,E的权值大于pl上其他任意边的权值,E的权值大于e1,e1的权值大于p上任意边的权值故E的权值大于R1’上除E外任意边的权值考察新环R1’,如果R1’上的E最终会被删去则定理证毕否则注意上文的p可能包含了em1,em2,—,emq中的某些边ek1,ek2,—,eks,且边{e1,e2,—,en}-{em1,em2,—,emq} {el1,el2,—,eln-q}在pl上,故在R1’上。ek1,ek2,—,eks和el1,el2,—,eln-q会在R1’上按某种次序被先后删除,但对于R1’来说可能还有其它会在e1被删除后被删除的边ej1,ej2,—,ejh,把ek1,ek2,—,eks, el1,el2,—,eln-q和ej1,ej2,—,ejh按删除的先后次序从早到晚排列起来得到删除序列eq1,eq2,—,eq(sn-qh),显然它们均不为E,然后考察R1’上对eq1删除该过程可以重复以上对R中删除e1的讨论最后可知删除eq1后我们将得到新环R2’E在R2’上且E的权值大于R2’上任意边的权值,如果R2’上的E最终会被删去则定理证毕否则对R2’再重复上述讨论又得到新环R3’—以此类推。由于G中的边数目是有限的所以这一讨论不可能无限进行下去于是就可以断言如果E始终未被删除则当边的删除操作停止也就是破圈法结束时E必然在删除结束后所得的结果图G’的环Rs’中且E是Rs’中权值最大的边这和删除操作结束后G’不存在环矛盾这就证明了任意环上权值最大的边在破圈法中必然会被删去定理五 破圈法运行结束后所得的最终图T一定为生成树且必然为执行算法前原图G的最小生成树证法一绕开定理 三由 定理二T是连通的显然T无环且边数为G的定点数减一故T为生成树如若T不是G的最小生成树设G的最小生成树为T’,T一定有边E不在T’中将边E加入T’中于是T’中出现环R’且E在R’上由定理四E一定不是R’上权值最大的边E’(否则E会被删去不会出现在T中)E’在T’中于是从T’中去除E’并加入E得到生成树T’‘,T’‘的权值小于T’,这和T’是G的最小生成树矛盾,故T是G的最小生成树证法二由证法一证明前半部分和定理三立即得到推论如果无向连通图G的每一条边的权值都不相同那么G的最小生成树唯一证明设G的顶点数为n,若G的边数为n-1,则G本身就是它的最小生成树若G的边数大于n-1,则G中必有环又因为G的每一条边的权值均不相同故G每一条环上权值均不相同由定理三和定理五最终图T就是G的全部最小生成树即G的唯一最小生成树证毕以上是全部证明如有错误欢迎在评论区指出