1012一些特殊的图.pptx

《1012一些特殊的图.pptx》由会员分享，可在线阅读，更多相关《1012一些特殊的图.pptx（18页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、110.1 欧拉图欧拉通路欧拉回路欧拉图半欧拉图 第1页/共18页2哥尼斯堡七桥问题 欧拉图是能一笔画出的边不重复的回路.第2页/共18页3欧拉图 欧拉通路:图中行遍所有顶点且恰好经过每条边一次的通路.欧拉回路:图中行遍所有顶点且恰好经过每条边一次的回路.欧拉图:有欧拉回路的图.半欧拉图:有欧拉通路而无欧拉回路的图.几点说明：上述定义对无向图和有向图都适用.规定平凡图为欧拉图.欧拉通路是简单通路,欧拉回路是简单回路.环不影响图的欧拉性.第3页/共18页4欧拉图(续)例 图中,(1),(4)为欧拉图;(2),(5)为半欧拉图;(3)，(6)既不 是欧拉图,也不是半欧拉图.在(3),(6)中各至少

2、加几条边才能成为欧拉图?第4页/共18页5欧拉图的判别法 定理 无向图G为欧拉图当且仅当G连通且无奇度顶点.无向图G是半欧拉图当且仅当G连通且恰有两个奇度顶点.定理 有向图D是欧拉图当且仅当D连通且每个顶点的入度都等于出度.有向图D具有欧拉通路当且仅当D连通且恰有两个奇度顶点,其中一个入度比出度大1,另一个出度比入度大1,其余顶点的入度等于出度.第5页/共18页6实例例1 哥尼斯堡七桥问题例2 下面两个图都是欧拉图.从A点出发,如何一次成功地走出一条欧拉回路来？第6页/共18页710.2 哈密顿图 哈密顿通路哈密顿回路哈密顿图半哈密顿图 第7页/共18页8哈密顿周游世界问题 第8页/共18页9

3、哈密顿图的定义哈密顿通路:经过图中所有顶点一次且仅一次的通路.哈密顿回路:经过图中所有顶点一次且仅一次的回路.哈密顿图:具有哈密顿回路的图.半哈密顿图:具有哈密顿通路而无哈密顿回路的图.几点说明：平凡图是哈密顿图.哈密顿通路是初级通路，哈密顿回路是初级回路.环与平行边不影响图的哈密顿性.第9页/共18页10实例例 图中,(1),(2)是哈密顿图;(3)是半哈密顿图.(4)既不是哈密顿图,也不是半哈密顿图，为什么？第10页/共18页11无向哈密顿图的一个必要条件 定理 设无向图G=是哈密顿图,则对于任意V1 V且V1,均有 p(G V1)|V1|.证 设C为G中一条哈密顿回路,有p(C V1)|

4、V1|.又因为C G,故 p(G V1)p(C V1)|V1|.几点说明定理中的条件是哈密顿图的必要条件,但不是充分条件.可利用该定理判断某些图不是哈密顿图.由定理可知,Kr,s当s r+1时不是哈密顿图.当r 2时,Kr,r是哈密顿图,而Kr,r+1是半哈密顿图.第11页/共18页12实例例 设G为n阶无向连通简单图,若G中有割点或桥,则G不是哈密顿图.证 (1)设v为割点,则p(G v)2|v|=1.根据定理,G不是哈密顿图.(2)若G是K2(K2有桥),它显然不是哈密顿图.除K2外,其他的有桥连通图均有割点.由(1),得证G不是哈密顿图.第12页/共18页13无向哈密顿图的一个充分条件

5、定理 设G是n阶无向简单图,若任意两个不相邻的顶点的度数之和大于等于n 1,则G中存在哈密顿通路.当n 3时,若任意两个不相邻的顶点的度数之和大于等于n,则G中存在哈密顿回路,从而G为哈密顿图.第13页/共18页14哈密顿通路(回路)的存在性(续)定理中的条件是存在哈密顿通路(回路)的充分条件,但不是必要条件.例如,设G为长度为n 1(n 4)的路径,它不满足定理中哈密顿通路的条件,但它显然存在哈密顿通路.设G是长为n的圈,它不满足定理中哈密顿回路的条件,但它显然是哈密顿图.由定理,当n 3时,Kn均为哈密顿图.判断某图是否为哈密顿图至今还是一个难题 第14页/共18页15判断是否是哈密顿图的

6、可行方法观察出一条哈密顿回路 例如 右图(周游世界问题)中红边给出一条哈密顿回路,故它是哈密顿图.注意,此图不满足定理的条件.满足充分条件例如 当n 3时,Kn中任何两个不同的顶点 u,v,均有d(u)+d(v)=2(n 1)n,所以Kn为哈密顿图.第15页/共18页16判断是否是哈 密顿图的可行方法(续)例 1/4国际象棋盘(4 4方格)上的跳马问题:马是否能恰好经过每一个方格一次后回到原处?解 每个方格看作一个顶点,2个顶点之间有边当且仅当马可以从一个方格跳到另一个方格,得到16阶图G,如左图红边所示.取V1=a,b,c,d,则p(G V1)=6|V1|,见右图.由定理,图中无哈密顿回路,

7、故问题无解.在国际象棋盘(8 8)上,跳马问题是否有解?不满足必要条件第16页/共18页17应用实例例 某次国际会议8人参加，已知每人至少与其余7人中的4人有共同语言，问服务员能否将他们安排在同一张圆桌就座，使得每个人都能与两边的人交谈？解 图是描述事物之间关系的最好的手段之一.作无向图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中找一条哈密顿回路C，按C中相邻关系安排座位即可.由本题想到的：哈密顿图的实质是能将图中所有的顶点排在同一个圈中.第17页/共18页18谢谢大家观赏！第18页/共18页