第十一章-几种特殊的图-离散数学及其应用课件.ppt

《第十一章-几种特殊的图-离散数学及其应用课件.ppt》由会员分享，可在线阅读，更多相关《第十一章-几种特殊的图-离散数学及其应用课件.ppt（60页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、：说明：规定平凡图为欧拉图规定平凡图为欧拉图.环不影响图的欧拉性环不影响图的欧拉性.4欧拉图实例欧拉图实例欧拉图欧拉图不是不是半欧拉图半欧拉图欧拉图欧拉图不是不是半欧拉图半欧拉图6Fleury算法算法算法：算法：(1)任取任取v0 V(G),令令P0=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

3、 e1,e2,ei 中的桥中的桥.设设ei+1=(vi,vi+1),把把ei+1vi+1加入加入Pi.(3)令令i=i+1,返回返回(2).7实例实例一笔画出一条欧拉回路一笔画出一条欧拉回路8实例实例一笔画出一条欧拉回路一笔画出一条欧拉回路10哈密顿图与半哈密顿图哈密顿图与半哈密顿图定义定义11.2 经过图中所有顶点一次且仅一次的通路称作经过图中所有顶点一次且仅一次的通路称作哈密顿哈密顿通路通路.经过图中所有顶点一次且仅一次的回路称作经过图中所有顶点一次且仅一次的回路称作哈密顿回哈密顿回路路.具有哈密顿回路的图称作具有哈密顿回路的图称作哈密顿图哈密顿图.具有哈密顿通路且无具有哈密顿通路且无哈密

4、顿回路的图称作哈密顿回路的图称作半哈密顿图半哈密顿图.规定规定:平凡图是哈密顿图平凡图是哈密顿图.哈密顿图哈密顿图半哈密顿图半哈密顿图哈密顿图哈密顿图例例不是不是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

