110.1 欧拉图§欧拉通路(tōnglù)(tōnglù)§欧拉回路§欧拉图§半欧拉图 第1页/共18页第一页，共19页 2哥尼斯堡七桥问题(wèntí)(wèntí) 欧拉图是能一笔画(bǐhuà)(bǐhuà)出的边不重复的回路. . 第2页/共18页第二页，共19页 3欧拉图 欧拉通路: 图中行遍所有(suǒyǒu)顶点且恰好经过每条边一次的通路. 欧拉回路: 图中行遍所有(suǒyǒu)顶点且恰好经过每条边一次的回路.欧拉图: 有欧拉回路的图.半欧拉图: 有欧拉通路而无欧拉回路的图.几点说明：上述定义对无向图和有向图都适用.规定平凡图为欧拉图.欧拉通路是简单通路, 欧拉回路是简单回路.环不影响图的欧拉性. 第3页/共18页第三页，共19页 4欧拉图( (续) )例 图中, (1), (4)为欧拉图; (2), (5)为半欧拉图; (3)，(6)既不 是欧拉图, 也不是半欧拉图. 在(3), (6)中各至少(zhìshǎo)加几条边才能成为欧拉图?第4页/共18页第四页，共19页 5欧拉图的判别(pànbié)(pànbié)法 定理 无向图G为欧拉图当且仅当G连通(liántōng)且无奇度顶点. 无向图G是半欧拉图当且仅当G连通(liántōng)且恰有两个奇度顶点. 定理 有向图D是欧拉图当且仅当D连通(liántōng)且每个顶点的入度都等于出度. 有向图D具有欧拉通路当且仅当D连通(liántōng)且恰有两个奇度顶点, 其中一个入度比出度大1, 另一个出度比入度大1, 其余顶点的入度等于出度.第5页/共18页第五页，共19页。
6实例(shílì)例1 哥尼斯堡七桥问题例2 下面(xià mian)两个图都是欧拉图. 从A点出发, 如何一次成功地走出一条欧拉回路来？ 第6页/共18页第六页，共19页 710.2 哈密顿图 §哈密顿通路(tōnglù)(tōnglù)§哈密顿回路§哈密顿图§半哈密顿图 第7页/共18页第七页，共19页 8哈密顿周游世界问题(wèntí)(wèntí) 第8页/共18页第八页，共19页 9哈密顿图的定义(dìngyì)(dìngyì)哈密顿通路: : 经过(jīngguò)(jīngguò)图中所有顶点一次且仅一次的通路. .哈密顿回路: : 经过(jīngguò)(jīngguò)图中所有顶点一次且仅一次的回路. .哈密顿图: : 具有哈密顿回路的图. .半哈密顿图: : 具有哈密顿通路而无哈密顿回路的图. . 几点说明：平凡图是哈密顿图. .哈密顿通路是初级通路，哈密顿回路是初级回路. .环与平行边不影响图的哈密顿性. .第9页/共18页第九页，共19页 10实例(shílì)例 图中, (1), (2)是哈密顿图; (3) 是半哈密顿图.(4)既不是(bù shi)哈密顿图, 也不是(bù shi)半哈密顿图，为什么？ 第10页/共18页第十页，共19页。
11无向(wú xiànɡ)(wú xiànɡ)哈密顿图的一个必要条件 定理 设无向图G=是哈密顿图, 则对于任意V1 V且V1, 均有 p(G V1) |V1|.证 设C为G中一条哈密顿回路(huílù), 有p(C V1) |V1|. 又因为C G, 故 p(G V1) p(C V1) |V1|. 几点说明定理中的条件是哈密顿图的必要条件, 但不是充分条件.可利用该定理判断某些图不是哈密顿图. 由定理可知, Kr,s当s r+1时不是哈密顿图. 当r 2时, Kr,r是哈密顿图, 而Kr,r+1是半哈密顿图. 第11页/共18页第十一页，共19页 12实例(shílì)例 设G为n阶无向连通(liántōng)简单图, 若G中有割点或桥, 则G不是哈密顿图.证 (1) 设v为割点, 则p(G v) 2>|{v}|=1. 根据定理, G不是哈密顿图. (2) 若G是K2(K2有桥), 它显然不是哈密顿图. 除K2外, 其他的有桥连通(liántōng)图均有割点. 由(1), 得证G不是哈密顿图.第12页/共18页第十二页，共19页。
13无向(wú xiànɡ)(wú xiànɡ)哈密顿图的一个充分条件 定理 设G是n阶无向简单图, 若任意两个不相邻的顶点的度数之和大于等于(děngyú)n 1, 则G中存在哈密顿通路. 当n 3时, 若任意两个不相邻的顶点的度数之和大于等于(děngyú)n, 则G中存在哈密顿回路, 从而G为哈密顿图. 第13页/共18页第十三页，共19页 14哈密顿通路(tōnglù)(回路)的存在性(续)定理中的条件(tiáojiàn)是存在哈密顿通路(回路)的充分条件, 但不是必要条件(tiáojiàn).例如, 设G为长度为n 1(n 4)的路径, 它不满足定理中哈密顿通路的条件(tiáojiàn), 但它显然存在哈密顿通路.设G是长为n的圈, 它不满足定理中哈密顿回路的条件, 但它显然是哈密顿图.由定理, 当n 3时, Kn均为哈密顿图.判断某图是否为哈密顿图至今还是一个难题 第14页/共18页第十四页，共19页 15判断是否是哈密顿图的可行(kěxíng)方法•观察出一条哈密顿回路(huílù) (huílù) •例如 右图( (周游世界问题) )中红•边给出一条哈密顿回路(huílù), (huílù), 故它•是哈密顿图. .•注意, , 此图不满足定理的条件. . •满足充分条件•例如 当n n 3 3时, , KnKn中任何两个不同的顶点 u,v, u,v, 均•有d(u)+d(v) d(u)+d(v) = = 2(n2(n 1) 1) n, n, 所以KnKn为哈密顿图. . 第15页/共18页第十五页，共19页。
16判断(pànduàn)是否是哈密顿图的可行方法(续)例 1/4国际象棋盘(4 4方格)上的跳马问题(wèntí): 马是否能恰好经过每一个方格一次后回到原处?解 每个方格看作一个顶点, 2个顶点之间有边当且仅当马可以从一个方格跳到另一个方格, 得到16阶图G, 如左图红边所示. 取V1={a, b, c, d}, 则p(G V1) = 6 >|V1|, 见右图. 由定理, 图中无哈密顿回路, 故问题(wèntí)无解.在国际象棋盘(8 8)上, 跳马问题(wèntí)是否有解? §不满足(mǎnzú)必要条件第16页/共18页第十六页，共19页 17应用(yìngyòng)实例例 某 次 国 际 会 议 8人 参 加 ， 已 知 每 人 至 少 与 其 余 7人 中(rénzhōng)的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页第十七页，共19页。
18谢谢(xiè xie)大家观赏！第18页/共18页第十八页，共19页 内容(nèiróng)总结1定理 无向(wú xiànɡ)图G为欧拉图当且仅当G连通且无奇度顶点.无向(wú xiànɡ)图G是半欧拉图当且仅当G连通且恰有两个奇度顶点.定理 有向图D是欧拉图当且仅当D连通且每个顶点的入度都等于出度.例2 下面两个图都是欧拉图.可利用该定理判断某些图不是哈密顿图.例 1/4国际象棋盘(44方格)上的顶点之间有边当且仅当马可以从一个方格跳到另一个方格,在国际象棋盘(88)上, 跳马问题是否有解谢谢大家观赏第十九页，共19页。