图论III几种特殊的图.ppt

1,第二课 几种特殊的图,2.1 二部图2.2 欧拉图2.3 哈密顿图2.4 平面图,2,2.1 二部图,二部图完全二部图,3,二部图,定义 设无向图 G=,若能将V 划分成V1 和 V2(V1V2=V,V1V2=),使得G中的每条边的两个端点都一个属于V1,另一个属于V2,则称G为二部图,记为,称V1和V2为互补顶点子集.又若G是简单图,且V1中每个顶点都与V2中每个顶点相邻,则称G为完全二部图,记为Kr,s,其中r=|V1|,s=|V2|.注意:n 阶零图为二部图.,4,二部图(续),例 下述各图是否是二部图?,定理 无向图G=是二部图当且仅当G中无奇圈,不是,5,2.2 欧拉图,欧拉路与欧拉回路存在欧拉路和欧拉回路的充分必要条件,6,哥尼斯堡七桥问题,要求找一条路线,经过每座桥一次且仅一次,7,欧拉图,欧拉路:图中经过每个顶点且恰好经过每条边一次的路.欧拉回路:图中经过每个顶点恰好经过每条边一次的回路.欧拉图:有欧拉回路的图.半欧拉图:有欧拉路,但无欧拉回路的图.几点说明：上述定义对无向图和有向图都适用.规定平凡图为欧拉图.欧拉路是迹,欧拉回路是闭迹.环不影响图的欧拉性.,8,欧拉图实例,例 是否是欧拉图或半欧拉图?,欧拉图,欧拉图,半欧拉图,半欧拉图,不是,不是,9,欧拉图的判别法,定理 无向图G为欧拉图当且仅当G连通且无奇度顶点.G是半欧拉图当且仅当G连通且恰有两个奇度顶点.定理 有向图D是欧拉图当且仅当D连通且每个顶点的入度都等于出度.D是半欧拉图当且仅当D连通且恰有两个奇度顶点,其中一个入度比出度大1,另一个出度比入度大1,其余顶点的入度等于出度.,10,实例,例1 哥尼斯堡七桥问题 4个奇度顶点,不存在 欧拉路,更不存在 欧拉回路,例2 下面两个图都是欧拉图.从A点出发,如何一次成功地走出一条欧拉回路来？,11,2.3 哈密顿图,哈密顿路和哈密顿回路存在哈密顿路和哈密顿回路的充分条件与必要条件,12,哈密顿周游世界问题,每个顶点是一个城市,有20个城市,要求从一个城市出发,恰好经过每一个城市一次,回到出发点.,13,哈密顿图的定义,哈密顿路:经过图中所有顶点一次且仅一次的路.哈密顿回路:经过图中所有顶点一次且仅一次的回路.哈密顿图:具有哈密顿回路的图.半哈密顿图:具有哈密顿路而无哈密顿回路的图.几点说明：平凡图是哈密顿图.哈密顿路是通路，哈密顿回路是圈.环不影响图的哈密顿性，对3阶以上图，平行边也不影响图的哈密顿性.,14,实例,例 是否是哈密顿图,半哈密顿图?,哈密顿图,哈密顿图,半哈密顿图*,不是*,15,无向哈密顿图的一个必要条件,定理 设无向图G=是哈密顿图,则对于任意V1V且V1,均有 p(GV1)|V1|.证 设C为G中一条哈密顿回路,有p(CV1)|V1|.又因为CG,故 p(GV1)p(CV1)|V1|.几点说明定理中的条件是哈密顿图的必要条件,但不是充分条件.可利用该定理判断某些图不是哈密顿图.由定理可知,Kr,s当s r时不是哈密顿图.当r2时,Kr,r是哈密顿图,而Kr,r+1是半哈密顿图.,16,实例,例 设G为n阶无向连通简单图,若G中有割点或桥,则G不是哈密顿图.,证(1)设v为割点,则p(Gv)2|v|=1.根据定理,G不是哈密顿图.,(2)若G是K2(K2有桥),它显然不是哈密顿图.除K2外,其他的有桥连通图均有割点.由(1),得证G不是哈密顿图.,17,无向哈密顿图的一个充分条件,定理 设G是n阶无向简单图,若任意两个不相邻的顶点的度数之和大于等于n1,则G中存在哈密顿通路.当n3时,若任意两个不相邻的顶点的度数之和大于等于n,则G中存在哈密顿回路.由定理,当n3时,Kn均为哈密顿图.定理中的条件是充分条件,但不是必要条件.例如,n(5)个顶点的路径存在哈密顿路,但不满足条件.n(5)个顶点的圈是哈密顿图,不满足条件.,18,判断是否是哈密顿图的可行方法,观察出一条哈密顿回路 例如 右图(周游世界问题)中红边给出一条哈密顿回路,故它是哈密顿图.满足充分条件例如 当n3时,Kn中任何两个不同的顶点 u,v,均有d(u)+d(v)=2(n1)n,所以Kn为哈密顿图.,19,应用实例,例 某次国际会议8人参加，已知每人至少与他4人有共同语言，问服务员能否将他们安排在同一张圆桌就座，使得每个人都能与两边的人交谈？,解 作无向图G=,其中V=v|v为与会者，E=(u,v)|u,vV,u与v有共同语言,且uv.G为简单图.根据条件,vV,d(v)4.于是，u,vV,有d(u)+d(v)8.由定理可知G为哈密顿图.服务员在G中找一条哈密顿回路C，按C中相邻关系安排座位即可.,20,2.4 平面图,平面图与平面嵌入平面图的面极大平面图与极小非平面图欧拉公式平面图的对偶图地图着色与四色定理,21,平面图和平面嵌入,定义 如果能将图G除顶点外边不相交地画在平面上,则称G是平面图.这个画出的无边相交的图称作G的平面嵌入.没有平面嵌入的图称作非平面图.例如 下图中(1)(4)是平面图,(2)是(1)的平面嵌入，(4)是(3)的平面嵌入.(5)是非平面图.,22,平面图和平面嵌入(续),今后称一个图是平面图,可以是指定义中的平面图,又可以是指平面嵌入,视当时的情况而定.当讨论的问题与图的画法有关时,是指平面嵌入.K5和K3,3是非平面图设G G,若G为平面图,则G 也是 平面图;若G 为非平面图,则G也 是非平面图.Kn(n5),Kn,m(n,m3)都是非平面图.平行边与环不影响图的平面性.,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(n4)阶极大平面图G均有(G)3.定理 n(n3)阶简单平面图是极大平面图当且仅当它连通且每个面的次数都为3.,26,实例,例 是否是极大平面图?,不是,不是,是,27,极小非平面图,定义 若G是非平面图,并且任意删除一条边所得图都是平面图,则称G为极小非平面图.极小非平面图必为简单图例如,K5,K3,3是极小非平面图,28,欧拉公式,定理(欧拉公式)设G为n阶m条边r个面的连通平面图,则 nm+r=2.证 对边数m做归纳证明.m=0,G为平凡图,结论为真.设m=k(k0)结论为真,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(p2)个连通分支的平面图,则 n m+r=p+1证 设第 i 个连通分支有 ni个顶点,mi 条边和 ri 个面.对各连通分支用欧拉公式,ni mi+ri=2,i=1,2,p求和并注意 r+p1=r1+rp,即得 n m+r=p+1,30,平面图的性质,定理 设G为n阶m条边的连通简单平面图,若n3,则mn-6 推论 K5 和 K3,3不是平面图.,K5,K3,3,31,同胚与收缩,消去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个图均为非平面图.,34,平面图的对偶图,定义 设平面图G,有n个顶点,m条边和r个面,G的对偶图G*=如下：在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,