5、V1)|V1|+1证证 设设 为从为从u到到v的哈密顿通路，令的哈密顿通路，令G =G(u,v)，则，则G 为哈密顿图为哈密顿图.于是于是 p(G V1)=p(G V1(u,v)p(G V1)+1|V1|+113例题例题例例3 设设G为为n阶无向连通简单图，若阶无向连通简单图，若G中有割点或桥，则中有割点或桥，则G不不是哈密顿图是哈密顿图.证证 设设v为割点，则为割点，则 p(G v)2|v|=1.K2有桥，它显然不是哈密顿图有桥，它显然不是哈密顿图.除除K2外，其他有桥的连外，其他有桥的连通图均有割点通图均有割点.15判断是否为哈密顿图判断是否为哈密顿图 判断是否为判断是否为(半半)哈密顿图

6、至今还是一个难题哈密顿图至今还是一个难题.(1)观察出一条哈密顿回路或哈密顿通路观察出一条哈密顿回路或哈密顿通路.(2)证明满足充分条件证明满足充分条件.(3)证明不满足必要条件证明不满足必要条件.例例4 证明右图证明右图(周游世界问题周游世界问题)是哈密顿图是哈密顿图证证 a b c d e f g h i j k l m n o p q r s t a是一条哈密顿回路是一条哈密顿回路.注意，此图不满足定理注意，此图不满足定理11.3推论的条件推论的条件.例例5 完全图完全图Kn(n 3)是哈密顿图是哈密顿图.证证 任何两个顶点任何两个顶点u,v，d(u)+d(v)=2(n 1)n16货郎问

7、题货郎问题货货郎郎问题问题:有有n个城市个城市,给给定城市之定城市之间间道路的道路的长长度度(长长度可以度可以为为,对应这对应这两个城市之两个城市之间间无交通无交通线线).货货郎从某个城市出郎从某个城市出发发,要要经过经过每个城市一次且每个城市一次且仅仅一次一次,最后回到出最后回到出发发的城市的城市,问问如何走如何走才能使他走的路才能使他走的路线线最短最短?图论图论方法描述如下方法描述如下:设设G=为一个为一个n阶完全带权图阶完全带权图Kn,各边的权非负各边的权非负,且可能为且可能为.求求G中的一条最短的哈密顿回路中的一条最短的哈密顿回路.不计出发点和方向不计出发点和方向,Kn(n 3)中有中

8、有(n 1)!/2 条不同的哈密顿回条不同的哈密顿回路路1811.3 二部图与匹配二部图与匹配定义定义11.3 设设 G=为一个无向图为一个无向图,若能将若能将 V分成分成 V1和和V2(V1 V2=V,V1 V2=),使得使得 G 中的每条边的两个端点都是一中的每条边的两个端点都是一个属于个属于V1,另一个属于另一个属于V2,则称则称 G 为为二部图二部图(或称或称二分图二分图,偶偶图图),称称V1和和V2为为互补顶点子集互补顶点子集,常将二部图常将二部图G记为记为.又若又若G是简单二部图是简单二部图,V1中每个顶点均与中每个顶点均与V2中所有的顶点相邻，中所有的顶点相邻，则称则称G为为完全

9、二部图完全二部图,记为记为 Kr,s,其中其中r=|V1|,s=|V2|.19实例实例例例K2,3K3,320二部图的判别法二部图的判别法定理定理11.4 无向无向图图G=是二部是二部图图当且当且仅仅当当G中无奇圈中无奇圈.证证 必要性必要性.若若G中无圈中无圈,结论结论成立成立.若若G中有圈中有圈,设设G中的一个中的一个圈圈C=v1v2vlv1,l2.不妨不妨设设v1 V1,v1,v2,vl 依次交替属于依次交替属于V1,V2且且vl V2,因而因而l为为偶数偶数.得得证证C为为偶圈偶圈充分性充分性.不妨不妨设设G为连为连通通图图,否否则则可可对对每个每个连连通分支通分支进进行行讨论讨论,孤

10、立点可根据需要分属孤立点可根据需要分属V1和和V2.设设v0为为G中任意一个中任意一个顶顶点点,令令 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构成一条构成一条长长度度为为奇数的回路奇数的回路.这这条

11、回路可条回路可能是一条复能是一条复杂杂回路回路,可以分解成若干由可以分解成若干由 i,j共有的共有的边边构成的构成的回路回路(实际实际上是每条上是每条边边重复一次的路径重复一次的路径)和由和由 i,j不共有的不共有的边边及及e构成的圈构成的圈.由由 i,j共有的共有的边边构成的回路的构成的回路的长长度度为为偶数偶数,故在故在由由 i,j不共有的不共有的边边(可以可以还还包括包括e)构成的圈中一定有奇圈构成的圈中一定有奇圈,这这与已知条件矛盾与已知条件矛盾.得得证证V1中任意两中任意两顶顶点不相点不相邻邻.由由对对称性称性,V2中也不存在相中也不存在相邻邻的的顶顶点点,得得证证G为为二部二部图图

12、22最大匹配最大匹配定定义义11.4 设设G=为为二部二部图图,M E,如果如果M中的任意中的任意两两条条边边都不相都不相邻邻,则则称称M是是G的一个的一个匹配匹配.G中中边边数最多的匹配数最多的匹配称作称作最大匹配最大匹配.又又设设|V1|V2|,如果如果M是是G的一个匹配且的一个匹配且|M|=|V1|,则则称称M是是V1到到V2的的完完备备匹配匹配.当当|V2|=|V1|时时,完完备备匹匹配又称作配又称作完美匹配完美匹配例例完备匹配完备匹配完美匹配完美匹配最大匹配最大匹配24可增广的交错路径可增广的交错路径例例左图左图,饱和点饱和点:u1,u3,u4,v1,v2,v3;非饱和点非饱和点:u

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

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

15、饱和点和点,从而全在从而全在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条条边边,而而V2中

16、每个中每个顶顶点至多关点至多关联联 t 条条边边,则则G 中存中存在在V1到到V2的完的完备备匹配匹配.(t条件条件)证证 V1中任意中任意k(1 k|V1|)个个顶顶点至少关点至少关联联kt条条边边,而而V2中每个中每个顶顶点至多关点至多关联联t条条边边,这这kt条条边边至少关至少关联联V2中中k个个顶顶点点.G满满足相异足相异性条件性条件第第2个个图图不不满满足足t条件条件,但有完但有完备备匹配匹配.例例前两个满足相异性条件前两个满足相异性条件,第第3个不满足个不满足28(2)是是(1)的平面嵌入，的平面嵌入，(4)是是(3)的平面嵌入的平面嵌入.11.4 平面图平面图定定义义11.6 如

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

18、单图简单图都是平面都是平面图图.当当|V1|=1和和2时时二部二部图图G=是平面是平面图图.Kn(n 5)和和Ks,t(s,t 3)都是非平面都是非平面图图.31次数的性质次数的性质定理定理17.4 平面图平面图各面次数之和等于各面次数之和等于边边数的两倍数的两倍.证证 对对每一条每一条边边e,若若e在两个面的公共在两个面的公共边边界上界上,则则在在计计算算这这两两个面的次数个面的次数时时,e各提供各提供1.而当而当e只在某一个面的只在某一个面的边边界上出界上出现现时时,它必在它必在该该面的面的边边界上出界上出现现两次两次,从而在从而在计计算算该该面的次数面的次数时时,e提供提供232极大平面

19、图极大平面图定义定义11.8 G为简单平面图为简单平面图,若在若在G的任意两个不相邻的顶点的任意两个不相邻的顶点之间加一条边所得图为非平面图之间加一条边所得图为非平面图,则称则称G为为极大平面图极大平面图.例如例如,K5,K33删去一条边后是极大平面图删去一条边后是极大平面图 K1,K2,K3,K4都是极大平面图都是极大平面图.定理定理11.10 设设G为为n(n 3)阶简单连通的平面图阶简单连通的平面图,G为极大平面为极大平面图当且仅当图当且仅当G的每个面的次数均为的每个面的次数均为3.证证 现现只只证证必要性必要性.各面次数都大于或等于各面次数都大于或等于3.假如假如deg(Ri)=s 4

20、,若若v1与与v3不相不相邻邻,则则在在Ri内加内加边边(v1,v3)不不破坏平面性破坏平面性,与与G是极大平面是极大平面图图矛盾矛盾,因因而而v1与与v3必相必相邻邻,且且边边(v1,v3)必在必在Ri外部外部.同同样样地地,v2与与v4也相也相邻邻且且边边(v2,v4)在在Ri的的外部外部.于是于是,(v1,v3)与与(v2,v4)相交于相交于Ri的外的外部部,与与G是平面是平面图图矛盾矛盾.33例例 是否是极大平面图是否是极大平面图?定理的应用定理的应用只有只有(3)为极大平面图为极大平面图 (1)(2)(3)34极小非平面图极小非平面图定义定义11.9 若在非平面图若在非平面图G中任意

21、删除一条边中任意删除一条边,所得图为平面图所得图为平面图,则称则称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)时结论时结论成立成立.当当m=k+1时时,分两者情况分两者情况讨论讨论:(1)G中有一个中有一个1度度顶顶点点v,令令G =G v,仍是仍是连连通的通的,n =n

