e5
v3
v2 e1 v1
e2
e3
e4
v4
e5
v3 e3 e4 v4
v2 v1 v5
e2 e3
e1 e5
v3 e4 v4 v6
v1
e6 v5 e7 e8 v6 e2 e3
e8 v5
e8 v6 v5 e2 v6
e7
G
v2 e1 v1 v5 v6 v3 e4 v4 v5 v2
G1
e2 v3 e4 v2 e1 v1 v5 e1
定理15.7
定理15.7 设G是n阶无向简单图，若对于G中任意不相邻的顶 点vi,vj，均有 d(vi)+d(vj)≥n-1 (15.1) 则G中存在哈密顿通路。 证明 首先证明G是连通图。 否则G至少有两个连通分支， 设G1,G2是阶数为n1,n2的两个连通分支， 设v1∈V(G1)，v2∈V(G2)，因为G是简单图，所以 dG(v1)+dG(v2)＝dG1(v1)+dG2(v2)≤n1-1+n2-1≤n-2 这与(15.1)矛盾，所以G必为连通图。
例15.3的说明
哈密顿通路是经过图中所有顶点的一条初级通路。 哈密顿回路是经过图中所有顶点的初级回路。 对于二部图还能得出下面结论： 一般情况下，设二部图G＝<V1,V2,E>，|V1|≤|V2|，且 |V1|≥2，|V2|≥2，由定理15.6及其推论可以得出下面结 论： (1) 若G是哈密顿图，则|V1|＝|V2|。 (2) 若G是半哈密顿图，则|V2|＝|V1|+1。 (3) 若|V2|≥|V1|+2，则G不是哈密顿图，也不是半哈密 顿图。
§15.2 哈密顿图
设图为G2，则G2＝<V1,V2,E>，其中 V1＝{a,g,h,i,c}，V2＝{b,e,f,j,k,d}， 易知，p(G2-V1)＝|V2|＝6>|V1|＝5， 由定理15.6可知，G2不是哈密顿图， 但G2是半哈密顿图。 baegjckhfid为G2中一条哈密顿通路。 设图为G3。G3＝<V1,V2,E>，其中 V1＝{a,c,g,h,e}，V2＝{b,d,i,j,f}， G3中存在哈密顿回路。 如 abcdgihjefa， 所以G3是哈密顿图。
®
(a) 制造满足归纳假设的若干个小欧拉图.由连通及 无奇度定点可知，(G) ≥2，用扩大路径法可得G 中长度≥3的圈C1.删除C1上所有边（不破坏G中顶 点度数的奇偶性）得G ，则G 无奇度顶点，设它 有s ≥1个连通分支G1 ,G2 ,…,Gs ，它们的边数均 ≤k，因而它们都是小欧拉图. (b) 将C1上被删除的边还原，从C1上某点出发走出 G的一条欧拉回路C.
十二面体
哈密尔顿把该游戏以25英镑的价格买给了J.Jacques and Sons公司 (该公司如今以制造国际象棋设备而著 名) ，1859年获得专利权。但商业运作失败了。
该游戏促使人们思考点线连接的图的结构特征。这 就是图论历史上著名的哈密尔顿问题。
哈密尔顿(1805---1865),爱尔兰数学家。个人生活很 不幸，但兴趣广泛：诗歌、光学、天文学和数学无所 不能。他的主要贡献是在代数领域，发现了四元数(第 一个非交换代数)，他认为数学是最美丽的花朵。
§15.2 哈密顿图
推论 设无向图G＝<V,E>是半哈密顿图，对于任意的V1V且 V1≠，均有 p(G-V1)≤|V1|+1 证明 设P是G中起于u终于v的哈密顿通路， 令G ＝G∪(u,v)(在G的顶点u,v之间加新边)， 易知G 为哈密顿图， 由定理15.6可知，p(G -V1)≤|V1|。 因此，p(G-V1) ＝ p(G -V1-(u,v)) ≤ p(G -V1)+1 ≤ |V1|+1
®
实例
(1)
(2)
(3)
(4)
在上图中， (1),(2) 是哈密顿图; (3)是半哈密顿图; (4)既不是哈密顿图，也不是半哈密顿图，为什么？
与判断一个图是否为欧拉图不一样，到目前为止，人们还 没有找到哈密顿图简单的充分必要条件。
§15.2 哈密顿图
定理15.6 设无向图G＝<V,E>是哈密顿图，对于任意V1V，且 V1≠，均有 p(G-V1)≤|V1| 其中，p(G-V1)为G-V1的连通分支数。 证明 设C为G中任意一条哈密顿回路， 易知，当V1中顶点在C上均不相邻时， p(C-V1)达到最大值|V1|， 而当V1中顶点在C上有彼此相邻的情况时， 均有p(C-V1)＜|V1|，所以有 p(C-V1)≤|V1|。 而C是G的生成子图，所以，有p(G-V1)≤p(C-V1)≤|V1|。 说明 本定理的条件是哈密顿图的必要条件，但不是充分条件。 可以验证彼得松图满足定理中的条件，但不是哈密顿图。 若一个图不满足定理中的条件，它一定不是哈密顿图。
第十五章 欧拉图与哈密顿图
第十五章 欧拉图与哈密顿图
欧拉图
哈密顿图
最短路问题与货郎担问题 知 识 点：欧拉图、汉密尔顿图、Fleury算法、Dijkstra 算法、货郎担问题 。 教学要求：深刻理解和掌握欧拉图与汉密尔顿图的性质。
教学重点：欧拉图与汉密尔顿图的性质。
学时: 2
§15.1 欧拉图
两个与可行遍问题有关的问题
§15.2 哈密顿图
定义15.2 通过图(无向图或有向图)中所有顶点一 次且仅一次的通路称为哈密顿通路. 通过图(无向图或有向图)中所有顶点一 次且仅一次的回路称为哈密顿回路(哈密顿圈). 具有哈密顿回路的图称为哈密顿图 具有哈密顿通路但不具有哈密顿回路的图称为半哈 密顿图 规定平凡图是哈密顿图 环与平行边不影响哈密顿性.
从以上证明不难看出：欧拉图是若干个边不重 的圈之并，见下图.
PLAY
§15.1 欧拉图
定理15.2 无向图G是半欧拉图当且仅当G是连通的且 恰有两个奇度顶点 证 必要性简单. 充分性（利用定理15.1） 设u,v为G 中的两个奇度顶点，令 G =G(u,v) 则G 连通且无奇度顶点，由定理15.1知G 为欧拉图，因而 存在欧拉回路C，令 =C(u,v) 则 为 G 中欧拉通路.

