集合论与图论第七章

1、集合论与图论第七章第1页，共45页，2022年，5月20日，1点22分，星期四17.1 树及其性质仅有一个顶点的树称为平凡树。 定义7.1.1 连通且无圈的无向图称为无向树,简称树。 一个没有圈的不连通的无向图称为无向森林,简称森林; 第2页，共45页，2022年，5月20日，1点22分，星期四2 定理7.1.1 设G=(V,E)是一个(p,q)图,则下列各命题等价:(1)G是树 (2)G的任意两个不同顶点间有唯一的一条路联结;(3)G是连通的且p=q+1;(4)G中无圈且p=q+1; (5)G中无圈且G中任意两个不邻接的顶点间加一条边,则得到一个有唯一的一个圈的图; (6)G是连通的,并且若

2、p3,则G不是Kp,G中任意两个不邻接的顶点间加一条边,则得到一个有唯一的一个圈的图。7.1 树及其性质第3页，共45页，2022年，5月20日，1点22分，星期四3 推论7.1.1 任一非平凡树中至少有两个度为1的顶点。7.1 树及其性质 定义7.1.2 连通图G称为是极小连通图,如果去掉G的任意一条边后得到的都是不连通图。极小连通图 推论7.1.2 图G是树当且仅当G是极小连通图。第4页，共45页，2022年，5月20日，1点22分，星期四4定义7.1.3 设G=(V,E)是连通图,vV,数称为v在G中的偏心率, v v点的偏心率是3,顶点v的偏心率7.1 树及其性质连通图G的半径 称为G

3、的半径,满足r(G)=e(v)的顶点v称为G的中心点,G的所有中心点组成的集合称为G的中心,G的中心记为C(G)第5页，共45页，2022年，5月20日，1点22分，星期四5 定理7.1.2 每棵树的中心或含有一个顶点,或含有两个邻接的顶点v4 v5 v3 v2 v1离中心最远的点满足什么性质?都是一度顶点; v4 v3 v2 如果把1度顶点都去掉，会不会引起中心点的变化？不会引起中心点的变化。7.1 树及其性质图1图2图3v5 v6 v4 v3 v2 v1第6页，共45页，2022年，5月20日，1点22分，星期四6 定理7.1.2 每棵树的中心或含有一个顶点,或含有两个邻接的顶点。 证显然

4、,一个顶点的树有一个中心,两个顶点的树有两个中心,这时定理成立; 设v是中心,则v只有到达一个一度顶点时,其偏心率才能达到最大值。 把所有的一度顶点全去掉，则其中心的偏心率都少1。 每次把所有的一度顶点全去掉，并不引起中心的变化。 每次把所有的一度顶点全去掉,经有限步必可得到一个只有一个顶点的树,或只有两个顶点的树。7.1 树及其性质第7页，共45页，2022年，5月20日，1点22分，星期四7 例7.1.1 任何一个非平凡的树都可用两种颜色给其顶点染色,使得每条边的两个端点不同色。 由第六章第4节中偶图的充分必要条件是图中所有圈都是偶数长可得树是偶图。 因此树可用两种颜色染色，并且每条边的两

5、个端点不同色。7.1 树及其性质第8页，共45页，2022年，5月20日，1点22分，星期四87.2 生成树 1、若图G有生成树,则G是连通的,所以不连通图没有生成树, 定义7.2.1 设G=(V,E)是一个图,G的一个生成子图T=(V,F)如果是树,则称T是G的生成树。2、连通图都有生成树吗? 定理7.2.1 图G有生成树的充分必要条件是G为一个连通图。第9页，共45页，2022年，5月20日，1点22分，星期四9 推论7.2.1 设G是一个(p,q)连通图,则qp-1。 定义7.2.2 设G是一个图,若G的生成子图F是一个森林,则F称为G的一个生成森林。任意图都有生成森林。7.2 生成树第