22、 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 =236 欧拉公式的推广欧拉公式的推广推推论论 对对于有于有k个个连连通分支的平面通分支的平面图图G,有有n m+r=k+1 其中其中n

23、,m,r分分别为别为G的的顶顶点数点数,边边数和面数数和面数.证证 设设G的的连连通分支通分支为为G1,G2,Gk,由欧拉公式由欧拉公式 ni mi+ri=2,i=1,2,k.G的面数的面数 .于是，于是，整理得整理得 n m+r=k+137解得解得 与欧拉公式有关的定理与欧拉公式有关的定理定理定理11.12 设设G为连通的平面图为连通的平面图,每个面的次数至少为每个面的次数至少为l 3，则，则 证证 由定理由定理11.9及及欧拉公式欧拉公式,定理定理11.13 K5,K3,3都是非平面图都是非平面图.证证 假假设设K5是平面是平面图图,K5无无环环和平行和平行边边,每个面的次数均大于等每个面

24、的次数均大于等于于3.应该应该有有矛盾矛盾.38证证(续续)假假设设K3,3是平面是平面图图,K3,3中最短圈的中最短圈的长长度度为为4,每个面的每个面的次数均大于等于次数均大于等于4.应该应该有有矛盾矛盾.定理定理11.14 设设G为为n(n 3)阶阶m条边的极大平面图条边的极大平面图,则则m=3n 6.证证 极大平面图是连通图极大平面图是连通图,由欧拉公式得由欧拉公式得 r=2+m n.又由定又由定理理11.10的必要性的必要性,G的每个面的次数均为的每个面的次数均为3,所以所以2m=3r.得得m=3n 6推论推论 设设G是是n(n 3)阶阶m条边的简单平面图条边的简单平面图,则则 m 3

25、n 6与欧拉公式有关的定理与欧拉公式有关的定理39如果如果简单连简单连通平面通平面图图G的每个面的次数都等于的每个面的次数都等于3,则则G为为极大平极大平面面图图.证证 由定理由定理11.9,2m=3r由欧拉公式由欧拉公式,r=2+m n 整理得整理得 m=3n 6若若G不是极大平面不是极大平面图图,则则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

