资源描述：
《定义7.5设图G的顶点非空真子集为V1V, 在G中一个端.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。
1、定义7.5:设图G的顶点非空真子集为V1V,在G中一个端点在V1中,另一端点在V(G)-V1中的所有边组成的集合称为G的一个断集或称边割,记为E(V1(V(G)-V1)),简记为(V1,V(G)-V1)。当
2、(V1,V(G)-V1)
3、=1时,(V1,V(G)-V1)中的那条边称为割边或桥。图7.2(b)中边集{e1,e2}和{e1,e2,e3,e4}都是断集(边割)。割集是断集,反之不一定。对于连通图G(V,E),删去一个割集D,得到两个分支,顶点集分别为V1和V(G)-V1,割集D是G中一个端点在V1中,另一端点在V(G)-V1中的边的全体。如
4、果在连通图G中,删去一个断集而不是一个割集,那么将得到多于两个分支。三、割集与回路定理7.4：任何一条回路和任何生成树的余树至少有一条公共边。证明：如果一条回路和一棵生成树的余树没有公共边,则这回路含在该生成树中,这是不可能的。定理7.5：任何一个割集和任何生成树至少有一条公共边。证明：如果一个割集和一棵生成树没有公共边,则删去该割集后留下一棵完整的生成树,也就是说,删去一个割集后,不能将图G分为两个分支,这与割集的定义相矛盾。定理7.6：任何一个回路和任何一个割集有偶数条公共边。证明：从连通图G中删去一个割集D后,得到两个顶点子集V1和V2,考察G
5、中任一条回路C:(1)如果C中所有顶点在V1(或V2)中,则C与D没有公共边。(2)如果C中顶点既有一些在V1中,又有一些在V2中,先看D中任何一边,它的一个端点在V1中,另一个端点在V2中,且G中除D中边以外,不再有任何边连接V1与V2中的顶点。定义7.6：设连通图G中给定生成树T,对于只包含T中一条枝的割集,称此割集为关于T的基本割集。在连通图G中,对于给定的生成树T,每一枝恰对应唯一的一个基本割集。因为从生成树T中删去一条枝,将T分为两棵树,它将G的顶点集V划分为V1和V-V1,在G中这两个顶点集之间的连边,便对应这一枝的唯一的基本割集。设连通
6、图G有e条边,n个顶点,给定的生成树T应有n-1条枝,所以恰有n-1个基本割集,这些基本割集的全体称为生成树T基本割集组。定义7.7:设连通图G中给定生成树T,在T中加一条弦,恰产生一条回路,称此回路为关于T的基本回路。由定理7.1的等价定义(4),可知在T中加一弦,产生唯一的回路。设连通图G有e条边,n个顶点,给定的生成树应有n-1条枝,e-n+1条弦,所以恰有e-n+1条基本回路,这些基本回路的全体称为生成树T的基本回路组。例如图(a)中给定T={e1,e4,e5,e6},关于T的基本割集组:{e1,e2,e8},{e4,e3,e2,e8},{e
7、5,e3,e2,e7},{e6,e7}基本回路组:{e2,e1,e4,e5},{e3,e4,e5},{e7,e5,e6},{e8,e1,e4,}7.3最小生成树定义7.10:设G(V,E,w)是带权连通简单图,w是从E到实数集的函数。又设T是G的一棵生成树,T中所有枝的权之和称为T的权,记为W(T)。具有权minTW(T)的生成树称为最小生成树。这个问题是具有实际意义的。例如G的顶点表示城市,G的边表示城市间的道路,边的权表示对应道路的长度,现在沿着道路架设通讯线路,将这些城市联系起来,要求架设的线路最短,这个问题就是求一棵最小生成树的问题克鲁斯科尔
8、算法的步骤,通俗地说,就是先将G中的边按权从小到大顺序排列,再从小到大依次取出每一边作检查。一开始取权最小的边{v1,v6}为e1,且w(e1)=l,由e1导出一个部分子图,然后依次每取一边加入已得部分子图。若保持无回路,将该边与原有部分子图中边导出一个新的部分子图;若得到回路,将该边放弃。上述过程继续进行,直到所有边均检查完,得到的部分子图就是所求的一棵最小生成树,如图(b)所示,这里e1={v1,v6}和e2={v7,v2}取出后,取e3为{v2,v3},;若改取e3为{v3,v7},可得到另一棵最小生成树求最小生成树的克鲁斯科尔(Kruska
9、l)算法克鲁斯科尔算法:设G(V,E,w)是有n个顶点的带权连通简单图。(1)选取G的一边e1,使w(e1)最小,令E1={e1},1i。(2)若已选Ei={e1,e2,,ei},那么从E-Ei中选取一边ei+1,满足:1)Ei∪{ei+1}的导出子图中不含有回路;同时2)w(ei+1)为满足1)E-Ei中的最小;3)若ei+1存在,则令Ei+1=Ei∪{ei+1},i+1i,转(2);若ei+1不存在,则停,此时Ei导出的子图就是所求的最小生成树,记为T。定理7.8:克鲁斯科尔算法所得到的图T是最小生成树。证明:首先由定理7.1等价定义(4)
10、(T是无回路图,且在T的任两个不相邻的顶点之间添加一边,恰得到一条回路)知T是G的一棵子树。并由等价定义(2