6、10页，共45页，2022年，5月20日，1点22分，星期四10 定理7.2.2 具有p个顶点的完全图Kp有pp-2棵生成树,p2.证设Kp的顶点集V=1,2,.,p, 定理中的数pp-2恰好是以V中数为项的长为p-2的所有序列的个数, 要证明该定理,只须在Kp的所有生成树之集与这些长为p-2的序列之集间建立一个一一对应即可。7.2 生成树第11页，共45页，2022年，5月20日，1点22分，星期四1112534 设一棵树的顶点集为A 1、从中找到编号最小的叶子结点，去掉该叶子结点a1及其邻接边(a1,b1)。 2、重复以上过程。只到剩一条边为止。 (1,2),(4,3),(3,2) 这棵树

7、对应序列（2，3，2） 一个棵对应序列B=b1b2b3bp-2而且是唯一的 定理7.2.2 具有p个顶点的完全图Kp有pp-2棵生成树,p2.7.2 生成树第12页，共45页，2022年，5月20日，1点22分，星期四1212534 树的顶点集合为12345 这棵树对应序列（2，3，2） 任给一个序列Bb1,b2,b3,bp-2 1、从A找到最小的不属于B的元素,设为a1,与b1连接，从A中去掉a1，从B中去掉b1. 2、重复以上过程只到B为空，A中剩余两个 3、连接剩余的两个顶点。7.2 生成树第13页，共45页，2022年，5月20日，1点22分，星期四13 定理7.2.3 设G=(V,E

8、)是连通图,T1=(V,E1)和T2=(V,E2)是G的两个不同的生成树,如果e1E1E2,则e2E2E1,使得(T1-e1)+e2为G的一棵生成树。7.2 生成树证所以(T1-e1)+e2是G的生成树。 由于T2是连通的，所以必然在V1与V2之间存在T2的一条边e2， 因为V1与V2之间在T1中只有一条边e1，所以e2E1,由树的性质,T1-e1恰有两个支,设这两支分别为G1=(V1,F1),G2=(V2,F2)因为e1E2,所以e2e1第14页，共45页，2022年，5月20日，1点22分，星期四14 定义7.2.3 设T1,T2是G的生成树,是T1的边但不是T2的边的条数k称为T1与T2

9、的距离,记为d(T1,T2)=k。由定义可知d(T1,T2)0,G的生成树之间的距离并且d(T2,T1)=d(T1,T2) 设T1的边集为E1,T2的边集为E2,用集合怎么表示两个生成树之间的距离?E1E27.2 生成树第15页，共45页，2022年，5月20日，1点22分，星期四15d(T1,T2) d(T1,T3) + d(T3,T2) 是T1的边但不是T2的边包括在如下情况中, 是T1的边不是T2的边是T3的边, 是T1的边不是T2的边也不是T3的边,7.2 生成树第16页，共45页，2022年，5月20日，1点22分，星期四16两个生成树之间的基本树变换若d(T1,T2)=1,T2=(

10、T1-e1)+e2它称为从T1到T2的一个基本树变换。 则T1中有一条边e1不在T2中,T2中也有一条边不在T1中,7.2 生成树第17页，共45页，2022年，5月20日，1点22分，星期四17 定理7.2.4 设T0和T是G的两距离为k的生成树,则从T0开始经k次基本树变换便可得到T。当k=0成立;证假设kn时结论成立,需证k=n+1时定理成立,设d(T0,T)=n+1,当k=1时，由定理7.2.3知结论成立。 由定理7.2.3,从T0中去掉一条不在T中边e1后,必在T中找到一条不在T0中边e27.2 生成树第18页，共45页，2022年，5月20日，1点22分，星期四18d(T1,T)=

11、n,由假设知d(T0,T)=n+1,由归纳假设,从T1经n个基本树变换便到T,因此从T0经n+1个基本树变换得到T因此定理成立。使得(T0-e1)+e2为生成树,设(T0-e1)+e2=T1,7.2 生成树第19页，共45页，2022年，5月20日，1点22分，星期四19最小生成树问题生成树的权 图G123123 T1231237.2 生成树 给定边带权连通图G,G中边的权是一个非负实数,生成树中各边的权之和称为该生成树的权； G的生成树中权最小的那个生成树就是最小生成树。图G的生成树T的权是6第20页，共45页，2022年，5月20日，1点22分，星期四20 如果边的权代表路程，最小生成树就