26、)为图为图G的一条的一条边边,在在G中中删删除除e,增加新的增加新的顶顶点点w,使使u,v均与均与w相相邻邻,称称为为在在G中中插入插入2度度顶顶点点w.设设w为为G中中一个一个2度度顶顶点点,w与与u,v相相邻邻,删删除除w,增加新增加新边边(u,v),称称为为在在G中中消去消去2度度顶顶点点w.若两个若两个图图G1与与G2同构同构,或通或通过过反复插入、消去反复插入、消去2度度顶顶点后同点后同构构,则则称称G1与与G2同胚同胚例例 插入与消去插入与消去2度顶点度顶点收缩边收缩边41库拉图斯基定理库拉图斯基定理定理定理11.15 G是平面图是平面图 G中不含与中不含与K5和和K3,3同胚的子

27、图同胚的子图.定理定理11.16 G是平面图是平面图 G中无可收缩为中无可收缩为K5或或K3,3的子图的子图.例例8 证明下边两个图为非平面图证明下边两个图为非平面图.与与K5同胚同胚 。与与K3,3同胚同胚 。42例题例题例例9 证明彼得森图为非平面图证明彼得森图为非平面图.与与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的每个的每个顶顶点涂一种点涂一种颜颜色色,使相使相邻邻的的顶顶点涂不同的点涂不同的颜颜色色,称称

28、为图为图G的一种的一种点着色点着色,简简称称着色着色.若若能用能用k种种颜颜色色给给G的的顶顶点着色，点着色，则则称称G是是k-可着色的可着色的图图的着色的着色问题问题:要用尽可能少的要用尽可能少的颜颜色色给图给图着色着色.偶圈用偶圈用2种种颜颜色色,奇圈用奇圈用3种种.奇奇阶轮图阶轮图用用3种种,偶偶阶轮图阶轮图用用4种种.例例11 G是是2-可着色的当且可着色的当且仅仅当当G是二部是二部图图.1212121232123323123243例例1044应用应用1.有有n项项工作工作,每每项项工作需要一天的工作需要一天的时间时间,有些工作不能同有些工作不能同时进时进行行,问问至少需要几天才能完成

29、所有的工作至少需要几天才能完成所有的工作?顶顶点表示工作点表示工作,两两点之点之间间有一条有一条边边这这两两项项工作不能同工作不能同时进时进行行.工作的工作的时间时间安排安排对应对应于于这这个个图图的点着色的点着色:着同一种着同一种颜颜色的色的顶顶点点对应对应的工作可的工作可安排在同一天安排在同一天,所需的最少天数是所需要的最少所需的最少天数是所需要的最少颜颜色数色数.2.寄存器分配寄存器分配.计计算机有算机有k个寄存器个寄存器,要要给给每一个每一个变变量分配一个量分配一个寄存器寄存器.如果两个如果两个变变量要在同一量要在同一时时刻使用刻使用,则则不能把它不能把它们们分配分配给给同一个寄存器同

30、一个寄存器.每一个每一个变变量是一个量是一个顶顶点点,如果两个如果两个变变量要在量要在同一同一时时刻使用刻使用,则则用一条用一条边连边连接接这这两个两个变变量量.这这个个图图的的k-着色着色对应给变对应给变量分配寄存器的一种安全方式量分配寄存器的一种安全方式:给给着同一种着同一种颜颜色的色的变变量分配同一个寄存器量分配同一个寄存器.45应用应用3.无无线线交交换设备换设备的波的波长长分配分配.有有n台台设备设备和和k个个发发射波射波长长,要要给给每一台每一台设备设备分配一个波分配一个波长长.如果两台如果两台设备设备靠得太近靠得太近,则则不能不能给给它它们们分配相同的波分配相同的波长长.以以设备

31、为顶设备为顶点点,如果两台如果两台设备设备靠得太近靠得太近,则则用一条用一条边连边连接它接它们们.这这个个图图的的k-着色着色给给出一个波出一个波长长分配方案分配方案:给给着同一种着同一种颜颜色的色的设备设备分配同一个波分配同一个波长长.46地图着色与对偶图地图着色与对偶图地地图图:连连通无通无桥桥平面平面图图的平面嵌入的平面嵌入.每一个面是一个国家每一个面是一个国家(或省或省,市市,区等区等).若两个国家有公共的若两个国家有公共的边边界，界，则则称称这这两个国家是相两个国家是相邻邻的的.对对地地图图的每个国家涂上一种的每个国家涂上一种颜颜色，使相色，使相邻邻的国家涂不同的的国家涂不同的颜颜色

