集合论与图论第七章优秀PPT.ppt

《集合论与图论第七章优秀PPT.ppt》由会员分享，可在线阅读，更多相关《集合论与图论第七章优秀PPT.ppt（45页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、集合论与图论第七章第一页，本课件共有45页17.1 7.1 树及其性质树及其性质仅有一个顶点的树称为平凡树。仅有一个顶点的树称为平凡树。定义定义7.1.1 7.1.1 连通且无圈的无向图称为无向树连通且无圈的无向图称为无向树,简称树。简称树。一个没有圈的不连通的无向图称为无一个没有圈的不连通的无向图称为无向森林向森林,简称森林简称森林;第二页，本课件共有45页2 定理定理7.1.1 7.1.1 设设G=(V,E)G=(V,E)是一个是一个(p,q)(p,q)图图,则下列各命则下列各命题等价题等价:(1)G(1)G是树是树 (2)G (2)G的任意两个不同顶点间有唯一的一条路联结的任意两个不同顶

2、点间有唯一的一条路联结;(3)G(3)G是连通的且是连通的且p=q+1;p=q+1;(4)G(4)G中无圈且中无圈且p=q+1;p=q+1;(5)G(5)G中无圈且中无圈且G G中任意两个不邻接的顶点间加一条边中任意两个不邻接的顶点间加一条边,则得到一个有唯一的一个圈的图则得到一个有唯一的一个圈的图;(6)G(6)G是连通的是连通的,并且若并且若p3,p3,则则G G不是不是K Kp p,G,G中任意两中任意两个不邻接的顶点间加一条边个不邻接的顶点间加一条边,则得到一个有唯一的一个圈的则得到一个有唯一的一个圈的图。图。7.1 7.1 树及其性质树及其性质第三页，本课件共有45页3 推论推论7.

3、1.1 7.1.1 任一非平凡树中至少有任一非平凡树中至少有两个度为两个度为1 1的顶点。的顶点。7.1 7.1 树及其性质树及其性质 定义定义7.1.2 7.1.2 连通图连通图G G称为是极小连通图称为是极小连通图,如果去掉如果去掉G G的任意一条边后得到的都是不连通的任意一条边后得到的都是不连通图。图。极小连通图极小连通图 推论推论7.1.2 7.1.2 图图G G是树当且仅当是树当且仅当G G是极小是极小连通图。连通图。第四页，本课件共有45页4定义定义7.1.3 7.1.3 设设G=(V,E)G=(V,E)是连通图是连通图,v,v V,V,数数称为称为v v在在G G中的偏心率中的偏

4、心率,v v v v点的偏心率是点的偏心率是3,3,顶点顶点v v的偏心率的偏心率7.1 7.1 树及其性质树及其性质连通图连通图G G的半径的半径 称为称为G G的半径的半径,满足满足r(G)=e(v)r(G)=e(v)的顶点的顶点v v称为称为G G的中心点的中心点,G,G的所有中心点组成的集合称为的所有中心点组成的集合称为G G的中心的中心,G,G的中心记为的中心记为C(G)C(G)第五页，本课件共有45页5 定理定理7.1.2 7.1.2 每棵树的中心或含有一个顶点每棵树的中心或含有一个顶点,或含或含有两个邻接的顶点有两个邻接的顶点 v4 v4 v5 v5 v3 v3 v2 v2 v1

5、 v1离中心最远的点满足什么性质离中心最远的点满足什么性质?都是一度顶点都是一度顶点;v4 v4 v3 v3 v2 v2 如果把如果把1 1度顶点都去掉，会不会引起中心点的变化？度顶点都去掉，会不会引起中心点的变化？不会引起中心点的变化。不会引起中心点的变化。7.1 7.1 树及其性质树及其性质图图1 1图图2 2图图3 3 v5 v5 v6 v6 v4 v4 v3 v3 v2 v2 v1 v1第六页，本课件共有45页6 定理定理7.1.2 7.1.2 每棵树的中心或含有一个顶点每棵树的中心或含有一个顶点,或或含有两个邻接的顶点。含有两个邻接的顶点。证证 显然显然,一个顶点的树有一个中心一个顶