12、是原图中路程最短的连通图。 如果边的权代表修路资金，最小生成树就是原图中花费资金最少的连通图。1、最小生成树不一定只有一个； 2、最小生成树按边的权的性质不同可以有不同的理解；7.2 生成树第21页，共45页，2022年，5月20日，1点22分，星期四21 定义7.2.4 设T是连通图G的生成树,G中不是T的边称为T的弦。 若G是一个(p,q)连通图,T是G的生成树,问T有多少条弦?T有p-1条边,有q-p+1条弦,生成树T的弦生成树T的基本圈, 如果e是T的一条弦,则T+e中有唯一的一个圈,这个圈称为G的相对生成树T的基本圈,在这个圈上只有e是T的弦,其它都是T的边,7.2 生成树第22页，

13、共45页，2022年，5月20日，1点22分，星期四22 设G=(V,E,w)是一个边带权图,其中对每条边xE,w(x)0, 如果T0是G的一个最小生成树,e是T0的一条弦,则T0+e中有唯一的一个圈C, C上的每条边x有w(x)w(e) G12433w(e) 如果有一条边x,w(x)w(e)从圈中去掉边x,加入边e则得到一个比T0更小的生成树。G12433w(e)7.2 生成树第23页，共45页，2022年，5月20日，1点22分，星期四23 定理7.2.5 设G=(V,E,w)是一个连通的边带权图,边上的权函数w是非负, (V1,E1),(V2,E2),.,(Vk,Ek)是G的生成森林,k

14、1,F= ,如果e=uv是EF中权值最小的边且uV1,vV1中,则存在G的一个包含Fe的生成树T,使得T的权不大于任一包含F的生成树的权。7.2 生成树第24页，共45页，2022年，5月20日，1点22分，星期四24 生成树T123344uve 图G123344uve 生成树T的权是包含生成森林的生成树中权最小的生成树。7.2 生成树第25页，共45页，2022年，5月20日，1点22分，星期四25证用反证法证明 把e加到T中,则T+e中有唯一的圈C使得C上除了边e外,必还有边e=uv,uV1,vV1, 根据e的假设必有w(e)w(e),从T+e中去掉e,得到一生成树T,T包含了Fe,并且T

15、的权不大于T的权,这与关于T的假定相矛盾; 如若不然,则G有一个生成树T=(V,E),T包含F(即FE),不包含边e；T的权小于任一包含Fe的生成树的权,因此定理成立。7.2 生成树第26页，共45页，2022年，5月20日，1点22分，星期四26最小生成树Kruskal算法14530265157356421453027.2 生成树第27页，共45页，2022年，5月20日，1点22分，星期四277.2 生成树输入:连通图G=(V,E),其中V=1,2,n, 输出:一颗最小生成树:算法:void Kruskal(V,T)T=V; ncomp=n;/连通分支 while(ncomp1)从E中取出

16、删除权最小的边(v,u); if(v和u属于T中不同的连通分支) T=T(v,u); ncomp-; 第28页，共45页，2022年，5月20日，1点22分，星期四28 定理7.2.6 设G=(V,E,w)是一个边带权连通图,U是V的一个真子集,如果u,v是uU,vVU的G的一条边,并且是所有的这样的边中,u,v的权w(u,v)最小,则G中一定存在一个最小生成树,它以u,v为其中一条边。7.2 生成树abcdefg1818191520820931516UVU第29页，共45页，2022年，5月20日，1点22分，星期四29证用反证法于是,T是含边u,v的最小生成树;在圈上有一条边u,v,使得u

17、U,vVU;假如G的最小生成树都不含边u,v; 令T=(T+uv)-uv,由于w(u,v)w(u,v),所以T的权T的权;这与假设相矛盾。 把边u,v加到G的一棵最小生成树T中,那么T+uv中有一个含边uv的圈;7.2 生成树第30页，共45页，2022年，5月20日，1点22分，星期四30Prim算法的基本思想是: 1、先置U=i1,E=,选取满足i2VU的边i1,i2使w(i1,i2)最小; 直到把所有的顶点都加入到U中,所得到的边集就构成一棵最小生成树。设G=(V,E,w)是带权连通图,V=1,2,.,p 2、置U=i1,i2,E=i1i2,选取满足iU,i3VU的边i,i3,使w(i,

18、i3)最小; 3、置U=i1,i2,i3,E=i1i2,ii3,继续这样的过程;7.2 生成树*第31页，共45页，2022年，5月20日，1点22分，星期四317.3 割点、桥和割集 定义7.3.1 设v是图G的一个顶点，如果G-v的支数大于G的支数，则称顶点v为图G的一个割点。上图中v5是割点，其它都不是割点。1、割点 v1 v6 v7 v4 v2 v5 v3 v8 v9 v1 v6 v7 v4 v2 v3 v8 v9第32页，共45页，2022年，5月20日，1点22分，星期四32 定义7.3.2 图G的一条边x称为G的一座桥，如果G-x的支数大于G的支数。图中边v2v5是桥；2、桥 v