32、，称色，称为对为对地地图图的面着色的面着色,简简称称地地图图着色着色.地地图图着色着色问题问题:用尽可能少的用尽可能少的颜颜色色给给地地图图着色着色.定定义义11.12 设设G是一个平面嵌入是一个平面嵌入,构造构造图图G*如下如下:在在G的每一个的每一个面面Ri中放置一个中放置一个顶顶点点vi*.设设e为为G的一条的一条边边,若若e在在G的面的面Ri与与Rj的公共的公共边边界上界上,则则作作边边e*=(vi*,vj*)与与e相交相交,且不与其他任何且不与其他任何边边相交相交.若若e为为G中的中的桥桥且在面且在面Ri的的边边界上界上,则则作以作以vi*为为端点的端点的环环e*=(vi*,vi*)

33、.称称G*为为G的的对对偶偶图图.47实例实例实线和空心点是平面嵌入实线和空心点是平面嵌入,虚线和实心点是对偶图虚线和实心点是对偶图.注意注意:这两个平面嵌入是同一个平面图的平面嵌入这两个平面嵌入是同一个平面图的平面嵌入.48四色定理四色定理四色猜想四色猜想(19世世纪纪50年代年代,德摩根德摩根)五色定理五色定理(1890年年,希伍德希伍德)四色定理四色定理(1976年年,阿佩阿佩尔尔与黑肯与黑肯)定理定理11.17 任何平面任何平面图图都是都是4-可着色的可着色的.49第十一章第十一章 习题课习题课 主要内容主要内容l欧拉通路与欧拉回路欧拉通路与欧拉回路,欧拉图与半欧拉图及判别欧拉图与半欧

34、拉图及判别l哈密顿通路与哈密顿回路哈密顿通路与哈密顿回路,哈密顿图与半哈密顿图及判别哈密顿图与半哈密顿图及判别l货郎问题货郎问题l二部图及其判别二部图及其判别l二部图匹配及相关概念二部图匹配及相关概念l二部图最大匹配的充要条件二部图最大匹配的充要条件,存在完备匹配的条件存在完备匹配的条件l平面图及其性质平面图及其性质(欧拉公式欧拉公式)l平面图的判别平面图的判别l着色问题着色问题l地图着色与平面图的对偶图地图着色与平面图的对偶图l四色定理四色定理l应用应用50基本要求基本要求基本要求基本要求l深刻理解欧拉图深刻理解欧拉图,半欧拉图半欧拉图,哈密顿图哈密顿图,半哈密顿图的定义半哈密顿图的定义l掌

35、握欧拉图掌握欧拉图,半欧拉图的判别半欧拉图的判别l会用哈密顿图与半哈密顿图的必要条件和充分条件会用哈密顿图与半哈密顿图的必要条件和充分条件l会一笔画出欧拉回路会一笔画出欧拉回路l了解货郎问题了解货郎问题l深刻理解二部图的定义深刻理解二部图的定义,掌握二部图的判别掌握二部图的判别l深刻理解二部图匹配及相关概念深刻理解二部图匹配及相关概念l了解二部图最大匹配了解二部图最大匹配的充要条件的充要条件,会用存在完会用存在完备备匹配的条匹配的条件件(Hall定理与定理与t条件条件)51基本要求基本要求l深刻理解平面图及相关的概念深刻理解平面图及相关的概念l牢记极大平面图的主要性质和判别方法牢记极大平面图的

36、主要性质和判别方法l熟记欧拉公式及推广形式，并能用欧拉公式及推广形式证熟记欧拉公式及推广形式，并能用欧拉公式及推广形式证明有关定理与命题明有关定理与命题l会用库拉图斯基定理证明非平面图会用库拉图斯基定理证明非平面图 l了解对偶图的概念了解对偶图的概念l了解着色问题了解着色问题,地图着色问题和四色定理地图着色问题和四色定理l会用上述概念和有关定理解决简单的实际问题会用上述概念和有关定理解决简单的实际问题521.设设G为为n(n 2)阶无向欧拉图阶无向欧拉图,证明证明G中无桥中无桥.证二证二 用反证法用反证法.假设假设e=(u,v)是桥是桥,则则G e产生两个连通分支产生两个连通分支G1,G2,不

