Download presentation
Presentation is loading. Please wait.
Published byVeronika Fekete Modified 6年之前
1
迷茫的旅行商 —— 图的哈密尔顿性 一名旅行商要拜访多个地点时, 如何找到在拜访每个地点一次后再回到起点的最短路径?? 很难吗?
不信你试试 !即使就只有33个地方,瞎走的话也许真的要走上至少200年!
2
(一)、哈密尔顿图的概念 1、背景 1857年, 哈密尔顿发明了一个游戏(Icosian Game).它是由一个木制的正十二面体构成,在它的每个棱角处标有当时很有名的城市。游戏目的是“环球旅行”。为了容易记住被旅游过的城市 ,在每个棱角上放上一个钉子,再用一根线绕在那些旅游过的城市上(钉子),由此可以获得旅程的直观表示。
3
哈密尔顿把该游戏以25英镑的价格买给了J.Jacques and Sons公司 (该公司如今以制造国际象棋设备而著名) ,1859年获得专利权。但商业运作失败了。
该游戏促使人们思考点线连接的图的结构特征。这就是图论历史上著名的哈密尔顿问题。 哈密尔顿( ), 爱尔兰数学家。个人生活很不幸,但兴趣广泛:诗歌、光学、天文学和数学无所不能。他的主要贡献是在代数领域,发现了四元数(第一个非交换代数),他认为数学是最美丽的花朵。
4
2、哈密尔顿图与哈密尔顿路 定义1 如果图G的一个圈C含有G的所有顶点,则称C为图G的哈密尔顿圈, 简称哈圈或者H-圈。
5
定义2 如果图G的一条路P含有G的所有顶点,则称P为图G的哈密尔顿路, 简称哈路或者H-路。
u v
6
定义3 如果图G含有哈密尔顿圈,则称G为哈密尔顿图
例1、正十二面体是H图。 例2 下图G是非H图。 图G u v
7
(二)、性质与判定 1、性质 定理1 (必要条件) 若G为H图,则对V(G)的任一非空顶点子集S,有:
证明:设C是G的H圈,则对V(G)的任意非空子集S, 容易知道: ω(G)表示 图G所含的连通分支的个数 所以,有:
8
注:不等式为G是H图的必要条件,即不等式不满足时,可断定对应图是非H图。
证明:取S={u, v, w},则有: 所以由定理1知,G为非H图。
9
注意:满足定理1不等式的图不一定是H图。 例如:著名的彼德森图是非H图,但它满足定理1的不等式。 彼得森( ),丹麦哥本哈根大学数学教授。家境贫寒,因此而辍过学。但19岁就出版了关于对数的专著。他当过中学教师,32岁获哥本哈根大学数学博士学位,然后一直在该大学作数学教授。
10
彼得森是一位出色的名教师。他讲课遇到推理困难时,总是说:“这是显而易见的”,并让学生自己查阅他的著作。同时,他是一位有经验的作家,论述问题很形象,讲究形式的优雅。
1891年,彼得森发表了一篇奠定他图论历史地位的长达28页的论文。这篇文章被公认是第一篇包含图论基本结论的文章。同时也是第一次在文章中使用“图”术语。 1898年,彼得森又发表了一篇只有3页的论文,在这篇文章中,为举反例构造了著名的彼得森图。
11
2、判定 图的H性判定是NP-困难问题。到目前为止,有关的定理有300多个,但没有一个是理想的。拓展H图的实用特征仍然被图论领域认为是重大而没有解决的问题。 图的哈密尔顿问题和四色问题被谓为挑战图论领域150年智力极限的总和。三位数学“诺奖”获得者ErdÖs、Whitney 、 Lovász 以及Dirac、Ore等在哈密尔顿问题上有过杰出贡献。 下面,介绍一个著名的定理。
12
定理2 (充分条件) 对于n≧3的简单图G,如果G中有: 那么G是H图。 证明: 若不然,设G是一个满足定理条件的极大非H简单图。显然G不能是完全图,否则,G是H图。 于是,可以在G中任意取两个不相邻顶点u与v。考虑图G + u v,由G的极大性,G+u v是H图。且G+u v的每一个H圈必然包含边uv。
13
所以,在G中存在起点为u而终点为v的H路P。
v=vn vn-1 vi+1 vi v3 v2 u=v1 P 令:
14
对于S与T, 显然, 所以: 另一方面:可以证明: 否则,设 那么,由 由 这样在G中有H圈,与假设矛盾! vn vn-1 vi+1 vi
P 这样在G中有H圈,与假设矛盾!
15
于是: 这与已知 矛盾! 注:该定理是数学家 Dirac在1952年得到的。该定理被认为是H问题的划时代奠基性成果。 Dirac曾经是丹麦奥尔胡斯大学知名教授,杰出的数学研究者。其父亲(继父)是在量子力学中做出卓越贡献的物理学家狄拉克,1933年获诺贝尔物理学奖。Dirac发表关于H问题论文39篇。他1952年的定理将永载史册!
16
1960年,美国耶鲁大学数学家Ore院士考察不相邻两点度和情况,弱化了Dirac条件 ,得到一个著名的结果。
Ore发表关于H问题论文59篇。 定理3 (充分条件) 对于n≧3的单图G,如果G中的任意两个不相邻顶点u与v,有: 那么,G是H图。
17
注: (1) 该定理证明和定理2完全一致! (2) 该定理的条件是紧的。例如:设G是由Kk+1的一个顶点和另一个Kk+1的一个顶点重合得到的图,那么对于G的任意两个不相邻顶点u与v,有: 但G是非H图。 k=3时的例子
Similar presentations