19、1 v6 v4 v2 v5 v7 v3 图中边v5v6,v5v7也是桥。7.3 割点、桥和割集第33页，共45页，2022年，5月20日，1点22分，星期四33 定理7.3.1 设v是连通图G=(V,E)的一个顶点，则下列命题等价： (1)v是图G的一个割点; (2)存在与v不同的两个顶点u和w,使得v在每一条u与w间的路上; (3)集合Vv有一个二划分U,W使得uU,wW,v在联结u和w的每条路上。7.3 割点、桥和割集第34页，共45页，2022年，5月20日，1点22分，星期四34 定理7.3.2 每个非平凡的连通图至少有两个顶点不是割点。证非平凡图的连通图必有生成树, 非平凡树至少有两

20、个度为1的顶点,它们就是原图的非割点。7.3 割点、桥和割集第35页，共45页，2022年，5月20日，1点22分，星期四35 定理7.3.3 设x是连通图G=(V,E)的一条边,则下列命题等价。 (1)x是G的桥; (2)x不在G的任一圈上; (3)存在G的两个不同顶点u和v,使得边x在联结u和v的每条路上; (4)存在V的一个划分U,W,使得uU及wW,x在每一条连接u与w的路上。7.3 割点、桥和割集第36页，共45页，2022年，5月20日，1点22分，星期四36 定义7.3.3 图G=(V,E),SE,如果从G中去掉S中的所有边得到的图G-S的支数大于G的支数,而去掉S的任一真子集中

21、的边得到的图的支数不大于G的支数,则称S为G的一个割集。割集7.3 割点、桥和割集abcdefg1818191520820931516第37页，共45页，2022年，5月20日，1点22分，星期四37 定理7.3.4 设S是连通图G=(V,E)的割集,则G-S恰有两个支。证这与S是割集矛盾,所以G-S恰有两个支。 假如G-S的支数大于2,则把S的边逐一加入G-S中； 每加入一条边至多能把G-S的两个支联结在一起； 将G中边逐一加入G-S中,总有一步使之有两个支;设加入的边为x1,x2,.,xn；则S1=S-x1,x2,.,xn是S的一个真子集；G-S1的支数也比G的支数多；7.3 割点、桥和割

22、集第38页，共45页，2022年，5月20日，1点22分，星期四38 推论7.3.2 不连通图G的每个割集必是G的某个支的割集。 推论7.3.1 设G是一个有k个支的图,如果S是G的割集,则G-S恰有k+1个支。7.3 割点、桥和割集 定理7.3.5 设T是连通图G=(V,E)的任一生成树,则G的每个割集至少包含T的一条边。第39页，共45页，2022年，5月20日，1点22分，星期四39 定理7.3.6 连通图G的每个圈与G的任一割集有偶数条公共边。 证设C是连通图G中的一个圈,S是G的一个割集,G1和G2是G-S的仅有的两个支, 如果C在G1中或G2中,则C与S无公共边,所以公共边数为0,故这时定理的结论成立,7.3 割点、桥和割集第40页，共45页，2022年，5月20日，1点22分，星期四40 现在假设圈C与割集S有公共边,则C上既有G1的顶点又有G2的顶点, 当从G1的一个顶点v1开始沿C周游时,必经一条边其两端分别在G1和G2里,然后在某个时候又经过另一条这样的边返回G1,如此走下去,当走完圈的边而回到v1时经过偶数次这样的边， 两个端点分别在G1与G2中,这样的边必在S中,所以,这时C与S也有偶数条边。7.3 割点、桥和割集第41页，共45页，2022年，5月20日，1点22分，星期四41 设G=(V,