37、妨设不妨设u在在G1中中,v在在G2中中.G中没有奇度顶点中没有奇度顶点,而删除而删除e,只使只使u,v 的度数各减的度数各减1,因而因而G1(G2)中只含一个奇度顶点中只含一个奇度顶点,与与任何图中奇度顶点的个数是偶数矛盾任何图中奇度顶点的个数是偶数矛盾.练习练习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

38、,j,l,V2=b,d,f,g,i,k,m,|V1|V2|.证三证三 n=13,m=21.h,l,j为为4度顶点度顶点,a,c,e为为3度顶点度顶点,且它且它们关联不相同的边们关联不相同的边.而在哈密顿回路上而在哈密顿回路上,每个顶点关联两条边每个顶点关联两条边,于是可能用于哈密顿回路的边至多有于是可能用于哈密顿回路的边至多有21(3 2+3 1)=12.12条条边不可能构成经过边不可能构成经过13个顶点的回路个顶点的回路.543某次国际会议某次国际会议8人参加人参加,已知每人至少与其余已知每人至少与其余7人中的人中的4人人能用相同的语言能用相同的语言,问服务员能否将他们安排在同一张圆桌就问服

39、务员能否将他们安排在同一张圆桌就座座,使得每个人都能与两边的人交谈？使得每个人都能与两边的人交谈？解解 做无向图做无向图G=,其中其中V=v|v为与会者为与会者，E=(u,v)|u,v V,u与与v有能用相同的语言有能用相同的语言,且且u v.G为简单图且为简单图且 v V,d(v)4.于是于是,u,v V,d(u)+d(v)8,故故G为哈密顿图为哈密顿图.服务员在服务员在G中找一条哈密顿回路中找一条哈密顿回路,按回路按回路中相邻关系安排座位即可中相邻关系安排座位即可.练习练习 3554.某公司招聘了某公司招聘了3名大学名大学毕业毕业生生,有有5个部个部门门需要人需要人.部部门领导门领导与与毕

40、业毕业生交生交谈谈后后,双方都愿意的双方都愿意的结结果如表所示果如表所示.如果每个部如果每个部门门只能接收一名只能接收一名毕业毕业生生,问这问这3名名毕业毕业生都能到他生都能到他满满意的部意的部门门工工作作吗吗?试给试给出分配方案出分配方案.练习练习 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的阶数的阶数

41、,边数边数,面数分别为面数分别为n,m,r.(1)用反证法用反证法.假设所有面的次数大于等于假设所有面的次数大于等于5,由欧拉公式得由欧拉公式得 2m 5r=5(2+m n)由由(G)3及握手定理有及握手定理有 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的非平凡简单无向图的非

42、平凡简单无向图,证明证明G和和 不可能不可能全是平面图全是平面图.证证 用反用反证证法法.假假设设 与与G 都是平面都是平面图图,则则G与与 的的边边数数m,m 应满应满足足 不妨不妨设设 由于由于G是平面是平面图图,又有又有 m 3n 6 得得 n2 13n+24 0 解得解得 2 n 10 与与n 11矛盾矛盾.练习练习6587.证明下图为非平面图证明下图为非平面图练习练习7证一证一 含子图含子图K3,3:删去顶点删去顶点a和边和边(c,d)证二证二 含与含与K5同胚的同胚的子图子图:删去删去(a,f),收缩收缩(a,e)和和(f,g)59练习练习88.给下图着色至少要用几种颜色给下图着色

43、至少要用几种颜色?解解 由于由于a,b,c 彼此相邻彼此相邻,至少要用至少要用3种颜色种颜色,设它们分别着设它们分别着颜色颜色1,2,3.最少还要用这三种颜色给最少还要用这三种颜色给d,e,f 着色着色.而而g与与d,e,f相邻只能用第相邻只能用第4种颜色种颜色.故至少要用故至少要用4种颜色种颜色.60练习练习99.某校计算机系三年级学生在本学期共有某校计算机系三年级学生在本学期共有6门选修课门选修课Ci,i=1,2,6.设设S(Ci)为选为选Ci课的学生集课的学生集.已知已知 S(Ci)S(C6),i=1,2,5，S(Ci)S(Ci+1),i=1,2,3,4，S(C5)S(C1).问这问这6门课至少几天能考完？门课至少几天能考完？解解 做无向图做无向图G=,其中其中 V=C1,C2,C6 E=(Ci,Cj)|S(Ci)S(Cj)最少要用最少要用4种颜色着色种颜色着色,故最少要故最少要4天天