《集合论与图论》第18讲1
第18讲哈密顿图
?1. 周游世界,哈密顿通(回)路,哈密顿图
?2. 判定哈密顿图的必要条件
?3. 判定哈密顿图的充分条件
?4. 边不重的哈密顿回路
?5. 货郎问题, 计算复杂性
《集合论与图论》第18讲2
周游世界
?Sir William Rowan Hamilton, 1857,
Icosian game:
《集合论与图论》第18讲3
Willam Rowan Hamilton
?Willam Rowan Hamilton(1805~1865):
?爱尔兰神童(child prodigy)
?三一学院(Trinity College)
?光学(optics)
《集合论与图论》第18讲4
Willam Rowan Hamilton
?Willam Rowan Hamilton(1805~1865):
?1827, Astronomer Royal of Ireland.
?1837, 复数公理化, a+bi, (a,b)
?四元数(quaternion): a+bi+cj+dk, 放弃乘法
交换律!
《集合论与图论》第18讲5
马的周游路线(knight’s tour)
?Leohard Euler, 1759, 棋盘上马的周游路
线(knight’s tour on a chessboard)
《集合论与图论》第18讲6
马的周游路线(knight’s tour)
?Leohard Euler, 1759, 详细分析
《集合论与图论》第18讲7
哈密顿图(Hamilton)
?哈密顿通路(Hamilton path): 经过图中所
有顶点的初级通路
?哈密顿回路(Hamilton circuit/cycle): 经过
图中所有顶点的初级回路
?哈密顿图(Hamiltonian): 有哈密顿回路的
图
?半哈密顿图(semi- Hamiltonian): 有哈密
顿通路的图
《集合论与图论》第18讲8
无向哈密顿图的必要条件
?定理6: 设G=<V,E>是无向哈密顿图,则对
V的任意非空真子集V
1
有
p(G-V
1
)≤|V
1
|
?证明: 设C是G中任意哈密顿回路, 当V
1
中
顶点在C中都不相邻时, p(C-V
1
)=|V
1
|最大;
否则, p(C-V
1
)<|V
1
|. C是G的生成子图, 所
以p(G-V
1
)≤P(C-V
1
)≤|V
1
|. #
《集合论与图论》第18讲9
无向半哈密顿图的必要条件
?定理7: 设G=<V,E>是无向半哈密顿图,则
对V的任意非空真子集V
1
有
p(G-V
1
)≤|V
1
|+1
?证明: 设P是G中任意哈密顿通路, 当V
1
中
顶点都在P内部且都不相邻时, p(P-V
1
)=
|V
1
|+1最大; 否则, p(P-V
1
)≤|V
1
|. P是G的
生成子图, 所以p(G-V
1
)≤p(P-V
1
)≤|V
1
|+1.
#
《集合论与图论》第18讲10
定理7(证明二)
?定理7: 设G=<V,E>是无向半哈密顿图,则
对V的任意非空真子集V
1
有
p(G-V
1
)≤|V
1
|+1
?证明二: 设P是G中任意哈密顿通路, 两个
端点是u与v. 令G
1
=G∪(u,v), 由定理6有
p(G-V
1
) ≤ p(G
1
-V
1
)+1 ≤ |V
1
|+1. #
《集合论与图论》第18讲11
举例
《集合论与图论》第18讲12
举例(续)
《集合论与图论》第18讲13
反例: 非充分条件
?上述条件只是必要条件,而不是充分条件
?反例: Petersen图
?Petersen图满足: ?V
1
≠?, p(G-V
1
)≤|V
1
|
?Petersen图不是哈密顿图: 穷举
?Petersen图是半哈密顿图
《集合论与图论》第18讲14
无向半哈密顿图的充分条件
?定理7: 设G是n(≥2)阶无向简单图,若对G
中任意不相邻顶点u与v有
d(u)+d(v)≥n-1
则G是半哈密顿图.
?证明: (1) G连通
(2) 由极大路径得圈
(3) 由圈得更长路径
路径--极大路径--圈--更长路径
---更长极大路径--更长圈--更长路径--……--哈密顿通路
《集合论与图论》第18讲15
定理7(证明(1)(3))
?证明: (1) G连通: ?u?v( (u,v)?E→
?w((u,w)∈E∧(w,v)∈E )
(3) 由圈得更长路径: 连通
n-2
《集合论与图论》第18讲16
定理7(证明(2))
?证明: (2) 由极大路径得圈: 设极大路径
Γ=v
0
v
1
…v
k
, k≤n-2. (2a) 若(v
0
,v
k
)∈E,则得圈
C=v
0
v
1
…v
k
v
0
. (2b) 若(v
0
,v
k
)?E,则
?i( 1≤i≤k-1∧(v
i
,v
k
)∈E∧(v
0
,v
i+1
)∈E ),
否则, d(v
0
)+d(v
k
)≤d(v
0
)+k-1-(d(v
0
)-1)=k≤n-2
(矛盾). 于是得圈C=v
0
…v
i
v
k
v
k-1
…v
i+1
v
0
. #
v
0
v
k
v
i
v
i+1
v
0
v
k
《集合论与图论》第18讲17
无向哈密顿图的充分条件
?推论1: 设G是n(≥3)阶无向简单图,若对G
中任意不相邻顶点u与v有
d(u)+d(v)≥n
则G是哈密顿图.
?证明: 由定理7知G连通且有哈密顿通路
Γ=v
0
v
1
…v
n
. (1) 若(v
0
,v
n
)∈E,则得哈密顿
回路C=v
0
v
1
…v
n
v
0
. (2) 若(v
0
,v
k
)?E,则与
定理7证明(2b)类似,也存在哈密顿回路. #
《集合论与图论》第18讲18
无向哈密顿图的充分条件
?推论2: 设G是n(≥3)阶无向简单图,若对G
中任意顶点u有
d(u)≥n/2
则G是哈密顿图.
?证明: 由推论1. #
《集合论与图论》第18讲19
定理8
?定理8: 设u,v是无向n阶简单图G中两个不
相邻顶点,且d(u)+d(v)≥n,则
G是哈密顿图? G∪(u,v)是哈密顿图.
?证明: (?)显然
(?) 设C是G∪(u,v)中的哈密顿回路.
(1) C不经过(u,v): C是G中哈密顿回路.
(2) C经过(u,v): C-(u,v)是G中哈密顿通路,
与定理7证明(2b)类似, G中有哈密顿回路.
#
《集合论与图论》第18讲20
有向半哈密顿图的充分条件
?定理9: 设D是n(≥2)阶竞赛图,则D是半哈
密顿图. #
?推论:设D是n阶有向图, 若D含n阶竞赛图
作为子图,则D是半哈密顿图. #
《集合论与图论》第18讲21
有向哈密顿图的充分条件
?定理10: 强连通的竞赛图是哈密顿图.
?证明: n=1时,平凡图是哈密顿图.
n=2时,不可能强连通. 下面设n≥3.
(1) D中存在长度为3的圈.
(2) D中存在长度为k的圈? D中存在长度
为k+1的圈.
《集合论与图论》第18讲22
定理10(证明(1))
?证明(续): (1) D中存在长度为3的圈.
?v∈V(D), 考虑v的前驱集
Γ
D
-
(v) = { u∈V(D) | <u,v>∈E(D) }与后继集
Γ
D
+
(v) = { u∈V(D) | <v,u>∈E(D) }.
D强连通竞赛图, 所以Γ
D
-
(v)≠?,
Γ
D
+
(v)≠?,Γ
D
-
(v)∪Γ
D
+
(v)=V(D)-{v},
?s∈Γ
D
+
(v), ?t∈Γ
D
-
(v), <s,t>∈E(D).
于是C=vstv是长度为3的圈.
v
t
s
Γ
D
-
(v)
Γ
D
+
(v)
《集合论与图论》第18讲23
定理10(证明(2))
?证明(续): (2) D中存在长度为k的圈? D
中存在长度为k+1的圈: 设D中长度为k
(3≤k≤n) 的圈C=v
1
v
2
…v
k
v
1
.
(2a) ?v∈V(D-C), ?v
s
∈V(C), ?v
t
∈V(C),
<v
s
v>∈E(D),<v,v
t
>∈E(D): 则?v
i-1
∈V(C),
?v
j
∈V(C), <v
i-1
,v>∈E(D),<v,v
j
>∈E(D).
v
s
v
t
v
v
i-1
v
i
v
《集合论与图论》第18讲24
定理10(证明(2a))
?证明(续): (2a) ?v∈V(D-C), ?v
i-1
∈V(C),
?v
i
∈V(C), <v
i-1
,v>∈E(D), <v,v
i
>∈E(D),
则C’=v
1
v
2
…v
i-1
vv
i
…v
k
v
1
是长度为k+1的
圈.
v
i-1
v
i
v
v
i-1
v
i
v
《集合论与图论》第18讲25
定理10(证明(2b))
?证明(续): (2b) ?v∈V(D-C),
( ?u∈V(C), <u,v>∈E(D) ) ∨
( ?u∈V(C), <v,u>∈E(D) ): 则令
V
1
={v∈V(D-C) | ?u∈V(C), <u,v>∈E(D) },
V
2
={v∈V(D-C) | ?u∈V(C), <v,u>∈E(D) },
则V
1
≠?,
V
2
≠?,
V
1
∩V
2
=?.
C
V
1
V
2
《集合论与图论》第18讲26
定理10(证明(2b))
?证明(续): (2b) 于是?s∈V
1
, ?t∈V
2
,
<s,t>∈E(D). 在C上任取相邻3点v
i-1
,v
i
,v
i+1
,
则C’=v
1
v
2
…v
i-1
stv
i+1
…v
k
v
1
是长度为k+1
的圈.#
C
V
1
V
2
s
t
v
i-1
v
i
v
i+1
《集合论与图论》第18讲27
推论
?推论:设D是n阶有向图, 若D含n阶强连通
竞赛图作为子图,则D是哈密顿图. #
《集合论与图论》第18讲28
边不重的哈密顿回路
?边不重的哈密顿回路: 设C
1
与C
2
都是图G
的哈密顿回路, 若E(C
1
)∩E(C
2
)=?, 则称
它们为边不重的哈密顿回路.
?问题: K
n
(≥3)中同时存在多少条边不重的
哈密顿回路?
《集合论与图论》第18讲29
定理11
?定理11: 完全图K
2k+1
(k≥1)中同时有k条边
不重的哈密顿回路,且这k条边不重的哈密
顿回路含K
2k+1
中所有边
?推论: 完全图K
2k
(k≥2)中同时有k-1条边不
重的哈密顿回路,并且删除这k-1条哈密顿
回路的所有边后, 剩下的是k条彼此不相
邻的边
《集合论与图论》第18讲30
定理11(证明)
?证明: 设V(K
2k+1
)={v
1
,v
2
,…,v
2k+1
}, 对
i=1,2,…,k, 令
P
i
=v
i
v
i-1
v
i+1
v
i-2
v
i+2
…v
i-(k-1)
v
i+(k-1)
v
i-k
,
把下标按mod(2k)转换到{1,2,…,2k+1}中,
0转换成2k, 令C
i
=v
2k+1
P
i
v
2k+1
.
可以证明: C
i
都是哈密顿回路;
E(C
i
)∩E(C
i
)=? (i≠j);
U
i=1
n
E(C
i
)=E(K
2k+1
). #
《集合论与图论》第18讲31
定理11(举例)
?K
7
: V(K
7
)={v
1
,v
2
,…,v
7
}, k=3, mod 6,
P
1
=v
1
v
0
v
2
v
-1
v
3
v
-2
=v
1
v
6
v
2
v
5
v
3
v
4
,
P
2
=v
2
v
1
v
3
v
0
v
4
v
-1
=v
2
v
1
v
3
v
6
v
4
v
5
,
P
3
=v
3
v
2
v
4
v
1
v
5
v
0
=v
3
v
2
v
4
v
1
v
5
v
6
,
v
1
v
2
v
3
v
4
v
5
v
6
v
7
v
1
v
2
v
3
v
4
v
5
v
6
v
7
v
1
v
2
v
3
v
4
v
5
v
6
v
7
《集合论与图论》第18讲32
推论(证明)
?证明: k=2时, K
4
显然. 下面设k≥3.
K
2k
= K
2(k-1)+1
+ K
1
(联图)
设V(K
2(k-1)+1
)={v
1
,v
2
,…,v
2k-1
}, V(K
1
)={v
2k
},
《集合论与图论》第18讲33
推论(证明)
?证明: 由定理11, K
2k-1
中有k-1条边不重的
哈密顿回路,设为C’
1
,C’
2
,…,C’
k-1
, 依次把
v
2k
“加入”C’
i
,得到满足要求的C
i
. #
《集合论与图论》第18讲34
货郎问题(TSP)
?货郎问题(Travling Salesman Problem):
给定n个城市之间的所有距离, 求推销员
走遍所有城市的最短路线
?又名旅行商问题,巡回售货员问题,TSP
?TSP: 给定带权完全图G=<V,E,W>,求最
短哈密顿回路.
《集合论与图论》第18讲35
复杂性(complexity)
?复杂性(complexity): 算法工作时需要的
资源数量, 如时间,空间等
?输入规模(input size): 反映输入大小的量,
如图的顶点数,图的边数等
?最坏情形(worst-case)复杂性: 在所有规
模为n的输入上, 算法工作所需要的最大
资源量, 通常表示为n的函数, 如n
2
, 2
n
等
《集合论与图论》第18讲36
可行(efficient)算法
?可行(efficient)算法: 复杂性是多项式函数
的算法, 如O(n
2
), O(n), O(n
3
), O(n
100
).
?易解(tractable)问题: 存在多项式复杂性
算法的问题, 如欧拉图问题
?P(polynomial time): 存在多项式时间复杂
性算法的问题, 如欧拉图问题
?难解(intractable)问题: 不存在多项式复杂
性算法的问题, 如货郎问题(TSP)
《集合论与图论》第18讲37
TSP的复杂性
?蛮力法(brute force): 穷举所有的可能性
来进行验证或比较, 复杂性为2
n
以上.
?TSP: n!条H通路, (n-1)!/2条H回路
?启发式(Heuristic)方法: 分支限界,……
?目前还不知道TSP是否有多项式时间算
法, 大多数学者认为没有. 证明?
?P=?NP问题:计算机科学的核心问题, 奖
金$1,000,000
?近似(approximation)算法
《集合论与图论》第18讲38
总结
?周游世界,哈密顿通(回)路,哈密顿图
?判定哈密顿图的必要条件
?判定哈密顿图的充分条件
?边不重的哈密顿回路
?货郎问题, 计算复杂性
《集合论与图论》第18讲39
作业(#14)
? p234, 习题八, 7,9,13
?今天交作业#11, #12, #13
《集合论与图论》第18讲40
习题讲解(#10)
?p213, 习题七, 1,2,3,4,5,7
?1. 解: 设G中顶点数为n,由握手定理:
32=2m=Σd(v)≤3*4+4*3+2(n-7),
解得n≥11. #
?错误: 32=2m=Σd(v)<3*4+4*3+3(n-7),
解得n>29/3≈9.67, n∈Z,∴ n≥10. #
《集合论与图论》第18讲41
习题讲解(#10)
?2. 方法一: 穷举法
?证明: 由握手定理及其推论, G中5度顶点
的个数只能是0,2,4,6,8, 相应的G中6度
顶点的个数是9,7,5,3,1.在这5种组合中,
前3种至少有5个6度顶点, 后2种至少有6
个5度顶点. #
?注意: 0个5度顶点是可能的
《集合论与图论》第18讲42
习题讲解(#10)
?2. 方法二: 反证法
?证明: (反证)假设结论不成立, 即G中至多
有4个6度顶点并且至多有5个5度顶点. 因
为G是9阶图并且只有5度和6度顶点, 所
以G中恰好有4个6度顶点和5个5度顶点.
但是, 这与握手定理及其推论相矛盾! #
《集合论与图论》第18讲43
习题讲解(#10)
?3.证明: (反证)假设存在这样的多面体,令
G=<V,E>, 其中V={ v | v 是多面体的面},
E={ (u,v) | 面u与面v之间有公共棱}. 则G
有奇数个顶点, 并且所有顶点都有奇数度.
这是与握手定理及其推论相矛盾的!. #
《集合论与图论》第18讲44
习题讲解(#10)
?4. 证明: 令G=<V,E>, 其中V={v|v是选手},
E={(u,v)|选手u与选手v下过棋}. G是简单
图并且δ(G)≥1.设V(G)={v
1
,v
2
,…,v
n
}, 则
?i∈{1,2,…,n}, d(v
i
)∈{1,2,…,n-1}. 由抽屉
原则,存在i,j∈{1,2,…,n}, i≠j, d(v
i
)=d(v
j
). #
?定理: 简单图中至少有2个顶点度相等.
《集合论与图论》第18讲45
习题讲解(#10)
?5. 方法一: 考虑G
解: 2m=3n, (握手定理) n=6
2n-3=m, (已知条件) m=9
所以G的度数列为(3,3,3,3,3,3), 删除1个
顶点后G
1
为(2,2,2,3,3). 考虑G
1
的2个3度
顶点是否相邻,可得出2种非同构情况. #
G
1 G
《集合论与图论》第18讲46
习题讲解(#10)
?5. 方法二: 考虑G
解: 2m=3n, (握手定理) n=6
2n-3=m, (已知条件) m=9
所以G的度数列为(3,3,3,3,3,3), G的度数
列是(2,2,2,2,2,2). 考虑G的圈的长度, 可
得出2种非同构情况. #
G G
《集合论与图论》第18讲47
习题讲解(#10)
?7. 解:
(1) (6,6,5,5,3,3,2) 不可简单图化
(5,4,4,2,2,1), (3,3,1,1,0), (2,0,0,0)
(2) (5,3,3,2,2,1) 可以(1种非同构的)
(2,2,1,1,0), (1,0,1,0)
《集合论与图论》第18讲48
习题讲解(#10)
?7. 解(续):
(3) (3,3,2,2,2,2) 可以(4种非同构的)
(2,1,1,2,2), (2,2,2,1,1), (1,1,1,1)
?错误: (2,1,1,2,2), (0,0,2,2) 不可