一个要求行遍图的每条边恰好一次, 这就是欧拉回路问 题,对应的图称为欧拉图

一个要求行遍图的每个顶点恰好一次, 这就是哈密顿圈 问题,对应的图称为哈密顿图
C
A
D
B
哥尼斯堡七桥问题 周游世界问题
®
§15.1 欧拉图
定义15.1 通过图(无向图或有向图)中所有边一次且仅一 次行遍所有顶点的通路称为欧拉通路. 通过图(无向图或有向图)中所有边一次且仅一 次行遍所有顶点的回路称为欧拉回路. 具有欧拉回路的图称为欧拉图 具有欧拉通路而无欧拉回路的图称为半欧拉图 规定平凡图是欧拉图
例15.3 在下图中给出的三个图都是二部图。它们中的哪些是 哈密顿图？哪些是半哈密顿图？为什么？ 易知互补顶点子集 V1＝{a,f} V2＝{b,c,d,e} 设此二部图为G1，则G1＝<V1,V2,E>。 p(G1-V1)＝4>|V1|＝2， 由定理15.6及其推论可知，G1不是哈 密顿图，也不是半哈密顿图。
®
§15.1 欧拉图
定理15.3 有向图D是欧拉图 当且仅当 D是强连通的且
每个顶点的入度等于出度
定理15.4 有向图D是半欧拉图当且仅当 D是单向连通的且 恰有两个奇度顶点,其中一个顶点的入度比出度大1, 另一个顶点出度比入度大1,而其余顶点入度等于出度 定理15.5 G是非平凡的欧拉图当且仅当G是连通的且是 若干个边不重的圈的并
G2
v3 v4 v6 v5
G3
v2
e1 v1 v6 v4 v3
v1
v6
v4
G4
®
G5
G6
G7
W =v e v3 e v e ve W v e =v W8=v0e6v e W v0 =v e v e e v v e v e v v e W =v W =v W =v W =v e v W =v 5 6 5 7 6 8 1 5 3 0 3 4 0 57 7 6 8 0 1 6 50 5 3 7 6 8 4 1 4 5 3 3 2 3 2 4 1 4 1 1e 0 6 2 0 6 5 7 6 3 0 6 5 7 6 8 6 5 7 6 4 8 0 1 6 5 5 3 7 3 6 4 8 4 1 5 2v5 3 2
例15.4
例15.4 设G是n阶无向连通图。证明：若G中有割点或桥，则 G不是哈密顿图。 证明 (1)证明若G中有割点，则G不是哈密顿图。 设v为连通图G中一个割点，则V ＝{v}为G中的点割集， 而 p(G-V )≥2＞1＝|V | 由定理15.6可知G不是哈密顿图。 (2)证明若G中有桥，则G不是哈密顿图。 设G中有桥，e＝(u,v)为其中的一个桥。 若u,v都是悬挂点，则G为K2，K2不是哈密顿图。 若u,v中至少有一个，比如u，d(u)≥2，由于e与u关联，e 为桥，所以G-u至少产生两个连通分支，于是u为G中割点 由(1)的讨论可知，G不是哈密顿图。
§15.2 哈密顿图
背景
1857年， 哈密尔顿发明了一个游戏(Icosian Game). 它是由一个木制的正十二面体构成，在它的每个棱角 处标有当时很有名的城市。游戏目的是“环球旅行”。 为了容易记住被旅游过的城市 ，在每个棱角上放上一 个钉子，再用一根线绕在那些旅游过的城市上(钉子), 由此可以获得旅程的直观表示。
彼德森图
K5
K3,3
®
§15.1 欧拉图
Fleury(弗罗莱)算法

⑴ 任取 v0∈V(G),令 P0 = v0 , i=0 ⑵ 设 Pi = v0e1v1e2…eivi , 如果 E(G)-{e1 , e2 , … ,ei}中没有与vi关联的边,则 计算停止。否则按下述条件从 E(G) - {e1 , e2 , … ,ei} 中任取一条边ei+1 (a) ei+1和vi相关联; (b) 除非没有别的边可选择,