.

............................... ...

6

4

哈密尔顿图的充分条件和必要条件的讨论

.

........................

7

5

结论

.

.. .................................................. .....................................

8

参考文献

.

........................... .................................................. ........

8

指导老师

.

.................................................. ...................................

9

1

引言

图论是一门既古老又年轻的学科

,< /p>

随着科学技术的蓬勃发展

,

它的应用已经

渗透到自然科学以及社会科学的各个领域之中

,

利用它我们可以解决很多实际生

活中的问题

,

给你一个图

,

你怎么知道它是否是哈密尔顿图呢

?

当然如果图的顶点

不多

,

你可以用最古老的”尝试和错误”的方法试试找哈密尔顿回路就可以解决< /p>

和判断

.

但是

,

数学家们并不满足这样的碰得焦头烂额后才找到的真理方法

.< /p>

是否

存在一组必要和充分的条件

,

使得我们能够简单轻易地判断一个图是否是哈密尔

顿图

?

有许多智者通过各种方式去尝试过了

,

遗憾的是至今尚未找到一个判别哈

密尔顿回路和通路的充分必要条件

.

虽然有些充分非必要或必要非充分条件

,

但

大部分还是采用尝试的办法

,

.

2

哈密尔顿图的背景

美国图论数学家奥在

1960

年给出了一个图是哈密尔顿图的充分条件：

对于顶点个数大于

2

的图，如果图中任意两点度的和大于或等于顶点总数，

那这个图一定是哈密尔顿图。闭合的哈密顿路径称作哈密顿圈，含有图中

所有顶 的路径称作哈密顿路径

.

1857

年，

哈密尔顿发明了一个游戏

(Icosian Game).

它是由一个木制的正

十二面体构成，

在它的 每个棱角处标有当时很有名的城市。

游戏目的是

“环球旅

行”。为了容易记住被旅游过的城市

，在每 个棱角上放上一个钉子，再用一根

线绕在那些旅游过的城市上

(

钉子

),

由此可以获得旅程的直观表示

(

如图

1)

。

图

1

哈密尔顿

(1805---1865 ),

爱尔兰数学家。

个人生活很不幸，

但兴趣广泛：

诗歌、

光学、天文学和数学无所不能。他的主要贡 献是在代数领域，发现了四元数

(

第

一 个非交换代数

)

，他认为数学是最美丽的花朵。

哈密尔顿把该游戏以

25

英 镑

的价格买给了

s and Sons

公司

(

该公司如今以制造国 际象棋设备而著

名

)

，

1859

年获得专利权。但商业运作失败了

.

该游戏促使人们思考点线连接的

图的结构特征。这就是图论历史上著名 的哈密尔顿问题。

3

哈密尔顿图的概念

含有图中所有顶点的轨称作哈密尔顿轨，闭合的哈密尔顿轨称作哈密

尔顿环，含 有哈密尔顿环的图称作哈密尔顿图。著名的美国图论数学家奥

勒在

1960

年给出了一个图是哈密尔顿图的充分条件：对于顶点个数大于

2

的图，如果图中任意两点度的和大于顶点总数，那这个图一定是哈密尔顿

图。哈密尔顿轨也称作哈密尔顿链，指在一个图中沿边访问每个顶点恰好

一次的路径。寻找这样的一个路径是一个典型的

NP-

完备

(NP- complete)

问

题。