哈密尔顿图教学中的几个问题

刘云芬,池召艳(.湖北师范学院 数学与统计学院，湖北 黄石 43500;.湖北文理学院 数学与计算机学院，湖北 襄阳 44053)

离散数学课程的教学目的是提高学生对实际问题的数学本质表达能力，增强学生解决实际问题的综合能力。图论是离散数学中的一个重要分支，而欧拉图和哈密尔顿图是图论中两类经典的图模型，在具体的教学过程中，由于欧拉图的研究已经比较彻底，有关欧拉图的教学问题大都是围绕着欧拉图的定义以及充要条件来展开。而哈密尔顿图问题就比较复杂，目前尚没有找到能方便判别一个图是否为哈密尔顿图的充要条件，教材[1，2]仅是给出了哈密尔顿图的一些充分条件和必要条件，但是，在本人的实际教学过程中发现：部分同学在判别哈密尔顿图时会产生困惑，不知道究竟怎样操作。以下针对此部分内容的教学，讨论了教学中的三个问题，以激发学生兴趣，引发学生思考，并在理解教学内容的基础上提高学生自主探索的能力。

1 哈密尔顿图相关概念的引入

哈密尔顿图的概念比较抽象，如果直接讲解，不能激发学生的学习兴趣，鉴于此，我们通过漫游问题介绍哈密尔顿图的起源，吸引学生的注意力，然后通过简单的数学游戏激发学生学习兴趣，比如英国亚瑟王的骑士排列问题[3]，引导学生在具体感知的基础上进行抽象概括，继而引出哈密尔顿图的概念以及判定定理如下：

定义1[1，2]图G的一条回路若通过G中每个节点一次，则称它为哈密尔顿回路，具有这种回路的图叫做哈密尔顿图。

定理1[1，2]设无向图G= 是哈密尔顿图，则对任意V1⊆V,必有P(G-V1)≤|V1| ,其中P(G-V1) 是从G中删去V1(包括V1中相应节点及其关联的边)后所得到的图的连通分支数。

定理2[1，2]设G= 为无向简单图，|V|≥3，如果G中每对节点次数之和大于等于 |V|，则必为哈密尔顿图。

2 哈密尔顿图的判别分析

上面的2个定理从理论上为我们判别哈密尔顿图提供了一些依据，但是在实际的操作过程中，很多同学还是会遇到如下的一些问题：

定理1为哈密尔顿图判别的必要条件，我们通常是借助它来判别一个无向图不是哈密尔顿图，但是由于其中的子集是任意的，到底怎样选择符合条件的子集，很多同学不知所措。

定理2则是哈密尔顿图判别的充分条件，但是这个条件比较强，一些简单图的哈密尔顿图都无法满足，比如图1是一个节点为6的简单无向图，它显然是哈密尔顿图，但每对节点次数之和为4，并不大于等于图中的节点数6.于是依赖定理2来判别一个简单无向图是否为哈密尔顿图又不够全面。

图1 简单无向图 图2 各节点度数图 图3 不存在哈密尔顿回路图

在实际的教学中，对于一些节点数不是太多的简单无向图，我们可以引导学生做进一步的分析思考，从而归纳出这类问题的简便方法。

一个给定的简单无向图，它要么是哈密尔顿图，要么不是。要想判别一个图是哈密尔顿图，要么是找到了满足条件的回路，要么是满足充分条件；于是我们可以先利用充分条件进行判别：如果满足，则一定可以在图中找出一条哈密尔顿回路出来，如果不满足，则可以尝试着在图中找这样的哈密尔顿回路，一般而言，一个节点数不太多的哈密尔顿图的哈密尔顿回路是比较容易找出来的， 如果经过上面的过程， 找不出这样的回路，则可以尝试着利用定理1判别这个图不是哈密尔顿图，要利用定理1，关键是找到符合条件的任意子集V，使得子集V的基数要尽量的小，G-V的连通分支尽要尽量的大，基于这一点，所寻求任意子集V中的点的度数应该是尽可能的大。

基于上面的分析，对于一些节点数不是太多的简单无向图，只需要三种操作便可以方便的解决问题，为了便于记忆，我们可以简单归结为：“标、寻、去”。

1)标——标出图中各节点的度数，如果度数最小的两个节点度数之和大于等于节点数，则利用定理2可以断定这个图中一定存在哈密尔顿回路。比如图2，两个最小节点的度数之和为6，则可以断定该图是哈密尔顿图。

2)寻——寻找图中的一条哈密尔顿回路。找出图2的一条哈密尔顿回路为：1-3-5-4-6-2-1.

3)去——去掉图中度数最大的点，令其为V1，考察P(G-V1)和 |V1|的关系，如P(G-V1)≤|V1| ，

则去掉G-V1中度数最大的点，并将此点加入到V1中，重复这个过程直到P(G-V1)>|V1|，则可以断定这个图中一定不存在哈密尔顿回路。如图3：令V1={3}，则P(G-V1)=2,|V1|=1,从而有P(G-V1)>|V1|，则此图不存在哈密尔顿回路。

3 巩固反思

离散数学的部分教材[1，2]和参考书[3，4]对于此部分的内容并没有做更多的介绍，但是教师在讲完教学内容后，一方面可以精选一些与教学内容相联系的习题来巩固基础知识，另一方面可以设计一系列的相关问题，既可以帮助他们梳理、运用所学知识，又可以引发他们自主探索:

1)前面的内容分析基本上可以解决点数不是太多的简单无向图中是否存在哈密尔顿图的判别问题，但是对于点数比较多的简单无向图中哈密尔顿回路的判定问题又是一个新的问题，事实教材的下一节就会介绍图的矩阵表示，学生可以尝试运用图的矩阵来帮助解决问题，复杂的计算过程可以让计算机来帮助解决。

2) 教材的前面部分介绍过赋权图，如果要在简单无向图中寻找一条权和最小的哈密尔顿回路，这即是推销员问题，学生可以查阅相关文献了解相关内容。

3)教材主要是讨论了简单无向图中哈密尔顿图的判定问题，那么对于简单有向图的判别又会有什么样的结论呢？学生可以自主探索并查阅文献来了解。

4 结束语

一些数学专业的学生在学习相关课程时存在一个问题：看不到所学的课程的适用价值，另外抽象严谨的数学令他们找不到探索的方向，于是一些同学是为了通过考试而学习。离散数学是一门既讲基础理论，又注重实际应用的学科，这门学科的一个显著特点是概念和定理多，另一个特点是方法性强，对于一个问题，如果知道方法，则很容易的可以解决问题，否则会事倍功半，有时，同一个问题可能有几种方法。这就使得部分同学对这门课程的一些知识点把握不准，似懂非懂。教师在教学过程中要了解学生的实际，通过介绍应用背景激发他们的学习兴趣，通过判定问题的分析，增强他们学习分析问题、解决问题的能力，通过作业巩固基础知识，通过反思激发学有余力的学生进一步的思考，鼓励他们查阅文献了解前沿研究热点问题，开拓视野，提高自主探索能力，为他们进一步的学习打下良好的基础。

参考文献:

[1]徐洁磐.离散数学导论(第三版)[M].北京：高等教育出版社，2006.

[2]耿素云,屈婉玲.离散数学[M].北京：高等教育出版社，2006.

[3]黄健斌.离散数学-精讲·精解·精练[M].西安：西安电子科技大学出版社，2006.

[4]朱怀宏,徐洁磐.离散数学导论(第三版)·学习指导与习题解析[M].北京：高等教育出版社，2006.