图4

42
无向半哈密顿图的充分条件 定理8.7: 设G是n(≥2)阶无向简 单图, 若对G中任意不相邻顶点 u与v有 d(u)+d(v)≥n-1 则G是半哈密顿图.
2008-11-20 《集合论与图论》第14讲 43
定理8.7证明 证: 只需证明 (1) G连通 (2) 由极大路径可得圈 (3) 由圈可得更长路径
2008-11-20
《集合论与图论》第14讲
3
Euler的解法 1736年, 图论和拓扑学诞生
c A a
2008-11-20 《集合论与图论》第14讲
C d eg b f B D
4
一笔画
2008-11-20
《集合论与图论》第14讲
5
欧拉通路(Euler trail)
经过图中所有边的简单通路
2008-11-20
(a) ei+1与vi关联 (b) 除非别无选择,否则ei+1不是Gi中的桥
Fleury算法举例
2008-11-20
《集合论与图论》第14讲
21
Fleury算法正确性 定理8.5: 设G是无向欧拉图,则 Fleury算法终止时得到的简单通 路是欧拉回路. #
2008-11-20
《集合论与图论》第14讲
2008-11-20
《集合论与图论》第14讲
11
(2)⇒(3) 若删除任意1个圈上的边,则所 有顶点的度还是偶数, 但是不一 定连通了. 对每个连通分支重复 进行.
2008-11-20
《集合论与图论》第14讲
12
(3)⇒(1) 有公共点但边不交的简单回路, 总可以拼接成欧拉回路: 在交点 处,走完第1个回路后再走第2个 回路.#
2008-11-20 《集合论与图论》第14讲 19
Fleury算法(迭代形式)
(1) P0:=v; (2) 设Pi=v0e1v1e2…eivi已经行遍, 设 Gi=G-{e1,e2 ,… ,ei}, ei+1:= Gi中满足如下2条件的边: (3) 若Gi≠Ni, 则回到(2); 否则算法停止
2008-11-20 《集合论与图论》第14讲 20
1 1 0 0 1 1 0 1
2008-11-20
《集合论与图论》第14讲
25
轮盘设计
D=<V,E>, V={00,01,10,11}, E={ abc=<ab,bc> | a,b,c∈{0,1} }
000 00 100 1 0 0 0 1 1 0 1 1 0 1 001 01
010 10 101 011 11 110 111
2008-11-20
《集合论与图论》第14讲
44
定理8.7证明(1) (1) G连通: ∀u∀v( (u,v)∉E→ ∃w((u,w)∈E∧(w,v)∈E )
n-2
2008-11-20
《集合论与图论》第14讲
45
定理8.7证明(2)
设极大路径 Γ=v0v1…vk, k≤n-2. 若(v0,vk)∉E, 则 ∃i( 1≤i≤k-1∧(vi,vk)∈E∧(v0,vi+1)∈E ), 否则, d(v0)+d(vk) ≤d(v0)+k-1-(d(v0)-1)=k≤n-2(矛盾). 于是得圈C=v0…vivkvk-1…vi+1v0.
2008-11-20
《集合论与图论》第14讲
26
周游世界
Sir William Rowan Hamilton, 1857, Icosian game:
2008-11-20
《集合论与图论》第14讲
27
Willam Rowan Hamilton (1805~1865) 爱尔兰神童(child prodigy) 三一学院(Trinity college) 光学(optics) 1827, Astronomer Royal of Ireland.
2008-11-20
《集合论与图论》第14讲
51
有向半哈密顿图的充分条件
定理8.9: 设D是n(≥2)阶竞赛图, 则 D是半哈密顿图. # 推论:设D是n阶有向图, 若D含n阶 竞赛图作为子图, 则D是半哈密顿 图. #
2008-11-20
《集合论与图论》第14讲
52
有向哈密顿图的充分条件 定理8.10: 强连通的竞赛图是哈 密顿图.
2008-11-20
《集合论与图论》第14讲
35
无向哈密顿图的必要条件 定理8.6: 设G=<V,E>是无向哈 密顿图, 则对V的任意非空真子 集V1有 p(G-V1) ≤ |V1|
2008-11-20
《集合论与图论》第14讲
36
定理8.6证明 证: 设C是G中任意哈密顿回路, 当V1中顶点在C中都不相邻时, p(C-V1)=|V1|最大; 否则, p(C-V1)<|V1|. C是G的生成子图, 所以p(G-V1)≤P(C-V1)≤|V1|. #
2008-11-20
《集合论与图论》第14讲
53
定理8.10 证: n=1时,平凡图是哈密顿图. n=2时,不可能强连通. 下面设n≥3. 只需证明: (1) D中存在长度为3的圈. (2) D中存在长度为k的圈 ⇒ D中 存在长度为k+1的圈.
2008-11-20 《集合论与图论》第14讲 54
无向哈密顿图的充分条件二 推论2: 设G是n(≥3)阶无向简单 图,若对G中任意顶点u有 d(u)≥n/2 则G是哈密顿图. #
2008-11-20
《集合论与图论》第14讲
50
定理8.8 设u,v是无向n阶简单图G中两个 不相邻顶点,且d(u)+d(v)≥n, 则 G是哈密顿图 ⇔ G∪(u,v)是哈密顿图. #
32
半哈密顿图(semi-Hamiltonian)
有哈密顿通路的图
2008-11-20
《集合论与图论》第14讲
33
哈密顿回路(Hamilton circuit/cycle)
经过图中所有顶点的初级回路
2008-11-20
《集合论与图论》第14讲
34
哈密顿图(Hamiltonian)
ห้องสมุดไป่ตู้有哈密顿回路的图
《集合论与图论》第14讲
17
Fleury算法(避桥法) 从任意一点开始, 沿着没有走过 的边向前走 在每个顶点, 优先选择剩下的非 桥边, 除非只有唯一一条边 直到得到欧拉回路或宣布失败
2008-11-20 《集合论与图论》第14讲 18
Fleury算法(递归形式)
if d(v)>1 then e:=v关联的任意非割边 else e:=v关联的唯一边 u:=e的另一个端点. 递归地求G-e的从u到w的欧拉通路 把e接续在递归求出的通路上
2008-11-20
《集合论与图论》第14讲
30
马的周游路线(knight’s tour)
Leohard Euler, 1759, 详细分析
2008-11-20
《集合论与图论》第14讲
31
哈密顿通路(Hamilton path)
经过图中所有顶点的初级通路
2008-11-20
《集合论与图论》第14讲
2008-11-20 《集合论与图论》第14讲 37
无向半哈密顿图的必要条件 定理8.7: 设G=<V,E>是无向半 哈密顿图,则对V的任意非空真 子集V1有 p(G-V1)≤|V1|+1 #
2008-11-20
《集合论与图论》第14讲
38
判断是否哈密顿图
2008-11-20
《集合论与图论》第14讲
39
选择V1
2008-11-20
《集合论与图论》第14讲
40
p(G-V1)=6 > 5=|V1|
2008-11-20
《集合论与图论》第14讲
41
非充分条件的反例 Petersen图 ∀V1≠∅, p(G-V1)≤|V1| 不是哈密顿图, 是半哈密顿图
2008-11-20
《集合论与图论》第14讲
第14讲 欧拉图与哈密顿图 内容提要 第八章 欧拉图与哈密顿图 8.1 欧拉图 8.2 哈密顿图
2008-11-20
《集合论与图论》第14讲
1
七桥问题 Königsberg, River Pregel, (Kaliningrad, Russia)
2008-11-20
《集合论与图论》第14讲
2
Leonhard Euler(1707~1783) 瑞士数学家, 最多产的数学家
D +
2008-11-20 《集合论与图论》第14讲 55
定理8.10证明(2)
设D中有圈C=v1v2…vkv1, (3≤k≤n) 若∃v∈V(D-C), ∃vs,vt∈V(C), 使得 <vsv>∈E(D), <v,vt>∈E(D), 则 ∃vi-1,vj∈V(C), 使得<vi-1,v>∈E(D),<v,vj>∈E(D).
22
逐步插入回路算法 每次求出一个简单回路 把新求出的回路插入老回路, 合 并成一个更大的回路 直到得到欧拉回路或宣布失败
2008-11-20
《集合论与图论》第14讲
23
逐步插入回路算法举例
2008-11-20
《集合论与图论》第14讲
24
轮盘设计
000,001,010,011,100,101,110,111
《集合论与图论》第14讲
9
无向欧拉图的充分必要条件 定理8.1: 设G是无向连通图,则 G是欧拉图 (1) ⇔ G中所有顶点都是偶数度 (2) ⇔ G是若干个边不交的圈的并(3)
《集合论与图论》第14讲 10