离散数学屈婉玲第十一章课件.ppt

1、1第十一章第十一章 几种特殊的图几种特殊的图主要内容主要内容l 欧拉图欧拉图l 哈密顿图哈密顿图l 二部图与匹配二部图与匹配l 平面图平面图l 着色着色.211.1 欧拉图欧拉图历史背景：哥尼斯堡七桥问题历史背景：哥尼斯堡七桥问题.3欧拉图定义欧拉图定义定义定义11.1 图图(无向图或有向图无向图或有向图)中所有边恰好通过一次且经过中所有边恰好通过一次且经过所有顶点的通路称为所有顶点的通路称为欧拉通路欧拉通路.图中所有边恰好通过一次且图中所有边恰好通过一次且经过所有顶点的回路称为经过所有顶点的回路称为欧拉回路欧拉回路具有欧拉回路的图称为具有欧拉回路的图称为欧拉图欧拉图.具有欧拉通路而无欧拉回路

2、的图称为具有欧拉通路而无欧拉回路的图称为半欧拉图半欧拉图说明：说明：规定平凡图为欧拉图规定平凡图为欧拉图.环不影响图的欧拉性环不影响图的欧拉性.4欧拉图实例欧拉图实例欧拉图欧拉图不是不是半欧拉图半欧拉图欧拉图欧拉图不是不是半欧拉图半欧拉图.5欧拉图的判别法欧拉图的判别法定理定理11.1 (1)无向图无向图G是欧拉图当且仅当是欧拉图当且仅当G是连通的且没有奇是连通的且没有奇度顶点度顶点(2)无向图无向图G是半欧拉图当且仅当是半欧拉图当且仅当G是连通的且恰有两个奇度是连通的且恰有两个奇度顶点顶点(3)有向图有向图D是欧拉图当且仅当是欧拉图当且仅当D是强连通的且每个顶点的入是强连通的且每个顶点的入度

3、等于出度度等于出度(4)有向图有向图D是半欧拉图当且仅当是半欧拉图当且仅当D是单向连通的且恰有两个是单向连通的且恰有两个奇度顶点奇度顶点,其中一个顶点的入度比出度大其中一个顶点的入度比出度大1,另一个顶点出度另一个顶点出度比入度大比入度大1,其余顶点的入度等于出度其余顶点的入度等于出度例例1 设设G是非平凡的欧拉图，则是非平凡的欧拉图，则(G)2.证证 只需证明只需证明G的任意一条边的任意一条边e都不是桥都不是桥.设设C是一条欧拉回路是一条欧拉回路,e在在C上，因而上，因而G e仍是连通的，故仍是连通的，故e不是桥不是桥.6Fleury算法算法算法：算法：(1)任取任取v0 V(G),令令P0

4、=v0,i=0.(2)设设Pi=v0e1v1e2eivi，如果如果E(G)-e1,e2,ei 中没有与中没有与vi关联的边关联的边,则计算结束则计算结束;否则按下面方法从否则按下面方法从E(G)e1,e2,ei 中选取中选取ei+1：(a)ei+1与与vi 关联；关联；(b)除非无别的边可供选择除非无别的边可供选择,否则否则ei+1不应为不应为 G e1,e2,ei 中的桥中的桥.设设ei+1=(vi,vi+1),把把ei+1vi+1加入加入Pi.(3)令令i=i+1,返回返回(2).7实例实例一笔画出一条欧拉回路一笔画出一条欧拉回路.8实例实例一笔画出一条欧拉回路一笔画出一条欧拉回路.911

5、.2 哈密顿图哈密顿图历史背景：哈密顿周游世界问题历史背景：哈密顿周游世界问题 (1)(2).10哈密顿图与半哈密顿图哈密顿图与半哈密顿图定义定义11.2 经过图中所有顶点一次且仅一次的通路称作经过图中所有顶点一次且仅一次的通路称作哈密顿哈密顿通路通路.经过图中所有顶点一次且仅一次的回路称作经过图中所有顶点一次且仅一次的回路称作哈密顿回哈密顿回路路.具有哈密顿回路的图称作具有哈密顿回路的图称作哈密顿图哈密顿图.具有哈密顿通路且无具有哈密顿通路且无哈密顿回路的图称作哈密顿回路的图称作半哈密顿图半哈密顿图.规定规定:平凡图是哈密顿图平凡图是哈密顿图.哈密顿图哈密顿图半哈密顿图半哈密顿图哈密顿图哈密

