集合论与图论第七章

集合论与图论第七章第一页，共四十五页，编辑于2023年，星期五17.1树及其性质仅有一个顶点的树称为平凡树。定义7.1.1连通且无圈的无向图称为无向树,简称树。一个没有圈的不连通的无向图称为无向森林,简称森林;第二页，共四十五页，编辑于2023年，星期五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是连通的,并且若p≥3,则G不是Kp,G中任意两个不邻接的顶点间加一条边,则得到一个有唯一的一个圈的图。7.1树及其性质第三页，共四十五页，编辑于2023年，星期五3推论7.1.1任一非平凡树中至少有两个度为1的顶点。7.1树及其性质定义7.1.2连通图G称为是极小连通图,如果去掉G的任意一条边后得到的都是不连通图。极小连通图推论7.1.2图G是树当且仅当G是极小连通图。第四页，共四十五页，编辑于2023年，星期五4定义7.1.3设G=(V,E)是连通图,vV,数称为v在G中的偏心率,vv点的偏心率是3,顶点v的偏心率7.1树及其性质连通图G的半径称为G的半径,满足r(G)=e(v)的顶点v称为G的中心点,G的所有中心点组成的集合称为G的中心,G的中心记为C(G)第五页，共四十五页，编辑于2023年，星期五5定理7.1.2每棵树的中心或含有一个顶点,或含有两个邻接的顶点v4v5v3v2v1离中心最远的点满足什么性质?都是一度顶点;

v4v3v2

