图论III几种特殊的图.pptVIP

第二课几种特殊的图2.1二部图2.2欧拉图2.3哈密顿图2.4平面图2.1二部图*二部图01完全二部图02二部图*定义设无向图G=V,E,若能将V划分成V1和V21(V1?V2=V,V1?V2=?),使得G中的每条边的两个端2点都一个属于V1,另一个属于V2,则称G为二部图,3记为V1,V2,E,称V1和V2为互补顶点子集.又若G4是简单图,且V1中每个顶点都与V2中每个顶点相邻,5则称G为完全二部图,记为Kr,s,其中r=|V1|,s=|V2|.6注意:n阶零图为二部图.7二部图(续)*例下述各图是否是二部图?定理无向图G=V,E是二部图当且仅当G中无奇圈不是2.2欧拉图*欧拉路与欧拉回路01存在欧拉路和欧拉回路的充分必要条件02哥尼斯堡七桥问题*要求找一条路线,经过每座桥一次且仅一次欧拉图*欧拉路:图中经过每个顶点且恰好经过每条边一次的路.1欧拉回路:图中经过每个顶点恰好经过每条边一次的回路.2欧拉图:有欧拉回路的图.3半欧拉图:有欧拉路,但无欧拉回路的图.4几点说明：上述定义对无向图和有向图都适用.5规定平凡图为欧拉图.6欧拉路是迹,欧拉回路是闭迹.7环不影响图的欧拉性.8欧拉图实例*例是否是欧拉图或半欧拉图?01欧拉图02欧拉图03半欧拉图04半欧拉图05不是06不是07欧拉图的判别法*恰有两个奇度顶点,其中一个入度比出度大1,另一个定理有向图D是欧拉图当且仅当D连通且每个顶点点.G是半欧拉图当且仅当G连通且恰有两个奇度顶出度比入度大1,其余顶点的入度等于出度.的入度都等于出度.D是半欧拉图当且仅当D连通且定理无向图G为欧拉图当且仅当G连通且无奇度顶点.实例*欧拉回路,4例2下面两个图都是欧拉图.5例1哥尼斯堡七桥问题14个奇度顶点,不存在2欧拉路,更不存在3从A点出发,如何一次成功地走出一条欧拉回路来？62.3哈密顿图*哈密顿路和哈密顿回路存在哈密顿路和哈密顿回路的充分条件与必要条件哈密顿周游世界问题*每个顶点是一个城市,有20个城市,要求从一个城市出发,恰好经过每一个城市一次,回到出发点.哈密顿图的定义*哈密顿路:经过图中所有顶点一次且仅一次的路.1哈密顿回路:经过图中所有顶点一次且仅一次的回路.2哈密顿图:具有哈密顿回路的图.3半哈密顿图:具有哈密顿路而无哈密顿回路的图.4几点说明：5平凡图是哈密顿图.6哈密顿路是通路，哈密顿回路是圈.7环不影响图的哈密顿性，对3阶以上图，平行边也不影响图的哈密顿性8.9实例*例是否是哈密顿图,半哈密顿图?哈密顿图01哈密顿图02半哈密顿图*03不是*04无向哈密顿图的一个必要条件*定理设无向图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是半哈密顿图.实例*例设G为n阶无向连通简单图,若G中有割点或桥,则G不是哈密顿图.证(1)设v为割点,则p(G?v)?2|{v}|=1.根据定理,G不是哈密顿图.(2)若G是K2(K2有桥),它显然不是哈密顿图.除K2外,其他的有桥连通图均有割点.由(1),得证G不是哈密顿图.无向哈密顿图的一个充分条件*01定理设G是n阶无向简单图,若任意两个不相邻的02顶点的度数之和大于等于n?1,则G中存在哈密顿通03路.当n?3时,若任意两个不相邻的顶点的度数之和04大于等于n,则G中存在哈密顿回路.05由定理,当n?3时,Kn均为哈密顿图.06定理中的条件是充分条件,但不是必要条件.07例如,n(?5)个顶点的路径存在哈密顿路,但不满08足条件.n(?5)个顶点的圈是哈密顿图,不满足条件.判断是否是哈密顿图的可行方法*例如右图(周游世界问题)中红边给出一条哈密顿回路,故它是哈密顿图