6、点的树有一个中心,两个顶点的两个顶点的树有两个中心树有两个中心,这时定理成立这时定理成立;设设v v是中心是中心,则则v v只有到达一个一度顶点时只有到达一个一度顶点时,其其偏心率才能达到最大值。偏心率才能达到最大值。把所有的一度顶点全去掉，则其中心的偏心把所有的一度顶点全去掉，则其中心的偏心率都少率都少1 1。每次把所有的一度顶点全去掉，并不引起每次把所有的一度顶点全去掉，并不引起中心的变化。中心的变化。每次把所有的一度顶点全去掉每次把所有的一度顶点全去掉,经有限步必可得经有限步必可得到一个只有一个顶点的树到一个只有一个顶点的树,或只有两个顶点的树。或只有两个顶点的树。7.1 7.1 树及其

7、性质树及其性质第七页，本课件共有45页7 例例7.1.1 7.1.1 任何一个非平凡的树都可用两种颜色给任何一个非平凡的树都可用两种颜色给其顶点染色其顶点染色,使得每条边的两个端点不同色。使得每条边的两个端点不同色。由第六章第由第六章第4 4节中偶图的充分必要条件是图中节中偶图的充分必要条件是图中所有圈都是偶数长可得树是偶图。所有圈都是偶数长可得树是偶图。因此树可用两种颜色染色，并且每条边的两个端因此树可用两种颜色染色，并且每条边的两个端点不同色。点不同色。7.1 7.1 树及其性质树及其性质第八页，本课件共有45页87.2 7.2 生成树生成树 1 1、若图、若图G G有生成树有生成树,则则

8、G G是连通的是连通的,所以不连通所以不连通图没有生成树图没有生成树,定义定义7.2.1 7.2.1 设设G=(V,E)G=(V,E)是一个图是一个图,G,G的一个生的一个生成子图成子图T=(V,F)T=(V,F)如果是树如果是树,则称则称T T是是G G的生成树。的生成树。2 2、连通图都有生成树吗、连通图都有生成树吗?定理定理7.2.1 7.2.1 图图G G有生成树的充分必要条件是有生成树的充分必要条件是G G为为一个连通图。一个连通图。第九页，本课件共有45页9 推论推论7.2.1 7.2.1 设设G G是一个是一个(p,q)(p,q)连通连通图图,则则q qp-1p-1。定义定义7.

9、2.2 7.2.2 设设G G是一个图是一个图,若若G G的的生成子图生成子图F F是一个森林是一个森林,则则F F称为称为G G的一的一个生成森林。个生成森林。任意图都有生成森林。任意图都有生成森林。7.2 7.2 生成树生成树第十页，本课件共有45页10 定理定理7.2.2 7.2.2 具有具有p p个顶点的完全图个顶点的完全图K Kp p有有p pp-2p-2棵生成树棵生成树,p2.,p2.证证 设设K Kp p的顶点集的顶点集V=1,2,.,p,V=1,2,.,p,定理中的数定理中的数p pp-2p-2恰好是以恰好是以V V中数为项的长为中数为项的长为p-p-2 2的所有序列的个数的所