如果把1度顶点都去掉，会不会引起中心点的变化？不会引起中心点的变化。7.1树及其性质图1图2图3v5v6v4v3v2v1第六页，共四十五页，编辑于2023年，星期五6定理7.1.2每棵树的中心或含有一个顶点,或含有两个邻接的顶点。[证]显然,一个顶点的树有一个中心,两个顶点的树有两个中心,这时定理成立;设v是中心,则v只有到达一个一度顶点时,其偏心率才能达到最大值。把所有的一度顶点全去掉，则其中心的偏心率都少1。每次把所有的一度顶点全去掉，并不引起中心的变化。每次把所有的一度顶点全去掉,经有限步必可得到一个只有一个顶点的树,或只有两个顶点的树。7.1树及其性质第七页，共四十五页，编辑于2023年，星期五7例7.1.1任何一个非平凡的树都可用两种颜色给其顶点染色,使得每条边的两个端点不同色。由第六章第4节中偶图的充分必要条件是图中所有圈都是偶数长可得树是偶图。因此树可用两种颜色染色，并且每条边的两个端点不同色。7.1树及其性质第八页，共四十五页，编辑于2023年，星期五87.2生成树1、若图G有生成树,则G是连通的,所以不连通图没有生成树,定义7.2.1设G=(V,E)是一个图,G的一个生成子图T=(V,F)如果是树,则称T是G的生成树。2、连通图都有生成树吗?定理7.2.1图G有生成树的充分必要条件是G为一个连通图。第九页，共四十五页，编辑于2023年，星期五9推论7.2.1设G是一个(p,q)连通图,则q≥p-1。定义7.2.2设G是一个图,若G的生成子图F是一个森林,则F称为G的一个生成森林。任意图都有生成森林。7.2生成树第十页，共四十五页，编辑于2023年，星期五10定理7.2.2具有p个顶点的完全图Kp有pp-2棵生成树,p≥2.[证]设Kp的顶点集V={1,2,...,p},定理中的数pp-2恰好是以V中数为项的长为p-2的所有序列的个数,要证明该定理,只须在Kp的所有生成树之集与这些长为p-2的序列之集间建立一个一一对应即可。7.2生成树第十一页，共四十五页，编辑于2023年，星期五1112534设一棵树的顶点集为A1、从中找到编号最小的叶子结点，去掉该叶子结点a1及其邻接边(a1,b1)。2、重复以上过程。只到剩一条边为止。(1,2),(4,3),(3,2)这棵树对应序列（2，3，2）一个棵对应序列B=b1b2b3…bp-2而且是唯一的定理7.2.2具有p个顶点的完全图Kp有pp-2棵生成树,p≥2.7.2生成树第十二页，共四十五页，编辑于2023年，星期五1212534树的顶点集合为12345这棵树对应序列（2，3，2）任给一个序列B{b1,b2,b3,…,bp-2}1、从A找到最小的不属于B的元素,设为a1,与b1连接，从A中去掉a1，从B中去掉b1.2、重复以上过程只到B为空，A中剩余两个3、连接剩余的两个顶点。7.2生成树第十三页，共四十五页，编辑于2023年，星期五13定理7.2.3设G=(V,E)是连通图,T1=(V,E1)和T2=(V,E2)是G的两个不同的生成树,如果e1E1\E2,则e2E2\E1,使得(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,所以e2≠e1第十四页，共四十五页，编辑于2023年，星期五14定义7.2.3设T1,T2是G的生成树,是T1的边但不是T2的边的条数k称为T1与T2的距离,记为d(T1,T2)=k。由定义可知d(T1,T2)≥0,G的生成树之间的距离并且d(T2,T1)=d(T1,T2)设T1的边集为E1,T2的边集为E2,用集合怎么表示两个生成树之间的距离?E1\E27.2生成树第十五页，共四十五页，编辑于2023年，星期五15d(T1,T2)≤d(T1,T3)+d(T3,T2)是T1的边但不是T2的边包括在如下情况中,是T1的边不是T2的边是T3的边,是T1的边不是T2的边也不是T3的边,7.2生成树第十六页，共四十五页，编辑于2023年，星期五16两个生成树之间的基本树变换若d(T1,T2)=1,T2=(T1-e1)+e2它称为从T1到T2的一个基本树变换。则T1中有一条边e1不在T2中,T2中也有一条边不在T1中,7.2生成树第十七页，共四十五页，编辑于2023年，星期五17定理7.2.4设T0和T是G的两距离为k的生成树,则从T0开始经k次基本树变换便可得到T。当k=0成立;[证]假设k≤n时结论成立,需证k=n+1时定理成立,设d(T0,T)=n+1,当k=1时，由定理7.2.3知结论成立。由定理7.2.3,从T0中去掉一条不在T中边e1后,必在T中找到一条不在T0中边e27.2生成树第十八页，共四十五页，编辑于2023年，星期五18d(T1,T)=n,由假设知d(T0,T)=n+1,由归纳假设,从T1经n个基本树变换便到T,因此从T0经n+1个基本树变换得到T因此定理成立。使得(T0-e1)+e2为生成树,设(T0-e1)+e2=T1,7.2生成树第十九页，共四十五页，编辑于2023年，星期五19最小生成树问题生成树的权图G123123T1231237.2生成树给定边带权连通图G,G中边的权是一个非负实数,生成树中各边的权之和称为该生成树的权；G的生成树中权最小的那个生成树就是最小生成树。图G的生成树T的权是6第二十页，共四十五页，编辑于2023年，星期五20如果边的权代表路程，最小生成树就是原图中路程最短的连通图。如果边的权代表修路资金，最小生成树就是原图中花费资金最少的连通图。1、最小生成树不一定只有一个；2、最小生成树按边的权的性质不同可以有不同的理解；7.2生成树第二十一页，共四十五页，编辑于2023年，星期五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生成树第二十二页，共四十五页，编辑于2023年，星期五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生成树第二十三页，共四十五页，编辑于2023年，星期五23定理7.2.5设G=(V,E,w)是一个连通的边带权图,边上的权函数w是非负,{(V1,E1),(V2,E2),...,(Vk,Ek)}是G的生成森林,k>1,F=,如果e=uv是E\F中权值最小的边且uV1,vV1中,则存在G的一个包含F∪{e}的生成树T,使得T的权不大于任一包含F的生成树的权。7.2生成树第二十四页，共四十五页，编辑于2023年，星期五24生成树T123344uve图G123344uve生成树T的权是包含生成森林的生成树中权最小的生成树。7.2生成树第二十五页，共四十五页，编辑于2023年，星期五25[证]用反证法证明把e加到T中,则T+e中有唯一的圈C使得C上除了边e外,必还有边e=uv,uV1,vV1,根据e的假设必有w(e)≤w(e),从T+e中去掉e,得到一生成树T,T包含了F∪{e},并且T的权不大于T的权,这与关于T的假定相矛盾;如若不然,则G有一个生成树T=(V,E),T包含F(即FE),不包含边e；T的权小于任一包含F∪{e}的生成树的权,因此定理成立。7.2生成树第二十六页，共四十五页，编辑于2023年，星期五26最小生成树Kruskal算法1453026515735642145302∞∞∞∞∞∞7.2生成树第二十七页，共四十五页，编辑于2023年，星期五277.2生成树输入:连通图G=(V,E),其中V={1,2,…,n},输出:一颗最小生成树:算法:voidKruskal(V,T){T=V;ncomp=n;//连通分支while(ncomp>1){从E中取出删除权最小的边(v,u);if(v和u属于T中不同的连通分支){T=T∪{(v,u)};ncomp--;}}}第二十八页，共四十五页，编辑于2023年，星期五28定理7.2.6设G=(V,E,w)是一个边带权连通图,U是V的一个真子集,如果{u,v}是uU,vV\U的G的一条边,并且是所有的这样的边中,{u,v}的权w(u,v)最小,则G中一定存在一个最小生成树,它以{u,v}为其中一条边。7.2生成树abcdefg1818191520820931516UV\U第二十九页，共四十五页，编辑于2023年，星期五29[证]用反证法于是,T是含边{u,v}的最小生成树;在圈上有一条边{u,v},使得uU,vV\U;假如G的最小生成树都不含边{u,v};令T=(T+uv)-uv,由于w(u,v)≤w(u,v),所以T的权≤T的权;这与假设相矛盾。把边{u,v}加到G的一棵最小生成树T中,那么T+uv中有一个含边uv的圈;7.2生成树第三十页，共四十五页，编辑于2023年，星期五30Prim算法的基本思想是:1、先置U={i1},E={},选取满足i2V\U的边{i1,i2}使w(i1,i2)最小;直到把所有的顶点都加入到U中,所得到的边集就构成一棵最小生成树。设G=(V,E,w)是带权连通图,V={1,2,...,p}2、置U={i1,i2},E={i1i2},选取满足iU,i3V\U的边{i,i3},使w(i,i3)最小;3、置U={i1,i2,i3},E={i1i2,ii3},继续这样的过程;7.2生成树**第三十一页，共四十五页，编辑于2023年，星期五317.3割点、桥和割集定义7.3.1设v是图G的一个顶点，如果G-v的支数大于G的支数，则称顶点v为图G的一个割点。上图中v5是割点，其它都不是割点。1、割点v1v6v7

v4v2v5

v3v8v9v1v6v7

v4v2

v3v8v9第三十二页，共四十五页，编辑于2023年，星期五32定义7.3.2图G的一条边x称为G的一座桥，如果G-x的支数大于G的支数。图中边v2v5是桥；2、桥v1v6v4v2v5v7v3图中边v5v6,v5v7也是桥。7.3割点、桥和割集第三十三页，共四十五页，编辑于2023年，星期五33定理7.3.1设v是连通图G=(V,E)的一个顶点，则下列命题等价：(1)v是图G的一个割点;(2)存在与v不同的两个顶点u和w,使得v在每一条u与w间的路上;(3)集合V\{v}有一个二划分{U,W}使得uU,wW,v在联结u和w的每条路上。7.3割点、桥和割集第三十四页，共四十五页，编辑于2023年，星期五34定理7.3.2每个非平凡的连通图至少有两个顶点不是割点。[证]非平凡图的连通图必有生成树,非平凡树至少有两个度为1的顶点,它们就是原图的非割点。7.3割点、桥和割集第三十五页，共四十五页，编辑于2023年，星期五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割点、桥和割集第三十六页，共四十五页，编辑于2023年，星期五36定义7.3.3图G=(V,E),SE,如果从G中去掉S中的所有边得到的图G-S的支数大于G的支数,而去掉S的任一真子集中的边得到的图的支数不大于G的支数,则称S为G的一个割集。割集7.3割点、桥和割集abcdefg1818191520820931516第三十七页，共四十五页，编辑于2023年，星期五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割点、桥和割集第三十八页，共四十五页，编辑于2023年，星期五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的一条边。第三十九页，共四十五页，编辑于2023年，星期五39定理7.3.6连通图G的每个圈与G的任一割集有偶数条公共边。[证]设C是连通图G中的一个圈,S是G的一个割集,G1和G2是G-S的仅有的两个支,如果C在G1中或G2中,则C与S无公共边,所以公共边数为0,故这时定理的结论成立,7.3割点、桥和割集第四十页，共四十五页，编辑于2023年，星期五40现在假设圈C与割集S有公共边,则C上既有G1的顶点又有G2的顶点,当从G1的一个顶点v1开始沿C周游时,必经一条边其两端分别在G1和G2里,然后在某个时候又经过另一条这样的边返回G1,如此走下去,当走完圈的边而回到v1时经过偶数次这样的边，两个端点分别在G1与G2中,这样的边必在S中,所以,这时C与S也有偶数条边。7.3割点、桥和割集第四十一页，共四十五页，编辑于2023年，星期五41设G=(V,E)是一个连通图,T=(V,F)是G的一个生成树。T+e中的唯一圈称为G的相对于生成树T的基本圈,这些基本圈之集称为与T关联的基本圈系统。弦与基本圈E\F中的每条边e为T的弦,T+e中有唯一的一个圈,7.3割点、桥和割集v1v6v4