哈密爾頓圖教學(xué)中的幾個(gè)問題

劉云芬,池召艷(.湖北師范學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，湖北 黃石 43500;.湖北文理學(xué)院 數(shù)學(xué)與計(jì)算機(jī)學(xué)院，湖北 襄陽 44053)

離散數(shù)學(xué)課程的教學(xué)目的是提高學(xué)生對(duì)實(shí)際問題的數(shù)學(xué)本質(zhì)表達(dá)能力，增強(qiáng)學(xué)生解決實(shí)際問題的綜合能力。圖論是離散數(shù)學(xué)中的一個(gè)重要分支，而歐拉圖和哈密爾頓圖是圖論中兩類經(jīng)典的圖模型，在具體的教學(xué)過程中，由于歐拉圖的研究已經(jīng)比較徹底，有關(guān)歐拉圖的教學(xué)問題大都是圍繞著歐拉圖的定義以及充要條件來展開。而哈密爾頓圖問題就比較復(fù)雜，目前尚沒有找到能方便判別一個(gè)圖是否為哈密爾頓圖的充要條件，教材[1，2]僅是給出了哈密爾頓圖的一些充分條件和必要條件，但是，在本人的實(shí)際教學(xué)過程中發(fā)現(xiàn)：部分同學(xué)在判別哈密爾頓圖時(shí)會(huì)產(chǎn)生困惑，不知道究竟怎樣操作。以下針對(duì)此部分內(nèi)容的教學(xué)，討論了教學(xué)中的三個(gè)問題，以激發(fā)學(xué)生興趣，引發(fā)學(xué)生思考，并在理解教學(xué)內(nèi)容的基礎(chǔ)上提高學(xué)生自主探索的能力。

1 哈密爾頓圖相關(guān)概念的引入

哈密爾頓圖的概念比較抽象，如果直接講解，不能激發(fā)學(xué)生的學(xué)習(xí)興趣，鑒于此，我們通過漫游問題介紹哈密爾頓圖的起源，吸引學(xué)生的注意力，然后通過簡(jiǎn)單的數(shù)學(xué)游戲激發(fā)學(xué)生學(xué)習(xí)興趣，比如英國(guó)亞瑟王的騎士排列問題[3]，引導(dǎo)學(xué)生在具體感知的基礎(chǔ)上進(jìn)行抽象概括，繼而引出哈密爾頓圖的概念以及判定定理如下：

定義1[1，2]圖G的一條回路若通過G中每個(gè)節(jié)點(diǎn)一次，則稱它為哈密爾頓回路，具有這種回路的圖叫做哈密爾頓圖。

定理1[1，2]設(shè)無向圖G= 是哈密爾頓圖，則對(duì)任意V1?V,必有P(G-V1)≤|V1| ,其中P(G-V1) 是從G中刪去V1(包括V1中相應(yīng)節(jié)點(diǎn)及其關(guān)聯(lián)的邊)后所得到的圖的連通分支數(shù)。

定理2[1，2]設(shè)G= 為無向簡(jiǎn)單圖，|V|≥3，如果G中每對(duì)節(jié)點(diǎn)次數(shù)之和大于等于 |V|，則必為哈密爾頓圖。

2 哈密爾頓圖的判別分析

上面的2個(gè)定理從理論上為我們判別哈密爾頓圖提供了一些依據(jù)，但是在實(shí)際的操作過程中，很多同學(xué)還是會(huì)遇到如下的一些問題：

定理1為哈密爾頓圖判別的必要條件，我們通常是借助它來判別一個(gè)無向圖不是哈密爾頓圖，但是由于其中的子集是任意的，到底怎樣選擇符合條件的子集，很多同學(xué)不知所措。

定理2則是哈密爾頓圖判別的充分條件，但是這個(gè)條件比較強(qiáng)，一些簡(jiǎn)單圖的哈密爾頓圖都無法滿足，比如圖1是一個(gè)節(jié)點(diǎn)為6的簡(jiǎn)單無向圖，它顯然是哈密爾頓圖，但每對(duì)節(jié)點(diǎn)次數(shù)之和為4，并不大于等于圖中的節(jié)點(diǎn)數(shù)6.于是依賴定理2來判別一個(gè)簡(jiǎn)單無向圖是否為哈密爾頓圖又不夠全面。

圖1 簡(jiǎn)單無向圖 圖2 各節(jié)點(diǎn)度數(shù)圖 圖3 不存在哈密爾頓回路圖

在實(shí)際的教學(xué)中，對(duì)于一些節(jié)點(diǎn)數(shù)不是太多的簡(jiǎn)單無向圖，我們可以引導(dǎo)學(xué)生做進(jìn)一步的分析思考，從而歸納出這類問題的簡(jiǎn)便方法。

一個(gè)給定的簡(jiǎn)單無向圖，它要么是哈密爾頓圖，要么不是。要想判別一個(gè)圖是哈密爾頓圖，要么是找到了滿足條件的回路，要么是滿足充分條件；于是我們可以先利用充分條件進(jìn)行判別：如果滿足，則一定可以在圖中找出一條哈密爾頓回路出來，如果不滿足，則可以嘗試著在圖中找這樣的哈密爾頓回路，一般而言，一個(gè)節(jié)點(diǎn)數(shù)不太多的哈密爾頓圖的哈密爾頓回路是比較容易找出來的， 如果經(jīng)過上面的過程， 找不出這樣的回路，則可以嘗試著利用定理1判別這個(gè)圖不是哈密爾頓圖，要利用定理1，關(guān)鍵是找到符合條件的任意子集V，使得子集V的基數(shù)要盡量的小，G-V的連通分支盡要盡量的大，基于這一點(diǎn)，所尋求任意子集V中的點(diǎn)的度數(shù)應(yīng)該是盡可能的大。