10、有序列的个数,要证明该定理要证明该定理,只须在只须在K Kp p的所有生成树之集与的所有生成树之集与这些长为这些长为p-2p-2的序列之集间建立一个一一对应即可。的序列之集间建立一个一一对应即可。7.2 7.2 生成树生成树第十一页，本课件共有45页1112534 设一棵树的顶点集为设一棵树的顶点集为A A 1 1、从中找到编号最小的叶、从中找到编号最小的叶子结点，去掉该叶子结点子结点，去掉该叶子结点a a1 1及其及其邻接边邻接边(a(a1 1,b,b1 1)。2 2、重复以上过程。只到剩、重复以上过程。只到剩一条边为止。一条边为止。(1,2),(4,3),(3,2)(1,2),(4,3),

11、(3,2)这棵树对应序列（这棵树对应序列（2 2，3 3，2 2）一个棵对应序列一个棵对应序列B=bB=b1 1b b2 2b b3 3bbp-2p-2而且是唯一的而且是唯一的 定理定理7.2.2 7.2.2 具有具有p p个顶点的完全图个顶点的完全图K Kp p有有p pp-2p-2棵棵生成树生成树,p2.,p2.7.2 7.2 生成树生成树第十二页，本课件共有45页1212534 树的顶点集合为树的顶点集合为12345 12345 这棵树对应序列（这棵树对应序列（2 2，3 3，2 2）任给一个序列任给一个序列BbBb1 1,b,b2 2,b,b3 3,b,bp-2p-2 1 1、从、从A

12、 A找到最小的不属于找到最小的不属于B B的元素的元素,设为设为a a1 1,与与b b1 1连接，连接，从从A A中去掉中去掉a a1 1，从，从B B中去掉中去掉b b1 1.2 2、重复以上过程只到、重复以上过程只到B B为空，为空，A A中剩余两个中剩余两个 3 3、连接剩余的两个顶点。、连接剩余的两个顶点。7.2 7.2 生成树生成树第十三页，本课件共有45页13 定理定理7.2.3 7.2.3 设设G=(V,E)G=(V,E)是连通图是连通图,T,T1 1=(V,E=(V,E1 1)和和T T2 2=(V,E=(V,E2 2)是是G G的两个不同的生成树的两个不同的生成树,如果如果

13、e e1 1 E E1 1EE2 2,则则 e e2 2 E E2 2EE1 1,使得使得(T(T1 1-e-e1 1)+e)+e2 2为为G G的一棵生成树。的一棵生成树。7.2 7.2 生成树生成树 证证 所以所以(T(T1 1-e-e1 1)+e)+e2 2是是G G的生成树。的生成树。由于由于T T2 2是连通的，所以必然在是连通的，所以必然在V V1 1与与V V2 2之间存之间存在在T T2 2的一条边的一条边e e2 2，因为因为V V1 1与与V V2 2之间在之间在T T1 1中只有一条边中只有一条边e e1 1，所以，所以e e2 2 E E1 1,由树的性质由树的性质,T

14、,T1 1-e-e1 1恰有两个支恰有两个支,设这两支分别为设这两支分别为G G1 1=(V=(V1 1,F,F1 1),G),G2 2=(V=(V2 2,F,F2 2)因为因为e e1 1 E E2 2,所以所以e e2 2ee1 1第十四页，本课件共有45页14 定义定义7.2.3 7.2.3 设设T T1 1,T,T2 2是是G G的生成树的生成树,是是T T1 1的边但的边但不是不是T T2 2的边的条数的边的条数k k称为称为T T1 1与与T T2 2的距离的距离,记为记为d(Td(T1 1,T,T2 2)=k)=k。由定义可知由定义可知d(Td(T1 1,T,T2 2)0,)0,

15、G G的生成树之间的距离的生成树之间的距离并且并且d(Td(T2 2,T,T1 1)=d(T)=d(T1 1,T,T2 2)设设T T1 1的边集为的边集为E E1 1,T,T2 2的边集为的边集为E E2 2,用集合怎么用集合怎么表示两个生成树之间的距离表示两个生成树之间的距离?E E1 1EE2 2 7.2 7.2 生成树生成树第十五页，本课件共有45页15d(Td(T1 1,T,T2 2)d(T)d(T1 1,T,T3 3)+d(T)+d(T3 3,T,T2 2)是是T T1 1的边的边但不是但不是T T2 2的边包括在的边包括在如下情况中如下情况中,是是T T1 1的边不的边不是是T

16、T2 2的边是的边是T T3 3的边的边,是是T T1 1的边不的边不是是T T2 2的边也的边也不是不是T T3 3的边的边,7.2 7.2 生成树生成树第十六页，本课件共有45页16两个生成树之间的基本树变换两个生成树之间的基本树变换若若d(Td(T1 1,T,T2 2)=1,)=1,T T2 2=(T=(T1 1-e-e1 1)+e)+e2 2它称为从它称为从T T1 1到到T T2 2的一个基本树变换。的一个基本树变换。则则T T1 1中有一条边中有一条边e e1 1不在不在T T2 2中中,T,T2 2中也有一条边中也有一条边不在不在T T1 1中中,7.2 7.2 生成树生成树第十

17、七页，本课件共有45页17 定理定理7.2.4 7.2.4 设设T T0 0和和T T是是G G的两距离为的两距离为k k的生成的生成树树,则从则从T T0 0开始经开始经k k次基本树变换便可得到次基本树变换便可得到T T。当当k=0k=0成立成立;证证 假设假设k kn n时结论成立时结论成立,需证需证k=n+1k=n+1时定理成立时定理成立,设设d(Td(T0 0,T)=n+1,T)=n+1,当当k=1k=1时，由定理时，由定理7.2.37.2.3知结论成立。知结论成立。由定理由定理7.2.3,7.2.3,从从T T0 0中去掉一条不在中去掉一条不在T T中边中边e e1 1后后,必在必

18、在T T中找到一条不在中找到一条不在T T0 0中边中边e e2 27.2 7.2 生成树生成树第十八页，本课件共有45页18d(Td(T1 1,T)=n,T)=n,由假设知由假设知d(Td(T0 0,T)=n+1,T)=n+1,由归纳假设由归纳假设,从从T T1 1经经n n个基本树变换便到个基本树变换便到T,T,因此从因此从T T0 0经经n+1n+1个基本树变换得到个基本树变换得到T T因此定理成立。因此定理成立。使得使得(T(T0 0-e-e1 1)+e)+e2 2为生成树为生成树,设设(T(T0 0-e-e1 1)+e)+e2 2=T=T1 1,7.2 7.2 生成树生成树第十九页，

19、本课件共有45页19最小生成树问题最小生成树问题生成树的权生成树的权 图图G G1 12 23 31 12 23 3 T T1 12 23 31 12 23 37.2 7.2 生成树生成树 给定边带权连通图给定边带权连通图G,GG,G中边的权是一个非负中边的权是一个非负实数实数,生成树中各边的权之和称为该生成树的权；生成树中各边的权之和称为该生成树的权；G G的生成树中权最小的那个生成树就是最的生成树中权最小的那个生成树就是最小生成树。小生成树。图图G G的生成树的生成树T T的权是的权是6 6第二十页，本课件共有45页20 如果边的权代表路程，最小生成树就是原如果边的权代表路程，最小生成树就

20、是原图中路程最短的连通图。图中路程最短的连通图。如果边的权代表修路资金，最小生成树如果边的权代表修路资金，最小生成树就是原图中花费资金最少的连通图。就是原图中花费资金最少的连通图。1 1、最小生成树不一定只有一个；、最小生成树不一定只有一个；2 2、最小生成树按边的权的性质不同可以有不、最小生成树按边的权的性质不同可以有不同的理解；同的理解；7.2 7.2 生成树生成树第二十一页，本课件共有45页21 定义定义7.2.4 7.2.4 设设T T是连通图是连通图G G的生成树的生成树,G,G中不是中不是T T的边称为的边称为T T的弦。的弦。若若G G是一个是一个(p,q)(p,q)连通图连通图

21、,T,T是是G G的生成树的生成树,问问T T有多少条弦有多少条弦?T T有有p-1p-1条边条边,有有q-p+1q-p+1条弦条弦,生成树生成树T T的弦的弦生成树生成树T T的基本圈的基本圈,如果如果e e是是T T的一条弦的一条弦,则则T+eT+e中有唯一的一个圈中有唯一的一个圈,这个圈称为这个圈称为G G的相对生成树的相对生成树T T的基本圈的基本圈,在这个圈上只有在这个圈上只有e e是是T T的弦的弦,其它都是其它都是T T的边的边,7.2 7.2 生成树生成树第二十二页，本课件共有45页22 设设G=(V,E,w)G=(V,E,w)是一个边带权图是一个边带权图,其中对每条其中对每条

22、边边x x E,w(x)0,E,w(x)0,如果如果T T0 0是是G G的一个最小生成树的一个最小生成树,e,e是是T T0 0的一条的一条弦弦,则则T T0 0+e+e中有唯一的一个圈中有唯一的一个圈C,C,C C上的每条边上的每条边x x有有w(x)w(e)w(x)w(e)G G1 12 24 43 33 3w(e)w(e)如果有一条边如果有一条边x,x,w(x)w(e)w(x)w(e)从圈中去掉边从圈中去掉边x,x,加入边加入边e e则得到一个比则得到一个比T T0 0更小的生成树。更小的生成树。G G1 12 24 43 33 3w(e)w(e)7.2 7.2 生成树生成树第二十三页

23、，本课件共有45页23 定理定理7.2.5 7.2.5 设设G=(V,E,w)G=(V,E,w)是一个连通的边带权是一个连通的边带权图图,边上的权函数边上的权函数w w是非负是非负,(V (V1 1,E,E1 1),(V),(V2 2,E,E2 2),.,(V),.,(Vk k,E,Ek k)是是G G的生成森林的生成森林,k1,F=,k1,F=,如果如果e=uve=uv是是EFEF中权值最小的边且中权值最小的边且u u V V1 1,v,v V V1 1中中,则存在则存在G G的一个包含的一个包含F Fee的生成树的生成树T,T,使得使得T T的权不大于任一包含的权不大于任一包含F F的生成

24、树的权。的生成树的权。7.2 7.2 生成树生成树第二十四页，本课件共有45页24 生成树生成树T T1 12 23 33 34 44 4u uv ve e 图图G G1 12 23 33 34 44 4u uv ve e 生成树生成树T T的权是包含生成森林的生成树中的权是包含生成森林的生成树中权最小的生成树。权最小的生成树。7.2 7.2 生成树生成树第二十五页，本课件共有45页25 证证 用反证法证明用反证法证明 把把e e加到加到T T 中中,则则T T+e+e中有唯一的圈中有唯一的圈C C使得使得C C上上除了边除了边e e外外,必还有边必还有边e e=u=u v v,u,uV V1

25、 1,v,vV V1 1,根据根据e e的假设必有的假设必有w(e)w(ew(e)w(e),),从从T T+e+e中去掉中去掉e e,得到一生成树得到一生成树T,TT,T包含了包含了F Fe,e,并且并且T T的权不大于的权不大于T T 的权的权,这与关于这与关于T T 的假定相矛盾的假定相矛盾;如若不然如若不然,则则G G有一个生成树有一个生成树T T=(V,E=(V,E),T),T 包含包含F F(即即F F E E),),不包含边不包含边e e；T T 的权小于任一包含的权小于任一包含F Fee的生成树的权的生成树的权,因此定理成立。因此定理成立。7.2 7.2 生成树生成树第二十六页，

26、本课件共有45页26最小生成树最小生成树KruskalKruskal算法算法14530265157356421453027.2 7.2 生成树生成树第二十七页，本课件共有45页277.2 7.2 生成树生成树输入输入:连通图连通图G=(V,E),G=(V,E),其中其中V=1,2,n,V=1,2,n,输出输出:一颗最小生成树一颗最小生成树:算法算法:void Kruskal(V,T)void Kruskal(V,T)T=V;T=V;ncomp=n;/ncomp=n;/连通分支连通分支 while(ncomp1)while(ncomp1)从从E E中取出删除权最小的边中取出删除权最小的边(v,u

27、);(v,u);if(v if(v和和u u属于属于T T中不同的连通分支中不同的连通分支)T=T T=T(v,u);ncomp-;第二十八页，本课件共有45页28 定理定理7.2.6 7.2.6 设设G=(V,E,w)G=(V,E,w)是一个边带权连通图是一个边带权连通图,U,U是是V V的一个真子集的一个真子集,如果如果u,vu,v是是u u U,vU,v VUVU的的G G的一的一条边条边,并且是所有的这样的边中并且是所有的这样的边中,u,v,u,v的权的权w(u,v)w(u,v)最最小小,则则G G中一定存在一个最小生成树中一定存在一个最小生成树,它以它以u,vu,v为其中为其中一条边

28、一条边。7.2 7.2 生成树生成树abcdefg1818191520820931516U UVUVU第二十九页，本课件共有45页29 证证 用反证法用反证法于是于是,T,T 是含边是含边u,vu,v的最小生成树的最小生成树;在圈上有一条边在圈上有一条边uu,v,v,使得使得u uU U,v,vVU;VU;假如假如G G的最小生成树都不含边的最小生成树都不含边u,v;u,v;令令T T=(T+uv)-=(T+uv)-u u v v,由于由于w(u,v)w(w(u,v)w(u u,v,v),所以所以T T 的权的权T T的权的权;这与假设相矛盾。这与假设相矛盾。把边把边u,vu,v加到加到G G

29、的一棵最小生成树的一棵最小生成树T T中中,那么那么T+uvT+uv中有一个含边中有一个含边uvuv的圈的圈;7.2 7.2 生成树生成树第三十页，本课件共有45页30PrimPrim算法的基本思想是算法的基本思想是:1 1、先置、先置U=iU=i1 1,E=,E=,选取满足选取满足i i2 2 VUVU的边的边ii1 1,i,i2 2 使使w(iw(i1 1,i,i2 2)最小最小;直到把所有的顶点都加入到直到把所有的顶点都加入到U U中中,所得到的边所得到的边集就构成一棵最小生成树。集就构成一棵最小生成树。设设G=(V,E,w)G=(V,E,w)是带权连通图是带权连通图,V=1,2,.,p

30、,V=1,2,.,p 2 2、置、置U=iU=i1 1,i,i2 2,E=i,E=i1 1i i2 2,选取满足选取满足i i U,iU,i3 3 VUVU的边的边i,ii,i3 3,使使w(i,iw(i,i3 3)最小最小;3 3、置、置U=iU=i1 1,i,i2 2,i,i3 3,E=i,E=i1 1i i2 2,ii,ii3 3,继续这样的过继续这样的过程程;7.2 7.2 生成树生成树*第三十一页，本课件共有45页317.3 7.3 割点、桥和割集割点、桥和割集 定义定义7.3.1 7.3.1 设设v v是图是图G G的一个顶点，如果的一个顶点，如果G-vG-v的支的支数大于数大于G

31、 G的支数，则称顶点的支数，则称顶点v v为图为图G G的一个割点。的一个割点。上图中上图中v v5 5是割点，其它都不是割点。是割点，其它都不是割点。1 1、割点、割点 v v1 1 v v6 6 v v7 7 v v4 4 v v2 2 v v5 5 v v3 3 v v8 8 v v9 9 v v1 1 v v6 6 v v7 7 v v4 4 v v2 2 v v3 3 v v8 8 v v9 9第三十二页，本课件共有45页32 定义定义7.3.2 7.3.2 图图G G的一条边的一条边x x称为称为G G的一座桥，的一座桥，如果如果G-xG-x的支数大于的支数大于G G的支数。的支数

32、。图中边图中边v v2 2v v5 5是桥；是桥；2 2、桥、桥 v1 v1 v6v6 v4 v4 v2 v2 v5v5 v7v7 v3 v3 图中边图中边v v5 5v v6 6,v,v5 5v v7 7也是桥。也是桥。7.3 7.3 割点、桥和割集割点、桥和割集第三十三页，本课件共有45页33 定理定理7.3.1 7.3.1 设设v v是连通图是连通图G=(V,E)G=(V,E)的一个顶的一个顶点，则下列命题等价：点，则下列命题等价：(1)v (1)v是图是图G G的一个割点的一个割点;(2)(2)存在与存在与v v不同的两个顶点不同的两个顶点u u和和w,w,使得使得v v在在每一条每一

33、条u u与与w w间的路上间的路上;(3)(3)集合集合VvVv有一个二划分有一个二划分U,WU,W使得使得 u u U,wU,w W,vW,v在联结在联结u u和和w w的每条路上。的每条路上。7.3 7.3 割点、桥和割集割点、桥和割集第三十四页，本课件共有45页34 定理定理7.3.2 7.3.2 每个非平凡的连通图至少有每个非平凡的连通图至少有两个顶点不是割点两个顶点不是割点。证证 非平凡图的连通图必有生成树非平凡图的连通图必有生成树,非平凡树至少有两个度为非平凡树至少有两个度为1 1的顶点的顶点,它们它们就是原图的非割点就是原图的非割点。7.3 7.3 割点、桥和割集割点、桥和割集第

34、三十五页，本课件共有45页35 定理定理7.3.3 7.3.3 设设x x是连通图是连通图G=(V,E)G=(V,E)的一条边的一条边,则下列命题等价则下列命题等价。(1)x (1)x是是G G的桥的桥;(2)x (2)x不在不在G G的任一圈上的任一圈上;(3)(3)存在存在G G的两个不同顶点的两个不同顶点u u和和v,v,使得边使得边x x在在联结联结u u和和v v的每条路上的每条路上;(4)(4)存在存在V V的一个划分的一个划分U,W,U,W,使得使得 u u U U及及 w w W,xW,x在每一条连接在每一条连接u u与与w w的路上。的路上。7.3 7.3 割点、桥和割集割点

35、、桥和割集第三十六页，本课件共有45页36 定义定义7.3.3 7.3.3 图图G=(V,E),SG=(V,E),S E,E,如果从如果从G G中去掉中去掉S S中的所有边得到的图中的所有边得到的图G-SG-S的支数大于的支数大于G G的支数的支数,而去掉而去掉S S的任一真子集中的边得到的图的支数不的任一真子集中的边得到的图的支数不大于大于G G的支数的支数,则称则称S S为为G G的一个割集。的一个割集。割集割集7.3 7.3 割点、桥和割集割点、桥和割集abcdefg1818191520820931516第三十七页，本课件共有45页37 定理定理7.3.4 7.3.4 设设S S是连通图

36、是连通图G=(V,E)G=(V,E)的割集的割集,则则G-SG-S恰有两个支恰有两个支。证证 这与这与S S是割集矛盾是割集矛盾,所以所以G-SG-S恰有两个支。恰有两个支。假如假如G-SG-S的支数大于的支数大于2,2,则把则把S S的边逐一加入的边逐一加入G-SG-S中；中；每加入一条边至多能把每加入一条边至多能把G-SG-S的两个支联结在的两个支联结在一起；一起；将将G G中边逐一加入中边逐一加入G-SG-S中中,总有一步使之有两总有一步使之有两个支个支;设加入的边为设加入的边为xx1 1,x,x2 2,.,x,.,xn n；则则S S1 1=S-x=S-x1 1,x,x2 2,.,x,

37、.,xn n 是是S S的一个真子集；的一个真子集；G-SG-S1 1的支数也比的支数也比G G的支数多；的支数多；7.3 7.3 割点、桥和割集割点、桥和割集第三十八页，本课件共有45页38 推论推论7.3.2 7.3.2 不连通图不连通图G G的每个割集必是的每个割集必是G G的某的某个支的割集。个支的割集。推论推论7.3.1 7.3.1 设设G G是一个有是一个有k k个支的图个支的图,如果如果S S是是G G的割集的割集,则则G-SG-S恰有恰有k+1k+1个支。个支。7.3 7.3 割点、桥和割集割点、桥和割集 定理定理7.3.5 7.3.5 设设T T是连通图是连通图G=(V,E)

38、G=(V,E)的任一生的任一生成树成树,则则G G的每个割集至少包含的每个割集至少包含T T的一条边。的一条边。第三十九页，本课件共有45页39 定理定理7.3.6 7.3.6 连通图连通图G G的每个圈与的每个圈与G G的任一的任一割集有偶数条公共边。割集有偶数条公共边。证证 设设C C是连通图是连通图G G中的一个圈中的一个圈,S,S是是G G的一个割的一个割集集,G,G1 1和和G G2 2是是G-SG-S的仅有的两个支的仅有的两个支,如果如果C C在在G G1 1中或中或G G2 2中中,则则C C与与S S无公共边无公共边,所以公共所以公共边数为边数为0,0,故这时定理的结论成立故这

39、时定理的结论成立,7.3 7.3 割点、桥和割集割点、桥和割集第四十页，本课件共有45页40 现在假设圈现在假设圈C C与割集与割集S S有公共边有公共边,则则C C上既有上既有G G1 1的顶点又有的顶点又有G G2 2的顶点的顶点,当从当从G G1 1的一个顶点的一个顶点v v1 1开始沿开始沿C C周游时周游时,必经必经一条边其两端分别在一条边其两端分别在G G1 1和和G G2 2里里,然后在某个时候又然后在某个时候又经过另一条这样的边返回经过另一条这样的边返回G G1 1,如此走下去如此走下去,当走完圈当走完圈的边而回到的边而回到v v1 1时经过偶数次这样的边，时经过偶数次这样的边

40、，两个端点分别在两个端点分别在G G1 1与与G G2 2中中,这样的边必在这样的边必在S S中中,所以所以,这时这时C C与与S S也有偶数条边。也有偶数条边。7.3 7.3 割点、桥和割集割点、桥和割集第四十一页，本课件共有45页41 设设G=(V,E)G=(V,E)是一个连通图是一个连通图,T=(V,F),T=(V,F)是是G G的一个生的一个生成树。成树。T+e T+e中的唯一圈称为中的唯一圈称为G G的相对于生成树的相对于生成树T T的基本圈的基本圈,这些基本圈之集称为与这些基本圈之集称为与T T关联的基本圈系统。关联的基本圈系统。弦与基本圈弦与基本圈EFEF中的每条边中的每条边e

41、e为为T T的弦的弦,T+eT+e中有唯一的一个圈中有唯一的一个圈,7.3 7.3 割点、桥和割集割点、桥和割集 v v1 1 v v6 6v v4 4 v v2 2 v v5 5 v v7 7 v v3 3 x x第四十二页，本课件共有45页42 对于对于T T的每条边的每条边x,T-xx,T-x有两个支有两个支,于是于是V V被分为两个不相被分为两个不相交子集交子集V V1 1和和V V2 2；基本割集基本割集 G G的一个端点在的一个端点在V V1 1里里,另一个另一个端点在端点在V V2 2里的边形成了里的边形成了G G的一的一个割集个割集,这个割集是由边这个割集是由边x x确定确定的

42、；的；7.3 7.3 割点、桥和割集割点、桥和割集 这个割集称由边这个割集称由边x x确定的基确定的基本割集；本割集；v v1 1 v v6 6v v4 4 v v2 2 v v5 5 v v7 7 v v3 3 x x所有这些割集之集称为所有这些割集之集称为G G的相对的相对T T的基本割集系统。的基本割集系统。T T的每条边确定的割集称为的每条边确定的割集称为G G的相对的相对T T的基本割集；的基本割集；第四十三页，本课件共有45页43 定理定理7.3.7 7.3.7 设设T T是连通图是连通图G G的一个生成树的一个生成树,e,e是是T T的一条弦的一条弦,C,C是由是由e e确定的确

43、定的T+eT+e中的一个基本圈中的一个基本圈,则则e e含在含在C C上除上除e e外的每条边确定的基本割集中外的每条边确定的基本割集中,但但不在其他割集中。不在其他割集中。7.3 7.3 割点、桥和割集割点、桥和割集 v v1 1 v v6 6v v4 4 v v2 2 v v5 5 v v7 7 v v3 3 x xe第四十四页，本课件共有45页44 定理定理7.3.8 7.3.8 设设T T是连通图是连通图G G的生成树的生成树,x,x是是T T的一的一条边条边,S,S为由为由x x确定的相对确定的相对T T的一个基本割集的一个基本割集,则则x x必在必在由由S S的每条弦确定的基本圈上

44、的每条弦确定的基本圈上,而不在其它基本圈上。而不在其它基本圈上。v v1 1 v v6 6v v4 4 v v2 2 v v5 5 v v7 7 v v3 3 x xS=x,vS=x,v2 2v v5 5,v,v1 1v v6 6 S S有两条弦有两条弦v v2 2v v5 5,v,v1 1v v6 6这两条弦确定的基本圈是这两条弦确定的基本圈是v v2 2v v5 5v v7 7v v3 3v v2 2和和v v1 1v v6 6v v7 7v v3 3v v1 1在其它基本圈上没有在其它基本圈上没有x x例如例如:v:v1 1v v4 4确定的基本圈确定的基本圈v v1 1v v4 4v v3 3v v1 17.3 7.3 割点、桥和割集割点、桥和割集第四十五页，本课件共有45页45