《一些特殊的图课件》由会员分享，可在线阅读，更多相关《一些特殊的图课件（18页珍藏版）》请在金锄头文库上搜索。
1、1,第10章 一些特殊的图,10.1 欧拉图 10.2 哈密顿图 10.3 平面图 10.4 二分图,2,10.1 欧拉图,欧拉通路 欧拉回路 欧拉图 半欧拉图,3,哥尼斯堡七桥问题,欧拉图是能一笔画出的边不重复的回路.,4,欧拉图,欧拉通路: 图中行遍所有顶点且恰好经过每条边一次的通路. 欧拉回路: 图中行遍所有顶点且恰好经过每条边一次的回路. 欧拉图: 有欧拉回路的图. 半欧拉图: 有欧拉通路而无欧拉回路的图. 几点说明： 上述定义对无向图和有向图都适用. 规定平凡图为欧拉图. 欧拉通路是简单通路, 欧拉回路是简单回路. 环不影响图的欧拉性.,5,欧拉图(续),例 图中, (1), (4)
2、为欧拉图; (2), (5)为半欧拉图; (3)，(6)既不 是欧拉图, 也不是半欧拉图. 在(3), (6)中各至少加几条边才能成为欧拉图?,6,欧拉图的判别法,定理 无向图G为欧拉图当且仅当G连通且无奇度顶点. 无向图G是半欧拉图当且仅当G连通且恰有两个奇度顶点. 定理 有向图D是欧拉图当且仅当D连通且每个顶点的入度都等于出度. 有向图D具有欧拉通路当且仅当D连通且恰有两个奇度顶点, 其中一个入度比出度大1, 另一个出度比入度大1, 其余顶点的入度等于出度.,7,实例,例1 哥尼斯堡七桥问题 例2 下面两个图都是欧拉图. 从A点出发, 如何一次成功地走出一条欧拉回路来？,8,10.2 哈密
3、顿图,哈密顿通路 哈密顿回路 哈密顿图 半哈密顿图,9,哈密顿周游世界问题,10,哈密顿图的定义,哈密顿通路: 经过图中所有顶点一次且仅一次的通路. 哈密顿回路: 经过图中所有顶点一次且仅一次的回路. 哈密顿图: 具有哈密顿回路的图. 半哈密顿图: 具有哈密顿通路而无哈密顿回路的图. 几点说明： 平凡图是哈密顿图. 哈密顿通路是初级通路，哈密顿回路是初级回路. 环与平行边不影响图的哈密顿性.,11,实例,例 图中, (1), (2)是哈密顿图; (3) 是半哈密顿图. (4)既不是哈密顿图, 也不是半哈密顿图，为什么？,12,无向哈密顿图的一个必要条件,定理 设无向图G=是哈密顿图, 则对于任
4、意V1V且 V1, 均有 p(GV1)|V1|. 证 设C为G中一条哈密顿回路, 有p(CV1) |V1|. 又因为 CG, 故 p(GV1) p(CV1) |V1|. 几点说明 定理中的条件是哈密顿图的必要条件, 但不是充分条件. 可利用该定理判断某些图不是哈密顿图. 由定理可知, Kr,s当sr+1时不是哈密顿图. 当r2时, Kr,r是哈密顿图, 而Kr,r+1是半哈密顿图.,13,实例,例 设G为n阶无向连通简单图, 若G中有割点或桥, 则G不是哈密顿图. 证 (1) 设v为割点, 则p(Gv) 2|v|=1. 根据定理, G不是哈密顿图. (2) 若G是K2(K2有桥), 它显然不是
5、哈密顿图. 除K2 外, 其他的有桥连通图均有割点. 由(1), 得证G不是 哈密顿图.,14,无向哈密顿图的一个充分条件,定理 设G是n阶无向简单图, 若任意两个不相邻的顶点 的度数之和大于等于n1, 则G中存在哈密顿通路. 当n3时, 若任意两个不相邻的顶点的度数之和大 于等于n, 则G中存在哈密顿回路, 从而G为哈密顿 图.,15,哈密顿通路(回路)的存在性(续),定理中的条件是存在哈密顿通路(回路)的充分条 件, 但不是必要条件. 例如, 设G为长度为n1(n4)的路径, 它不满足定理 中哈密顿通路的条件, 但它显然存在哈密顿通路. 设G是长为n的圈, 它不满足定理中哈密顿回路的条 件
6、, 但它显然是哈密顿图. 由定理, 当n3时, Kn均为哈密顿图. 判断某图是否为哈密顿图至今还是一个难题,16,判断是否是哈密顿图的可行方法,观察出一条哈密顿回路 例如 右图(周游世界问题)中红 边给出一条哈密顿回路, 故它 是哈密顿图. 注意, 此图不满足定理的条件. 满足充分条件 例如 当n3时, Kn中任何两个不同的顶点 u,v, 均 有d(u)+d(v) = 2(n1) n, 所以Kn为哈密顿图.,17,判断是否是哈 密顿图的可行方法(续),例 1/4国际象棋盘(44方格)上的 跳马问题: 马是否能恰好经过 每一个方格一次后回到原处? 解 每个方格看作一个顶点, 2个 顶点之间有边当
7、且仅当马可以从一个方格跳到另一个方格, 得到16阶图G, 如左图红边所示. 取V1=a, b, c, d, 则p(GV1) = 6 |V1|, 见右图. 由定理, 图中无哈密顿回路, 故问题无解. 在国际象棋盘(88)上, 跳马问题是否有解?,不满足必要条件,18,应用实例,例 某次国际会议8人参加，已知每人至少与其余7人中 的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中相邻关系 安排座位即可. 由本题想到的：哈密顿图的实质是能将图中所有的顶点 排在同一个圈中.,
