图论III 几种特殊的图

1第二课几种特殊的图2.1二部图2.2欧拉图2.3哈密顿图2.4平面图22.1二部图二部图完全二部图3二部图定义设无向图G=V,E,若能将V划分成V1和V2(V1V2=V,V1V2=),使得G中的每条边的两个端点都一个属于V1,另一个属于V2,则称G为二部图,记为V1,V2,E,称V1和V2为互补顶点子集.又若G是简单图,且V1中每个顶点都与V2中每个顶点相邻,则称G为完全二部图,记为Kr,s,其中r=|V1|,s=|V2|.注意:n阶零图为二部图.4二部图(续)例下述各图是否是二部图?定理无向图G=V,E是二部图当且仅当G中无奇圈不是52.2欧拉图欧拉路与欧拉回路存在欧拉路和欧拉回路的充分必要条件6哥尼斯堡七桥问题要求找一条路线,经过每座桥一次且仅一次7欧拉图欧拉路:图中经过每个顶点且恰好经过每条边一次的路.欧拉回路:图中经过每个顶点恰好经过每条边一次的回路.欧拉图:有欧拉回路的图.半欧拉图:有欧拉路,但无欧拉回路的图.几点说明：上述定义对无向图和有向图都适用.规定平凡图为欧拉图.欧拉路是迹,欧拉回路是闭迹.环不影响图的欧拉性.8欧拉图实例例是否是欧拉图或半欧拉图?欧拉图欧拉图半欧拉图半欧拉图不是不是9欧拉图的判别法定理无向图G为欧拉图当且仅当G连通且无奇度顶点.G是半欧拉图当且仅当G连通且恰有两个奇度顶点.定理有向图D是欧拉图当且仅当D连通且每个顶点的入度都等于出度.D是半欧拉图当且仅当D连通且恰有两个奇度顶点,其中一个入度比出度大1,另一个出度比入度大1,其余顶点的入度等于出度.10实例例1哥尼斯堡七桥问题4个奇度顶点,不存在欧拉路,更不存在欧拉回路,例2下面两个图都是欧拉图.从A点出发,如何一次成功地走出一条欧拉回路来？112.3哈密顿图哈密顿路和哈密顿回路存在哈密顿路和哈密顿回路的充分条件与必要条件12哈密顿周游世界问题每个顶点是一个城市,有20个城市,要求从一个城市出发,恰好经过每一个城市一次,回到出发点.13哈密顿图的定义哈密顿路:经过图中所有顶点一次且仅一次的路.哈密顿回路:经过图中所有顶点一次且仅一次的回路.哈密顿图:具有哈密顿回路的图.半哈密顿图:具有哈密顿路而无哈密顿回路的图.几点说明：平凡图是哈密顿图.哈密顿路是通路，哈密顿回路是圈.环不影响图的哈密顿性，对3阶以上图，平行边也不影响图的哈密顿性.14实例例是否是哈密顿图,半哈密顿图?哈密顿图哈密顿图半哈密顿图*不是*15无向哈密顿图的一个必要条件定理设无向图G=V,E是哈密顿图,则对于任意V1V且V1,均有p(GV1)|V1|.证设C为G中一条哈密顿回路,有p(CV1)|V1|.又因为CG,故p(GV1)p(CV1)|V1|.几点说明定理中的条件是哈密顿图的必要条件,但不是充分条件.可利用该定理判断某些图不是哈密顿图.由定理可知,Kr,s当s≠r时不是哈密顿图.当r2时,Kr,r是哈密顿图,而Kr,r+1是半哈密顿图.16实例例设G为n阶无向连通简单图,若G中有割点或桥,则G不是哈密顿图.证(1)设v为割点,则p(Gv)2|{v}|=1.根据定理,G不是哈密顿图.(2)若G是K2(K2有桥),它显然不是哈密顿图.除K2外,其他的有桥连通图均有割点.由(1),得证G不是哈密顿图.17无向哈密顿图的一个充分条件定理设G是n阶无向简单图,若任意两个不相邻的顶点的度数之和大于等于n1,则G中存在哈密顿通路.当n3时,若任意两个不相邻的顶点的度数之和大于等于n,则G中存在哈密顿回路.由定理,当n3时,Kn均为哈密顿图.定理中的条件是充分条件,但不是必要条件.例如,n(5)个顶点的路径存在哈密顿路,但不满足条件.n(5)个顶点的圈是哈密顿图,不满足条件.18判断是否是哈密顿图的可行方法观察出一条哈密顿回路例如右图(周游世界问题)中红边给出一条哈密顿回路,故它是哈密顿图.满足充分条件例如当n3时,Kn中任何两个不同的顶点u,v,均有d(u)+d(v)=2(n1)n,所以Kn为哈密顿图.19应用实例例某次国际会议8人参加，已知每人至少与他4人有共同语言，问服务员能否将他们安排在同一张圆桌就座，使得每个人都能与两边的人交谈？解作无向图G=V,E,其中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中找一条哈密顿回路C，按C中相邻关系安排座位即可.202.4平面图平面图与平面嵌入平面图的面极大平面图与极小非平面图欧拉公式平面图的对偶图地图着色与四色定理21平面图和平面嵌入定义如果能将图G除顶点外边不相交地画在平面上,则称G是平面图.这个画出的无边相交的图称作G的平面嵌入.没有平面嵌入的图称作非平面图.例如下图中(1)~(4)是平面图,(2)是(1)的平面嵌入，(4)是(3)的平面嵌入.(5)是非平面图.22平面图和平面嵌入(续)•今后称一个图是平面图,可以是指定义中的平面图,又可以是指平面嵌入,视当时的情况而定.当讨论的问题与图的画法有关时,是指平面嵌入.•K5和K3,3是非平面图•设GG,若G为平面图,则G也是平面图;若G为非平面图,则G也是非平面图.•Kn(n5),Kn,m(n,m3)都是非平面图.•平行边与环不影响图的平面性.23平面图的面与次数设G是一个平面嵌入G的面:由G的边将平面划分成的每一个区域无限面(外部面):面积无限的面,用R0表示有限面(内部面):面积有限的面,用R1,R2,…,Rk表示面Ri的边界:包围Ri的所有边构成的回路（组）面Ri的次数:Ri边界的长度，用deg(Ri)表示定理平面图各面的次数之和等于边数的2倍.证每条边可能在两个面的公共边界上，也可能只在一个面的边界上.前者,在每个面的边界上这条边只出现一次,计算两次.后者,它在这个面的边界上出现2次,也计算两次.24平面图的面与次数(续)例1右图有4个面,deg(R1)=1,deg(R2)=3,deg(R3)=2,deg(R0)=8.例2左边2个图是同一个平面图的平面嵌入.R1在(1)中是外部面,在(2)中是内部面;R2在(1)中是内部面,在(2)中是外部面.其实,在平面嵌入中可把任何面作为外部面.25极大平面图定义若G是简单平面图,并且在任意两个不相邻的顶点之间加一条新边所得图为非平面图,则称G为极大平面图.例如,K5,K3,3若删去一条边是极大平面图.K1,K2,K3,K4都是极大平面图(它们已无不相邻顶点).•极大平面图必连通*.•阶数大于等于3的极大平面图中不可能有割点和桥*.•任何n(n4)阶极大平面图G均有(G)3.定理n(n3)阶简单平面图是极大平面图当且仅当它连通且每个面的次数都为3.26实例例是否是极大平面图?不是不是是27极小非平面图定义若G是非平面图,并且任意删除一条边所得图都是平面图,则称G为极小非平面图.极小非平面图必为简单图例如,K5,K3,3是极小非平面图28欧拉公式定理(欧拉公式)设G为n阶m条边r个面的连通平面图,则nm+r=2.证对边数m做归纳证明.m=0,G为平凡图,结论为真.设m=k(k0)结论为真,m=k+1时分情况讨论如下:(1)若G中有一个1度顶点v,则G=G-v连通,有n-1个顶点,k条边和r个面.由归纳假设,(n-1)-k+r=2,即n-(k+1)+r=2,得证m=k+1时结论成立.(2)否则,G中必有圈.删除一个圈上的一条边,记作G.G连通,有n个顶点,k条边和r-1个面.由归纳假设,n-k+(r-1)=2,即n-(k+1)+r=2,得证m=k+1时结论也成立.29欧拉公式(续)推论(欧拉公式的推广)设G是有p(p2)个连通分支的平面图,则nm+r=p+1证设第i个连通分支有ni个顶点,mi条边和ri个面.对各连通分支用欧拉公式,nimi+ri=2,i=1,2,…,p求和并注意r+p1=r1+…+rp,即得nm+r=p+130平面图的性质定理设G为n阶m条边的连通简单平面图,若n3,则m≤n-6推论K5和K3,3不是平面图.K5K3,331同胚与收缩消去2度顶点v如上图从(1)到(2)插入2度顶点v如上图从(2)到(1)G1与G2同胚:G1与G2同构,或经过反复插入、或消去2度顶点后同构收缩边e如下图从(1)到(2)32库拉图斯基定理定理G是平面图G中不含与K5同胚的子图,也不含与K3,3同胚的子图.定理G是平面图G中无可收缩为K5的子图,也无可收缩为K3,3的子图.33非平面图证明例证明下述2个图均为非平面图.收缩2条边收缩2条边K3,3取子图K5取子图34平面图的对偶图定义设平面图G,有n个顶点,m条边和r个面,G的对偶图G*=V*,E*如下：在G的每一个面Ri中任取一个点vi*作为G*的顶点,V*={vi*|i=1,2,…,r}.对G每一条边ek,若ek在G的面Ri与Rj的公共边界上,则作边ek*=(vi*,vj*),且与ek相交;若ek为G中的桥且在面Ri的边界上,则作环ek*=(vi*,vi*).E*={ek*|k=1,2,…,m}.35平面图的对偶图的实例例黑色实线为原平面图,红色虚线为其对偶图36平面图的对偶图的性质性质：•对偶图是平面图，而且是平面嵌入.•对偶图是连通图•若边e为G中的环，则G*与e对应的边e*为桥;若e为桥，则G*中与e对应的边e*为环.•同构的平面图的对偶图不一定同构.上页两个平面图同构,它们的对偶图不同构.37地图:连通无桥平面图的平面嵌入,每一个面是一个国家.若两个国家有公共边界,则称它们是相邻的.地图着色(面着色):对地图的每个国家涂一种颜色，使相邻的国家涂不同的颜色.地图着色问题:用尽可能少的颜色给地图着色.地图着色可以转化成平面图的点着色.当G中无桥时,G*中无环.G的面与G*的顶点对应,且G的两个面相邻当且仅当G*对应的两个顶点相邻,从而G的面着色等同于G*的点着色.地图着色地图着色与平面图的点着色38例红红兰兰绿绿绿绿绿绿黄黄黄黄黄黄四色定理四色猜想(100多年前):任何地图都可以用4种颜色着色,即任何平面图都是4-可着色的.1890年希伍德证明五色定理:任何平面图都是5-可着色的.1976年美国数学家阿佩尔和黑肯证明,如果四色猜想不成立,则存在一个反例,这个反例大约有2000种可能(后来有人简化到600多种),他们用计算机分析了所有这些可能,都没有导致反例.四色定理任何平面图都是4-可着色的.39