哈密爾頓圖教學中的幾個問題

劉云芬,池召艷(.湖北師范學院 數學與統計學院，湖北 黃石 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.