基于上面的分析，對(duì)于一些節(jié)點(diǎn)數(shù)不是太多的簡(jiǎn)單無向圖，只需要三種操作便可以方便的解決問題，為了便于記憶，我們可以簡(jiǎn)單歸結(jié)為：“標(biāo)、尋、去”。

1)標(biāo)——標(biāo)出圖中各節(jié)點(diǎn)的度數(shù)，如果度數(shù)最小的兩個(gè)節(jié)點(diǎn)度數(shù)之和大于等于節(jié)點(diǎn)數(shù)，則利用定理2可以斷定這個(gè)圖中一定存在哈密爾頓回路。比如圖2，兩個(gè)最小節(jié)點(diǎn)的度數(shù)之和為6，則可以斷定該圖是哈密爾頓圖。

2)尋——尋找圖中的一條哈密爾頓回路。找出圖2的一條哈密爾頓回路為：1-3-5-4-6-2-1.

3)去——去掉圖中度數(shù)最大的點(diǎn)，令其為V1，考察P(G-V1)和 |V1|的關(guān)系，如P(G-V1)≤|V1| ，

則去掉G-V1中度數(shù)最大的點(diǎn)，并將此點(diǎn)加入到V1中，重復(fù)這個(gè)過程直到P(G-V1)>|V1|，則可以斷定這個(gè)圖中一定不存在哈密爾頓回路。如圖3：令V1={3}，則P(G-V1)=2,|V1|=1,從而有P(G-V1)>|V1|，則此圖不存在哈密爾頓回路。

3 鞏固反思

離散數(shù)學(xué)的部分教材[1，2]和參考書[3，4]對(duì)于此部分的內(nèi)容并沒有做更多的介紹，但是教師在講完教學(xué)內(nèi)容后，一方面可以精選一些與教學(xué)內(nèi)容相聯(lián)系的習(xí)題來鞏固基礎(chǔ)知識(shí)，另一方面可以設(shè)計(jì)一系列的相關(guān)問題，既可以幫助他們梳理、運(yùn)用所學(xué)知識(shí)，又可以引發(fā)他們自主探索:

1)前面的內(nèi)容分析基本上可以解決點(diǎn)數(shù)不是太多的簡(jiǎn)單無向圖中是否存在哈密爾頓圖的判別問題，但是對(duì)于點(diǎn)數(shù)比較多的簡(jiǎn)單無向圖中哈密爾頓回路的判定問題又是一個(gè)新的問題，事實(shí)教材的下一節(jié)就會(huì)介紹圖的矩陣表示，學(xué)生可以嘗試運(yùn)用圖的矩陣來幫助解決問題，復(fù)雜的計(jì)算過程可以讓計(jì)算機(jī)來幫助解決。

2) 教材的前面部分介紹過賦權(quán)圖，如果要在簡(jiǎn)單無向圖中尋找一條權(quán)和最小的哈密爾頓回路，這即是推銷員問題，學(xué)生可以查閱相關(guān)文獻(xiàn)了解相關(guān)內(nèi)容。

3)教材主要是討論了簡(jiǎn)單無向圖中哈密爾頓圖的判定問題，那么對(duì)于簡(jiǎn)單有向圖的判別又會(huì)有什么樣的結(jié)論呢？學(xué)生可以自主探索并查閱文獻(xiàn)來了解。

4 結(jié)束語

一些數(shù)學(xué)專業(yè)的學(xué)生在學(xué)習(xí)相關(guān)課程時(shí)存在一個(gè)問題：看不到所學(xué)的課程的適用價(jià)值，另外抽象嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)令他們找不到探索的方向，于是一些同學(xué)是為了通過考試而學(xué)習(xí)。離散數(shù)學(xué)是一門既講基礎(chǔ)理論，又注重實(shí)際應(yīng)用的學(xué)科，這門學(xué)科的一個(gè)顯著特點(diǎn)是概念和定理多，另一個(gè)特點(diǎn)是方法性強(qiáng)，對(duì)于一個(gè)問題，如果知道方法，則很容易的可以解決問題，否則會(huì)事倍功半，有時(shí)，同一個(gè)問題可能有幾種方法。這就使得部分同學(xué)對(duì)這門課程的一些知識(shí)點(diǎn)把握不準(zhǔn)，似懂非懂。教師在教學(xué)過程中要了解學(xué)生的實(shí)際，通過介紹應(yīng)用背景激發(fā)他們的學(xué)習(xí)興趣，通過判定問題的分析，增強(qiáng)他們學(xué)習(xí)分析問題、解決問題的能力，通過作業(yè)鞏固基礎(chǔ)知識(shí)，通過反思激發(fā)學(xué)有余力的學(xué)生進(jìn)一步的思考，鼓勵(lì)他們查閱文獻(xiàn)了解前沿研究熱點(diǎn)問題，開拓視野，提高自主探索能力，為他們進(jìn)一步的學(xué)習(xí)打下良好的基礎(chǔ)。

參考文獻(xiàn):

[1]徐潔磐.離散數(shù)學(xué)導(dǎo)論(第三版)[M].北京：高等教育出版社，2006.

[2]耿素云,屈婉玲.離散數(shù)學(xué)[M].北京：高等教育出版社，2006.

[3]黃健斌.離散數(shù)學(xué)-精講·精解·精練[M].西安：西安電子科技大學(xué)出版社，2006.

[4]朱懷宏,徐潔磐.離散數(shù)學(xué)導(dǎo)論(第三版)·學(xué)習(xí)指導(dǎo)與習(xí)題解析[M].北京：高等教育出版社，2006.