6、顿图例例不是不是.11无向哈密顿图的一个必要条件无向哈密顿图的一个必要条件定理定理11.2 设无向图设无向图G=是哈密顿图，对于任意是哈密顿图，对于任意V1 V且且V1，均有，均有 p(G V1)|V1|证证 设设C为为G中一条哈密顿回路中一条哈密顿回路(1)p(C V1)|V1|(2)p(G V1)p(C V1)|V1|（因为（因为C G）推论推论 设无向图设无向图G=是半哈密顿图，对于任意的是半哈密顿图，对于任意的V1 V且且V1均有均有 p(G V1)|V1|+1证证 设设 为从为从u到到v的哈密顿通路，令的哈密顿通路，令G =G(u,v)，则，则G 为为哈密顿图哈密顿图.于是于是 p(

7、G V1)=p(G V1(u,v)p(G V1)+1|V1|+1.12例题例题例例2 判断下面的图是不是哈密顿图判断下面的图是不是哈密顿图,是不是半哈密顿图是不是半哈密顿图.解解 (a)取取V1=a,f,p(G V1)=|b,c,d,e|=4|V1|=2,不是哈密顿图，不是哈密顿图，也不是半哈密顿图也不是半哈密顿图(b)取取V1=a,g,h,i,c,p(G V1)=|b,e,f,j,k,d|=6|V1|=5,不是哈密不是哈密顿图顿图.而而baegjckhfid是一条哈密顿通路是一条哈密顿通路,是半哈密顿图是半哈密顿图(c)abcdgihjefa是一条哈密顿回路，是哈密顿图是一条哈密顿回路，是哈

8、密顿图.13例题例题例例3 设设G为为n阶无向连通简单图，若阶无向连通简单图，若G中有割点或桥，则中有割点或桥，则G不不是哈密顿图是哈密顿图.证证 设设v为割点，则为割点，则 p(G v)2|v|=1.K2有桥，它显然不是哈密顿图有桥，它显然不是哈密顿图.除除K2外，其他有桥的连外，其他有桥的连通图均有割点通图均有割点.14无向哈密顿图的一个充分条件无向哈密顿图的一个充分条件定理定理11.3 设设G是是n阶无向简单图阶无向简单图,若对于任意不相邻的顶点若对于任意不相邻的顶点vi,vj,均有均有 d(vi)+d(vj)n 1 ()则则G 中存在哈密顿通路中存在哈密顿通路.推论推论 设设G为为n(

9、n 3)阶无向简单图阶无向简单图,若对于若对于G中任意两个不相中任意两个不相邻的顶点邻的顶点vi,vj,均有均有 d(vi)+d(vj)n （）则则G中存在哈密顿回路中存在哈密顿回路.15判断是否为哈密顿图判断是否为哈密顿图 判断是否为判断是否为(半半)哈密顿图至今还是一个难题哈密顿图至今还是一个难题.(1)观察出一条哈密顿回路或哈密顿通路观察出一条哈密顿回路或哈密顿通路.(2)证明满足充分条件证明满足充分条件.(3)证明不满足必要条件证明不满足必要条件.例例4 证明右图证明右图(周游世界问题周游世界问题)是哈密顿图是哈密顿图证证 a b c d e f g h i j k l m n o p

10、 q r s t a是一条哈密顿回路是一条哈密顿回路.注意，此图不满足定理注意，此图不满足定理11.3推论的条件推论的条件.例例5 完全图完全图Kn(n 3)是哈密顿图是哈密顿图.证证 任何两个顶点任何两个顶点u,v，d(u)+d(v)=2(n 1)n.16货郎问题货郎问题货郎问题货郎问题:有有n个城市个城市,给定城市之间道路的长度给定城市之间道路的长度(长度可以为长度可以为,对应这两个城市之间无交通线对应这两个城市之间无交通线).货郎从某个城市出发货郎从某个城市出发,要要经过每个城市一次且仅一次经过每个城市一次且仅一次,最后回到出发的城市最后回到出发的城市,问如何走问如何走才能使他走的路线最

11、短才能使他走的路线最短?图论方法描述如下图论方法描述如下:设设G=为一个为一个n阶完全带权图阶完全带权图Kn,各边的权非负各边的权非负,且可能为且可能为.求求G中的一条最短的哈密顿回路中的一条最短的哈密顿回路.不计出发点和方向不计出发点和方向,Kn(n 3)中有中有(n 1)!/2 条不同的哈密顿回条不同的哈密顿回路路.17 解解 C1=a b c d a,W(C1)=10 C2=a b d c a,W(C2)=11 C3=a c b d a,W(C3)=9 最短最短 例例6 求下面带权图求下面带权图K4中最短哈密顿回路中最短哈密顿回路.例题例题.1811.3 二部图与匹配二部图与匹配定义定义

12、11.3 设设 G=为一个无向图为一个无向图,若能将若能将 V分成分成 V1和和V2(V1 V2=V,V1 V2=),使得使得 G 中的每条边的两个端点都是一中的每条边的两个端点都是一个属于个属于V1,另一个属于另一个属于V2,则称则称 G 为为二部图二部图(或称或称二分图二分图,偶偶图图),称称V1和和V2为为互补顶点子集互补顶点子集,常将二部图常将二部图G记为记为.又若又若G是简单二部图是简单二部图,V1中每个顶点均与中每个顶点均与V2中所有的顶点相邻，中所有的顶点相邻，则称则称G为为完全二部图完全二部图,记为记为 Kr,s,其中其中r=|V1|,s=|V2|.19实例实例例例K2,3K3

13、,3.20二部图的判别法二部图的判别法定理定理11.4 无向图无向图G=是二部图当且仅当是二部图当且仅当G中无奇圈中无奇圈.证证 必要性必要性.若若G中无圈中无圈,结论成立结论成立.若若G中有圈中有圈,设设G中的一个中的一个圈圈C=v1v2vlv1,l2.不妨设不妨设v1 V1,v1,v2,vl 依次交替属于依次交替属于V1,V2且且vl V2,因而因而l为偶数为偶数.得证得证C为偶圈为偶圈充分性充分性.不妨设不妨设G为连通图为连通图,否则可对每个连通分支进行讨论否则可对每个连通分支进行讨论,孤立点可根据需要分属孤立点可根据需要分属V1和和V2.设设v0为为G中任意一个顶点中任意一个顶点,令令

14、 V1=v|v V(G)d(v0,v)为偶数为偶数 V2=v|v V(G)d(v0,v)为奇数为奇数d(v0,v)是是v0到到v的最短路径的边数的最短路径的边数(每条边的权为每条边的权为1).V1，V2,V1 V2=,V1 V2=V(G).要证要证V1中任意两点不相邻中任意两点不相邻.21证明证明假若存在假若存在vi,vj V1相邻相邻,记记e=(vi,vj),设设v0到到vi,vj的最短路径分别的最短路径分别为为 i,j,由由 i,j和和e构成一条长度为奇数的回路构成一条长度为奇数的回路.这条回路可这条回路可能是一条复杂回路能是一条复杂回路,可以分解成若干由可以分解成若干由 i,j共有的边构

15、成的共有的边构成的回路回路(实际上是每条边重复一次的路径实际上是每条边重复一次的路径)和由和由 i,j不共有的边不共有的边及及e构成的圈构成的圈.由由 i,j共有的边构成的回路的长度为偶数共有的边构成的回路的长度为偶数,故在故在由由 i,j不共有的边不共有的边(可以还包括可以还包括e)构成的圈中一定有奇圈构成的圈中一定有奇圈,这这与已知条件矛盾与已知条件矛盾.得证得证V1中任意两顶点不相邻中任意两顶点不相邻.由对称性由对称性,V2中也不存在相邻的顶点中也不存在相邻的顶点,得证得证G为二部图为二部图.22最大匹配最大匹配定义定义11.4 设设G=为二部图为二部图,M E,如果如果M中的任意两中的

16、任意两条边都不相邻条边都不相邻,则称则称M是是G的一个的一个匹配匹配.G中边数最多的匹配中边数最多的匹配称作称作最大匹配最大匹配.又设又设|V1|V2|,如果如果M是是G的一个匹配且的一个匹配且|M|=|V1|,则称则称M是是V1到到V2的的完备匹配完备匹配.当当|V2|=|V1|时时,完备匹完备匹配又称作配又称作完美匹配完美匹配例例完备匹配完备匹配完美匹配完美匹配最大匹配最大匹配.23与匹配有关的概念与匹配有关的概念定义定义11.5 设设M是二部图是二部图G=的一个匹配的一个匹配.称称M中的边中的边为为匹配边匹配边,不在不在M中的边为中的边为非匹配边非匹配边.与匹配边相关联的顶点与匹配边相关

17、联的顶点为为饱和点饱和点,不与匹配边相关联的顶点为不与匹配边相关联的顶点为非饱和点非饱和点.G中由匹配中由匹配边和非匹配边交替构成的路径称为边和非匹配边交替构成的路径称为交错路径交错路径,起点和终点都是起点和终点都是非饱和点的交错路径称为非饱和点的交错路径称为可增广的交错路径可增广的交错路径M为为G的完备匹配当且仅当的完备匹配当且仅当V1或或V2中的每个顶点都是饱和点中的每个顶点都是饱和点M为为G的完美匹配当且仅当的完美匹配当且仅当G中的每个顶点都是饱和点中的每个顶点都是饱和点.24可增广的交错路径可增广的交错路径例例左图左图,饱和点饱和点:u1,u3,u4,v1,v2,v3;非饱和点非饱和点

18、:u2,v4;可增广的交错路径可增广的交错路径 :u2v3u4v2u1v4.由由 得到多一条边的匹配得到多一条边的匹配.设设M为为G的一个匹配的一个匹配,是关于是关于M的可增广的交错路径的可增广的交错路径,则则 M =M E()=(M E()(M E()是比是比M多一条边的匹配多一条边的匹配.定理定理11.5 M为为G的最大匹配的最大匹配G中不含中不含M的可增广的交错路径的可增广的交错路径.u1u1u2u2u3u3u4u4v1v2v3v4v1v2v3v4.25Hall定理定理定理定理11.6(Hall定理定理)设二部图设二部图G=,其中其中|V1|V2|,则则 G中存在从中存在从V1到到V2的

19、完备匹配当且仅当的完备匹配当且仅当V1中任意中任意k(1 k|V1|)个顶点至少与个顶点至少与V2中的中的k个顶点相邻个顶点相邻.(相异性条件相异性条件)证证 必要性显然必要性显然.证充分性证充分性.设设M为为G的最大匹配的最大匹配,若若M不是完备不是完备的的,则存在非饱和点则存在非饱和点vx V1.于是于是,存在存在e E1=E M与与vx关联关联,且且V2中与中与vx相邻的顶点都是饱和点相邻的顶点都是饱和点.考虑从考虑从vx出发的尽可能长的出发的尽可能长的所有交错路径所有交错路径,这些交错路径都不是可增广的这些交错路径都不是可增广的,因此每条路径因此每条路径的另一个端点一定是饱和点的另一个

20、端点一定是饱和点,从而全在从而全在V1中中.令令 S=v|v V1且且v在从在从vx出发的交错路径上出发的交错路径上 T=v|v V2且且v在从在从vx出发的交错路径上出发的交错路径上除除vx外外,S和和T中的顶点都是饱和点中的顶点都是饱和点,且由匹配边给出两者之间且由匹配边给出两者之间的一一对应的一一对应,因而因而|S|=|T|+1.这说明这说明V1中有中有|T|+1个顶点只与个顶点只与V2中中|T|个顶点相邻个顶点相邻,与相异性条件矛盾与相异性条件矛盾.26t条件条件定理定理11.7 设二部图设二部图G=,如果存在如果存在t使得使得,V1中每个顶中每个顶点至少关联点至少关联t条边条边,而而

21、V2中每个顶点至多关联中每个顶点至多关联 t 条边条边,则则G 中存中存在在V1到到V2的完备匹配的完备匹配.(t条件条件)证证 V1中任意中任意k(1 k|V1|)个顶点至少关联个顶点至少关联kt条边条边,而而V2中每个顶中每个顶点至多关联点至多关联t条边条边,这这kt条边至少关联条边至少关联V2中中k个顶点个顶点.G满足相异满足相异性条件性条件第第2个图不满足个图不满足t条件条件,但有完备匹配但有完备匹配.例例前两个满足相异性条件前两个满足相异性条件,第第3个不满足个不满足.27一个应用实例一个应用实例例例7 某课题组要从某课题组要从a,b,c,d,e 5人中派人中派3人分别到上海、广州、

22、人分别到上海、广州、香港去开会香港去开会.已知已知a只想去上海，只想去上海，b只想去广州，只想去广州，c,d,e都表示都表示想去广州或香港想去广州或香港.问该课题组在满足个人要求的条件下，共问该课题组在满足个人要求的条件下，共有几种派遣方案？有几种派遣方案？解解 令令G=，其中，其中V1=s,g,x，s,g,x分别表示上海、分别表示上海、广州和香港广州和香港.V2=a,b,c,d,e,E=(u,v)|u V1,v V2,v想去想去u.每个每个V1到到V2的完备匹配给的完备匹配给出一个派遣方案出一个派遣方案,共有共有9种种.如如a到上海到上海,b到广州到广州,c到香到香港港.28(2)是是(1)

23、的平面嵌入，的平面嵌入，(4)是是(3)的平面嵌入的平面嵌入.11.4 平面图平面图定义定义11.6 如果能将无向图如果能将无向图G画在平面上使得除顶点处外无边相画在平面上使得除顶点处外无边相交交,则称则称G是是可平面图可平面图,简称简称平面图平面图.画出的无边相交的图称为画出的无边相交的图称为G的的平面嵌入平面嵌入.无平面嵌入的图称为无平面嵌入的图称为非平面图非平面图例例 (1)(2)(3)(4).29平面图的性质平面图的性质l K5,K3,3都是非平面图（都是非平面图（定理定理11.13）l 平行边与环不影响平面性平行边与环不影响平面性.定理定理11.8 平面图的子图都是平面图平面图的子图

24、都是平面图,非平面图的母图都是非非平面图的母图都是非平面图平面图例如例如,所有度数不超过所有度数不超过4的简单图都是平面图的简单图都是平面图.当当|V1|=1和和2时二部图时二部图G=是平面图是平面图.Kn(n 5)和和Ks,t(s,t 3)都是非平面图都是非平面图.30平面图的面与次数平面图的面与次数定义定义11.7 给定平面图给定平面图G的平面嵌入的平面嵌入,G的边将平面划分成若干的边将平面划分成若干个区域个区域,每个区域都称为每个区域都称为G的一个的一个面面,其中有一个面的面积无其中有一个面的面积无限限,称为称为无限面无限面或或外部面外部面,其余面的面积有限其余面的面积有限,称为称为有限

25、面有限面或或内部面内部面.包围每个面的所有边组成的回路组称为该面的包围每个面的所有边组成的回路组称为该面的边界边界，边界的长度称为该面的边界的长度称为该面的次数次数面面R的次数记为的次数记为deg(R)deg(R1)=1,deg(R2)=3,deg(R3)=2,deg(R0)=8.例例.31次数的性质次数的性质定理定理17.4 平面图平面图各面次数之和等于边数的两倍各面次数之和等于边数的两倍.证证 对每一条边对每一条边e,若若e在两个面的公共边界上在两个面的公共边界上,则在计算这两则在计算这两个面的次数时个面的次数时,e各提供各提供1.而当而当e只在某一个面的边界上出现只在某一个面的边界上出现

26、时时,它必在该面的边界上出现两次它必在该面的边界上出现两次,从而在计算该面的次数时从而在计算该面的次数时,e提供提供2.32极大平面图极大平面图定义定义11.8 G为简单平面图为简单平面图,若在若在G的任意两个不相邻的顶点的任意两个不相邻的顶点之间加一条边所得图为非平面图之间加一条边所得图为非平面图,则称则称G为为极大平面图极大平面图.例如例如,K5,K33删去一条边后是极大平面图删去一条边后是极大平面图 K1,K2,K3,K4都是极大平面图都是极大平面图.定理定理11.10 设设G为为n(n 3)阶简单连通的平面图阶简单连通的平面图,G为极大平面为极大平面图当且仅当图当且仅当G的每个面的次数

27、均为的每个面的次数均为3.证证 现只证必要性现只证必要性.各面次数都大于或等于各面次数都大于或等于3.假如假如deg(Ri)=s 4,若若v1与与v3不相邻不相邻,则在则在Ri内加边内加边(v1,v3)不不破坏平面性破坏平面性,与与G是极大平面图矛盾是极大平面图矛盾,因因而而v1与与v3必相邻必相邻,且边且边(v1,v3)必在必在Ri外部外部.同样地同样地,v2与与v4也相邻且边也相邻且边(v2,v4)在在Ri的的外部外部.于是于是,(v1,v3)与与(v2,v4)相交于相交于Ri的外的外部部,与与G是平面图矛盾是平面图矛盾.33例例 是否是极大平面图是否是极大平面图?定理的应用定理的应用只有

28、只有(3)为极大平面图为极大平面图 (1)(2)(3).34极小非平面图极小非平面图定义定义11.9 若在非平面图若在非平面图G中任意删除一条边中任意删除一条边,所得图为平面图所得图为平面图,则称则称G为为极小非平面图极小非平面图.l K5,K3,3都是极小非平面图都是极小非平面图l 极小非平面图必为简单图极小非平面图必为简单图.35 欧拉公式欧拉公式定理定理11.11 设设G为为n阶阶m条边条边r个面的连通平面图个面的连通平面图,则则n m+r=2证证 对对m做归纳证明做归纳证明.m=0时时,G为平凡图为平凡图,n=1,m=0,r=1,成立成立.设设m=k(k 0)时结论成立时结论成立.当当

29、m=k+1时时,分两者情况讨论分两者情况讨论:(1)G中有一个中有一个1度顶点度顶点v,令令G =G v,仍是连通的仍是连通的,n =n 1,m =m 1=k,r =r.由归纳假设由归纳假设,n m +r =2.于是于是 n m+r=(n +1)(m +1)+r =n m +r =2(2)G中没有中没有1度顶点度顶点,则每一条边都在某两个面的公共边界则每一条边都在某两个面的公共边界上上.任取一条边任取一条边e,令令G =G e,仍连通且仍连通且n =n,m =m 1=k,r =r 1.由归纳假设由归纳假设,n m +r =2.于是于是 n m+r=n (m +1)+(r +1)=n m +r

30、=2.36 欧拉公式的推广欧拉公式的推广推论推论 对于有对于有k个连通分支的平面图个连通分支的平面图G,有有n m+r=k+1 其中其中n,m,r分别为分别为G的顶点数的顶点数,边数和面数边数和面数.证证 设设G的连通分支为的连通分支为G1,G2,Gk,由欧拉公式由欧拉公式 ni mi+ri=2,i=1,2,k.G的面数的面数 .于是，于是，整理得整理得 n m+r=k+1 kiikrr1)1(1)(21 krmnrmnkkiiii.37)2(2 nllm)2()deg(21nmlrlRmrii )2(2 nllm解得解得 与欧拉公式有关的定理与欧拉公式有关的定理定理定理11.12 设设G为连

31、通的平面图为连通的平面图,每个面的次数至少为每个面的次数至少为l 3，则，则 证证 由定理由定理11.9及及欧拉公式欧拉公式,定理定理11.13 K5,K3,3都是非平面图都是非平面图.证证 假设假设K5是平面图是平面图,K5无环和平行边无环和平行边,每个面的次数均大于等每个面的次数均大于等于于3.应该有应该有矛盾矛盾.9)25(23310 .38证证(续续)假设假设K3,3是平面图是平面图,K3,3中最短圈的长度为中最短圈的长度为4,每个面的每个面的次数均大于等于次数均大于等于4.应该有应该有矛盾矛盾.8)26(2449 定理定理11.14 设设G为为n(n 3)阶阶m条边的极大平面图条边的

32、极大平面图,则则m=3n 6.证证 极大平面图是连通图极大平面图是连通图,由欧拉公式得由欧拉公式得 r=2+m n.又由定理又由定理11.10的必要性的必要性,G的每个面的次数均为的每个面的次数均为3,所以所以2m=3r.得得m=3n 6推论推论 设设G是是n(n 3)阶阶m条边的简单平面图条边的简单平面图,则则 m 3n 6与欧拉公式有关的定理与欧拉公式有关的定理.39如果简单连通平面图如果简单连通平面图G的每个面的次数都等于的每个面的次数都等于3,则则G为极大平为极大平面图面图.证证 由定理由定理11.9,2m=3r由欧拉公式由欧拉公式,r=2+m n 整理得整理得 m=3n 6若若G不是

33、极大平面图不是极大平面图,则则G中存在不相邻的顶点中存在不相邻的顶点u,v,使得使得G =G(u,v)还是简单平面图还是简单平面图,而而G 的边数的边数m =m+1,n =n,故故 m 3n 6与定理与定理11.14的推论矛盾的推论矛盾定理定理11.10充分性证明充分性证明.40 同胚同胚定义定义11.10 设设e=(u,v)为图为图G的一条边的一条边,在在G中删除中删除e,增加新的增加新的顶点顶点w,使使u,v均与均与w相邻相邻,称为在称为在G中中插入插入2度顶点度顶点w.设设w为为G中一个中一个2度顶点度顶点,w与与u,v相邻相邻,删除删除w,增加新边增加新边(u,v),称为在称为在G中中

34、消去消去2度顶点度顶点w.若两个图若两个图G1与与G2同构同构,或通过反复插入、消去或通过反复插入、消去2度顶点后同度顶点后同构构,则称则称G1与与G2同胚同胚例例 插入与消去插入与消去2度顶点度顶点收缩边收缩边.41库拉图斯基定理库拉图斯基定理定理定理11.15 G是平面图是平面图 G中不含与中不含与K5和和K3,3同胚的子图同胚的子图.定理定理11.16 G是平面图是平面图 G中无可收缩为中无可收缩为K5或或K3,3的子图的子图.例例8 证明下边两个图为非平面图证明下边两个图为非平面图.与与K5同胚同胚 。与与K3,3同胚同胚 。.42例题例题例例9 证明彼得森图为非平面图证明彼得森图为非

35、平面图.与与K5同胚同胚收缩收缩(a,f),(b,g),(c,h),(d,i),(e,j)与与K3,3同胚同胚收缩收缩(b,g),(c,h),(d,i),(e,j).43点着色点着色定义定义11.11 设无向图设无向图G无环无环,对对G的每个顶点涂一种颜色的每个顶点涂一种颜色,使相使相邻的顶点涂不同的颜色邻的顶点涂不同的颜色,称为图称为图G的一种的一种点着色点着色,简称简称着色着色.若若能用能用k种颜色给种颜色给G的顶点着色，的顶点着色，则称则称G是是k-可着色的可着色的图的着色问题图的着色问题:要用尽可能少的颜色给图着色要用尽可能少的颜色给图着色.偶圈用偶圈用2种颜色种颜色,奇圈用奇圈用3种

36、种.奇阶轮图用奇阶轮图用3种种,偶阶轮图用偶阶轮图用4种种.例例11 G是是2-可着色的当且仅当可着色的当且仅当G是二部图是二部图.1212121232123323123243例例10.44应用应用1.有有n项工作项工作,每项工作需要一天的时间每项工作需要一天的时间,有些工作不能同时有些工作不能同时进行进行,问至少需要几天才能完成所有的工作问至少需要几天才能完成所有的工作?顶点表示工作顶点表示工作,两点之间有一条边两点之间有一条边这这两项工作不能同时进行两项工作不能同时进行.工作的时间工作的时间安排对应于这个图的点着色安排对应于这个图的点着色:着同一种颜色的顶点对应的工着同一种颜色的顶点对应的

37、工作可安排在同一天作可安排在同一天,所需的最少天数是所需要的最少颜色数所需的最少天数是所需要的最少颜色数.2.寄存器分配寄存器分配.计算机有计算机有k个寄存器个寄存器,要给每一个变量分配一要给每一个变量分配一个寄存器个寄存器.如果两个变量要在同一时刻使用如果两个变量要在同一时刻使用,则不能把它们分则不能把它们分配给同一个寄存器配给同一个寄存器.每一个变量是一个顶点每一个变量是一个顶点,如果两个变量要如果两个变量要在同一时刻使用在同一时刻使用,则用一条边连接这两个变量则用一条边连接这两个变量.这个图的这个图的k-着着色对应给变量分配寄存器的一种安全方式色对应给变量分配寄存器的一种安全方式:给着同

38、一种颜色给着同一种颜色的变量分配同一个寄存器的变量分配同一个寄存器.45应用应用3.无线交换设备的波长分配无线交换设备的波长分配.有有n台设备和台设备和k个发射波长个发射波长,要给要给每一台设备分配一个波长每一台设备分配一个波长.如果两台设备靠得太近如果两台设备靠得太近,则不能给则不能给它们分配相同的波长它们分配相同的波长.以设备为顶点以设备为顶点,如果两台设备靠得太近如果两台设备靠得太近,则用一条边连接它们则用一条边连接它们.这个图的这个图的k-着色给出一个波长分配方案着色给出一个波长分配方案:给着同一种颜色的设备分配同一个波长给着同一种颜色的设备分配同一个波长.46地图着色与对偶图地图着色

39、与对偶图地图地图:连通无桥平面图的平面嵌入连通无桥平面图的平面嵌入.每一个面是一个国家每一个面是一个国家(或省或省,市市,区等区等).若两个国家有公共的边界，则称这两个国家是相邻若两个国家有公共的边界，则称这两个国家是相邻的的.对地图的每个国家涂上一种颜色，使相邻的国家涂不同对地图的每个国家涂上一种颜色，使相邻的国家涂不同的颜色，称为对地图的面着色的颜色，称为对地图的面着色,简称简称地图着色地图着色.地图着色问题地图着色问题:用尽可能少的颜色给地图着色用尽可能少的颜色给地图着色.定义定义11.12 设设G是一个平面嵌入是一个平面嵌入,构造图构造图G*如下如下:在在G的每一个的每一个面面Ri中放

40、置一个顶点中放置一个顶点vi*.设设e为为G的一条边的一条边,若若e在在G的面的面Ri与与Rj的公共边界上的公共边界上,则作边则作边e*=(vi*,vj*)与与e相交相交,且不与其他任何边且不与其他任何边相交相交.若若e为为G中的桥且在面中的桥且在面Ri的边界上的边界上,则作以则作以vi*为端点的环为端点的环e*=(vi*,vi*).称称G*为为G的的对偶图对偶图.47实例实例实线和空心点是平面嵌入实线和空心点是平面嵌入,虚线和实心点是对偶图虚线和实心点是对偶图.注意注意:这两个平面嵌入是同一个平面图的平面嵌入这两个平面嵌入是同一个平面图的平面嵌入.48四色定理四色定理四色猜想四色猜想(19世

41、纪世纪50年代年代,德摩根德摩根)五色定理五色定理(1890年年,希伍德希伍德)四色定理四色定理(1976年年,阿佩尔与黑肯阿佩尔与黑肯)定理定理11.17 任何平面图都是任何平面图都是4-可着色的可着色的.49第十一章第十一章 习题课习题课 主要内容主要内容l 欧拉通路与欧拉回路欧拉通路与欧拉回路,欧拉图与半欧拉图及判别欧拉图与半欧拉图及判别l 哈密顿通路与哈密顿回路哈密顿通路与哈密顿回路,哈密顿图与半哈密顿图及判别哈密顿图与半哈密顿图及判别l 货郎问题货郎问题l 二部图及其判别二部图及其判别l 二部图匹配及相关概念二部图匹配及相关概念l 二部图最大匹配的充要条件二部图最大匹配的充要条件,存

42、在完备匹配的条件存在完备匹配的条件l 平面图及其性质平面图及其性质(欧拉公式欧拉公式)l 平面图的判别平面图的判别l 着色问题着色问题l 地图着色与平面图的对偶图地图着色与平面图的对偶图l 四色定理四色定理l 应用应用.50基本要求基本要求基本要求基本要求l 深刻理解欧拉图深刻理解欧拉图,半欧拉图半欧拉图,哈密顿图哈密顿图,半哈密顿图的定义半哈密顿图的定义l 掌握欧拉图掌握欧拉图,半欧拉图的判别半欧拉图的判别l 会用哈密顿图与半哈密顿图的必要条件和充分条件会用哈密顿图与半哈密顿图的必要条件和充分条件l 会一笔画出欧拉回路会一笔画出欧拉回路l 了解货郎问题了解货郎问题l 深刻理解二部图的定义深刻

43、理解二部图的定义,掌握二部图的判别掌握二部图的判别l 深刻理解二部图匹配及相关概念深刻理解二部图匹配及相关概念l 了解二部图最大匹配了解二部图最大匹配的充要条件的充要条件,会用存在完备匹配的条会用存在完备匹配的条件件(Hall定理与定理与t条件条件).51基本要求基本要求l 深刻理解平面图及相关的概念深刻理解平面图及相关的概念l 牢记极大平面图的主要性质和判别方法牢记极大平面图的主要性质和判别方法l 熟记欧拉公式及推广形式，并能用欧拉公式及推广形式熟记欧拉公式及推广形式，并能用欧拉公式及推广形式证明有关定理与命题证明有关定理与命题l 会用库拉图斯基定理证明非平面图会用库拉图斯基定理证明非平面图

44、 l 了解对偶图的概念了解对偶图的概念l 了解着色问题了解着色问题,地图着色问题和四色定理地图着色问题和四色定理l 会用上述概念和有关定理解决简单的实际问题会用上述概念和有关定理解决简单的实际问题.521.设设G为为n(n 2)阶无向欧拉图阶无向欧拉图,证明证明G中无桥中无桥.证二证二 用反证法用反证法.假设假设e=(u,v)是桥是桥,则则G e产生两个连通分支产生两个连通分支G1,G2,不妨设不妨设u在在G1中中,v在在G2中中.G中没有奇度顶点中没有奇度顶点,而删除而删除e,只使只使u,v 的度数各减的度数各减1,因而因而G1(G2)中只含一个奇度顶点中只含一个奇度顶点,与任与任何图中奇度

45、顶点的个数是偶数矛盾何图中奇度顶点的个数是偶数矛盾.练习练习1证一证一 设设C为为G中一条欧拉回路中一条欧拉回路,e E(G),e在在C上上,C e 连通连通,G e也连通也连通,所以所以e不为桥不为桥.532.证明右图不是哈密顿图证明右图不是哈密顿图.证一证一 取取 V1=a,c,e,h,j,l，p(G V1)=7 6=|V1|练习练习 2证二证二 G为二部图为二部图,V1=a,c,e,h,j,l,V2=b,d,f,g,i,k,m,|V1|V2|.证三证三 n=13,m=21.h,l,j为为4度顶点度顶点,a,c,e为为3度顶点度顶点,且它且它们关联不相同的边们关联不相同的边.而在哈密顿回路

46、上而在哈密顿回路上,每个顶点关联两条边每个顶点关联两条边,于是可能用于哈密顿回路的边至多有于是可能用于哈密顿回路的边至多有21(3 2+3 1)=12.12条条边不可能构成经过边不可能构成经过13个顶点的回路个顶点的回路.543某次国际会议某次国际会议8人参加人参加,已知每人至少与其余已知每人至少与其余7人中的人中的4人人能用相同的语言能用相同的语言,问服务员能否将他们安排在同一张圆桌就问服务员能否将他们安排在同一张圆桌就座座,使得每个人都能与两边的人交谈？使得每个人都能与两边的人交谈？解解 做无向图做无向图G=,其中其中V=v|v为与会者为与会者，E=(u,v)|u,v V,u与与v有能用相

47、同的语言有能用相同的语言,且且u v.G为简单图且为简单图且 v V,d(v)4.于是于是,u,v V,d(u)+d(v)8,故故G为哈密顿图为哈密顿图.服务员在服务员在G中找一条哈密顿回路中找一条哈密顿回路,按回路按回路中相邻关系安排座位即可中相邻关系安排座位即可.练习练习 3.554.某公司招聘了某公司招聘了3名大学毕业生名大学毕业生,有有5个部门需要人个部门需要人.部门领导部门领导与毕业生交谈后与毕业生交谈后,双方都愿意的结果如表所示双方都愿意的结果如表所示.如果每个部门如果每个部门只能接收一名毕业生只能接收一名毕业生,问这问这3名毕业生都能到他满意的部门工名毕业生都能到他满意的部门工作

48、吗作吗?试给出分配方案试给出分配方案.练习练习 4解解 作二部图作二部图G=部门部门1 部门部门2 部门部门3 部门部门4 部门部门5毕业生毕业生A 毕业生毕业生B 毕业生毕业生C 1ABC2345一个分配方案是一个分配方案是G的一个匹配的一个匹配.G满足满足t条件条件,t=3,有完备匹配有完备匹配.如如,A1,B 2,C 3;A 3,B 2,C 5等等.56练习练习5解解 设设G的阶数的阶数,边数边数,面数分别为面数分别为n,m,r.(1)用反证法用反证法.假设所有面的次数大于等于假设所有面的次数大于等于5,由欧拉公式得由欧拉公式得 2m 5r=5(2+m n)由由(G)3及握手定理有及握手

49、定理有 2m 3n 得得 m 30又有又有 r=2+m n 12 与又可得与又可得 m30,矛盾矛盾.5.设设G是连通的简单平面图是连通的简单平面图,面数面数r12,(G)3.(1)证明证明G中存在次数中存在次数 4的面的面.(2)举例说明当举例说明当r=12时时,(1)中结论不真中结论不真.(2)正十二面体是一个反例正十二面体是一个反例.576.设设G是阶数是阶数 11的非平凡简单无向图的非平凡简单无向图,证明证明G和和 不可能不可能全是平面图全是平面图.G证证 用反证法用反证法.假设假设 与与G 都是平面图都是平面图,则则G与与 的边数的边数m,m 应满足应满足 不妨设不妨设 GG2)1(

50、nnmm4)1(nnm由于由于G是平面图是平面图,又有又有 m 3n 6 得得 n2 13n+24 0 解得解得 2 n 10 与与n 11矛盾矛盾.练习练习6.587.证明下图为非平面图证明下图为非平面图练习练习7证一证一 含子图含子图K3,3:删去顶点删去顶点a和边和边(c,d)证二证二 含与含与K5同胚的同胚的子图子图:删去删去(a,f),收缩收缩(a,e)和和(f,g).59练习练习88.给下图着色至少要用几种颜色给下图着色至少要用几种颜色?解解 由于由于a,b,c 彼此相邻彼此相邻,至少要用至少要用3种颜色种颜色,设它们分别着设它们分别着颜色颜色1,2,3.最少还要用这三种颜色给最少