呂誠，孫秀華

（安徽建筑大學(xué)數(shù)理系，安徽合肥230022）

離散數(shù)學(xué)中圖論教學(xué)的探討

呂誠，孫秀華

（安徽建筑大學(xué)數(shù)理系，安徽合肥230022）

離散數(shù)學(xué)圖論部分具有概念多，定理多，內(nèi)容豐富，學(xué)習(xí)難度大等特點(diǎn)，但其對(duì)計(jì)算機(jī)科學(xué)等相關(guān)專業(yè)大學(xué)生的后續(xù)課程又極為重要，因此本文試圖探索如何激發(fā)貫穿整個(gè)課程的各種興趣點(diǎn)，引導(dǎo)學(xué)生自發(fā)式學(xué)習(xí).同時(shí)也探討類比式的教學(xué)方式在該課程的具體實(shí)施方法.

離散數(shù)學(xué)；圖論；歐拉圖；哈密爾頓圖；教學(xué)

1 引言

近年來,離散數(shù)學(xué)在現(xiàn)代科學(xué)中的重要性日益增加,已不僅是計(jì)算機(jī)專業(yè)的必備理論基礎(chǔ),也為其它工科專業(yè)和工程技術(shù)人員所必需.正鑒于此,各大高校的計(jì)算機(jī)專業(yè)、電子信息專業(yè)和計(jì)算信息專業(yè)等均開設(shè)《離散數(shù)學(xué)》課程[1,2]，并將其視為重要的專業(yè)基礎(chǔ)課.圖論作為《離散數(shù)學(xué)》課程的一個(gè)重要部分,在近幾十年里得到迅速發(fā)展,并且圖論的各種理論被大量應(yīng)用于解決生產(chǎn)管理、軍事、交通運(yùn)輸、計(jì)算機(jī)和通訊網(wǎng)絡(luò)中的許多離散性問題，因而更加重要.于是有相當(dāng)數(shù)量的高校還為高年級(jí)學(xué)生及研究生專門開設(shè)《圖論》課程[3].圖論部分的內(nèi)容很多，解決問題的方式各不相同，特別是大量全新的概念和靈活多樣的定理證明，且沒有任何前期課程作為參考，對(duì)初學(xué)者有相當(dāng)?shù)碾y度，教學(xué)中也有著一定的困難.對(duì)于如何提高圖論部分的教學(xué)，眾多學(xué)者一直在做各種努力[4,5].本文將討論興趣教學(xué)和類比教學(xué)在該課程實(shí)施的方法,從而對(duì)教學(xué)工作者和廣大學(xué)生起到一定的幫助.

2 興趣帶動(dòng)教學(xué)的方式

提到以興趣帶動(dòng)教學(xué)，眾多授課教師都會(huì)在介紹圖論這一章之前提及歐拉和“哥尼斯堡七橋問題”，這些內(nèi)容可以極大地激發(fā)初學(xué)者的興趣，并帶動(dòng)他們主動(dòng)思考相關(guān)問題，從而帶著問題進(jìn)入本章內(nèi)容.然而數(shù)學(xué)的學(xué)習(xí)通常都極為辛苦，單單上述興趣不足以持續(xù)太久，學(xué)生的三分鐘熱度一過，又會(huì)覺得課程枯燥、煩悶，教學(xué)效果自然大打折扣.因而，本文主張將興趣教學(xué)貫穿始終，從培養(yǎng)學(xué)生對(duì)圖論這一全新內(nèi)容的興趣，到將已有的興趣激發(fā)并轉(zhuǎn)化為強(qiáng)烈的學(xué)習(xí)欲望，更好地完成本課程的教學(xué).

其實(shí)可以激發(fā)學(xué)生興趣的方法很多，在各個(gè)內(nèi)容中都可找到興趣點(diǎn)，讓學(xué)生覺得每個(gè)知識(shí)點(diǎn)都頗有意思.比如通過介紹數(shù)學(xué)史，如上述“哥尼斯堡七橋問題”，也可以是該課程的一些重大問題，特別是前人的智慧都無法解決的，對(duì)于提升學(xué)習(xí)該課程的動(dòng)力更為明顯.當(dāng)介紹到漢密爾頓圖時(shí)，可指出將一個(gè)圖的每一頂點(diǎn)均視為某個(gè)城市，每條邊視為某兩個(gè)城市間的道路，哈密爾頓圖則可以理解為遍歷所有城市且不重復(fù)經(jīng)過任意城市，即通常所說的“環(huán)游世界問題”，而且這一問題至今沒能給出有效地方法完全解決，只能得到某些充分條件和某些必要條件，亦可適當(dāng)引導(dǎo)學(xué)生思考這些為什么不能統(tǒng)一起來得到充要條件.當(dāng)介紹到圖的同構(gòu)概念時(shí)，也可說明這也是圖論學(xué)科需要解決的一個(gè)重要問題，即如何有效地判斷圖的同構(gòu).當(dāng)介紹到平面圖及圖的染色時(shí)，可介紹著名的“四色猜想”：在1852年英國一名青年蓋思里發(fā)現(xiàn)在給英國地圖染色時(shí)只需四種顏色即可，且四種顏色是必要的，于是提出猜想：任何地圖上的國家只須四種顏色來染，使得任何具有共同邊界的兩個(gè)國家顏色都不相同.1878年倫敦?cái)?shù)學(xué)會(huì)負(fù)責(zé)人凱萊向倫敦?cái)?shù)學(xué)會(huì)成員正式宣布了這一問題，并形成當(dāng)時(shí)著名的“四色猜想”.在隨后一百多年里，很多人“證明”了這一結(jié)論，卻又被發(fā)現(xiàn)這些都是失敗的證明.最終1976年美國伊利諾斯大學(xué)的阿佩爾和?？蟽擅淌诮柚?jì)算機(jī)花費(fèi)1200多個(gè)小時(shí)，討論了近兩千個(gè)可約構(gòu)形后，宣布“四色猜想”成為“四色定理”.然而計(jì)算機(jī)的證明卻并沒有給予人們信服，因?yàn)闄z驗(yàn)這近兩千個(gè)可約構(gòu)形絕非易事，因而尋求“通?！钡姆椒ā捶菣C(jī)器的數(shù)學(xué)證明來解決這一問題，仍然十分重要，這一點(diǎn)至今沒有做到.這就是我們所試圖達(dá)到的：介紹本課程現(xiàn)存的重要問題，令學(xué)生在無從尋找參考答案的情況下進(jìn)行思考，感受課程的魅力，提高學(xué)習(xí)興趣.

有時(shí)介紹某些復(fù)雜的定義時(shí)，難免會(huì)然學(xué)生感覺生硬，單從定義也很難讓學(xué)生理解.于是如果能夠用其解決某些實(shí)際問題，可加深學(xué)生對(duì)概念的理解與運(yùn)用.比如剛開始介紹圖論正文，便有一堆概念和定義，單是圖的定義就有好幾百字，講解完畢后，學(xué)生卻一頭霧水，仍沒弄清頂點(diǎn)、邊等概念.這時(shí)可以令學(xué)生思考如下問題：在某個(gè)集會(huì)時(shí)，恰有6人坐在同一桌上，則或者其中有三人兩兩相識(shí)，或者三人兩兩都不相識(shí).在給出的數(shù)分鐘里，學(xué)生們無法給出解決的思路，我們卻可以告訴他們用圖的定義可以輕松解答.我們記x1、x2、x3、x4、x5、x6六個(gè)頂點(diǎn)表示六個(gè)人，并用不同顏色的邊來表示兩人之間的關(guān)系，如果兩人相互認(rèn)識(shí)，就用黃線連接，如果兩人不認(rèn)識(shí)，就用黑線連接.現(xiàn)在只需證明這個(gè)圖中必含有一個(gè)同色的三角形.不妨取點(diǎn)x1，則與x1相連的邊中至少有三條同色，設(shè)x1x2、x1x3和x1x4為黃邊.現(xiàn)考查三角形x2x3x4，若其中有一條黃邊，設(shè)x2x3，則x1x2x3為黃邊三角形；若沒有一條為黃邊，則x2x3x4本身為黑邊三角形.這一簡單應(yīng)用同樣可以帶來意想不到的教學(xué)效果.

3 類比教學(xué)的方式

圖論中涉及眾多概念，而且很多概念有相關(guān)之處，不易區(qū)分.在指導(dǎo)學(xué)生學(xué)習(xí)時(shí)不妨采用類比的方式加以強(qiáng)化.比如歐拉圖與哈密爾頓圖，歐拉圖是數(shù)學(xué)家歐拉為解決著名的“哥尼斯堡七橋問題”而得出的，并由此產(chǎn)生了圖論這門新興學(xué)科；哈密爾頓圖由“環(huán)游世界游戲”而得出，至今仍未能給出哈密爾頓圖存在的充分必要條件.這兩種圖作為圖論中的重點(diǎn)和難點(diǎn)對(duì)于初學(xué)者有相當(dāng)大的難度.我可通過舉例將他們進(jìn)行類比，加以區(qū)分.

例[2](a)畫一個(gè)圖使它既是歐拉圖又是哈密爾頓圖.

(b)畫一個(gè)圖使它是歐拉圖但不是哈密爾頓圖.

(c)畫一個(gè)圖使它是哈密爾頓圖但不是歐拉圖.

(d)畫一個(gè)圖使它既不是歐拉圖又不是哈密爾頓圖.

初學(xué)者看到此類練習(xí),很少能有清晰的思路,眾多輔導(dǎo)書或習(xí)題解答常給出較為繁瑣的圖例[6],不太容易構(gòu)造也不利學(xué)生理解,有的學(xué)生甚至還需花上一些時(shí)間來判斷為什么這種圖符合條件.我們?cè)诖私o出簡易的結(jié)論，并輔以適當(dāng)簡潔的圖例,找出其中的規(guī)律，同時(shí)可加深對(duì)歐拉回路與哈密爾頓回路的區(qū)分.

定理1[2]圖G具有一條歐拉路徑當(dāng)且僅當(dāng)G具有零個(gè)或兩個(gè)奇數(shù)次數(shù)的頂點(diǎn).

定理2[2]一個(gè)連通圖是歐拉圖當(dāng)且僅當(dāng)該圖的頂點(diǎn)次數(shù)都是偶數(shù).

定理3[2]若圖G=是哈密爾頓圖,則對(duì)V的每個(gè)非空真子集S均成立:ω(G-S)≤|S|,其中|S|表示S中的頂點(diǎn)數(shù),ω(G-S)表示G刪去頂點(diǎn)集S后得到的圖的連通分圖個(gè)數(shù).

結(jié)論4由定義知判斷一個(gè)圖是否為歐拉圖,就是判斷該圖能否一筆畫出,即所謂的“一筆畫問題”.根據(jù)上述定理1、定理2可知判斷一個(gè)圖是否為歐拉圖,只需數(shù)一下該圖每個(gè)頂點(diǎn)的邊數(shù)是否都是偶數(shù).

結(jié)論5由定理3可知判斷一個(gè)圖是不是哈密爾頓圖,可采用刪除結(jié)點(diǎn)的方法.

解(a')我們畫一個(gè)三角形或一個(gè)四邊形，因它們顯然可以一筆畫出且經(jīng)過所有的點(diǎn)，故既是歐拉圖又是哈密爾頓圖.圖例如下：

(b')由于所需的圖不是哈密爾頓圖,可考慮將兩個(gè)圖通過合并某一結(jié)點(diǎn)粘合為一個(gè)圖,這樣刪除該結(jié)點(diǎn)便得到兩個(gè)分圖,于是不滿足定理3，從而不是哈密爾頓圖.又要求是歐拉圖,故用來粘合的圖可選擇具有歐拉回路的圖,這樣粘合后所得圖的每個(gè)頂點(diǎn)的次數(shù)仍為偶數(shù),故仍為歐拉圖.于是我們將兩個(gè)三角形或一個(gè)三角形與一個(gè)四邊形通過一個(gè)結(jié)點(diǎn)而粘合.圖例如下：

(c')由于所需的圖是哈密爾頓圖而不是歐拉圖,故只需找一四邊形,通過加上一些邊使其具有奇數(shù)次數(shù)的頂點(diǎn),從而不是歐拉圖.圖例如下:

(d')由于所需圖既不是歐拉圖又不是哈密爾頓圖，故可選用“圖(c1)”，再用(b')粘合的方法將其轉(zhuǎn)化為非哈密爾頓圖.或選用“圖(b2)”由(c')中添加邊的方法將其轉(zhuǎn)化為非歐拉圖.圖例如下：

〔1〕屈婉玲,耿素云,張立昂.離散數(shù)學(xué)[M].北京:清華大學(xué)出版社,2005.

〔2〕方世昌.離散數(shù)學(xué)[M].西安:西安電子科技大學(xué)出版社, 1996.

〔3〕徐俊明.圖論及其應(yīng)用[M].合肥:中國科學(xué)技術(shù)大學(xué)出版社,1998.

〔4〕翟明清.淺析圖論教學(xué)[J].大學(xué)數(shù)學(xué),2011，27(5):203-206.

〔5〕田京京.信息專業(yè)圖論課教學(xué)改革和實(shí)踐[J].中國電力教育，2011(8)：114-116.

〔6〕孫學(xué)紅，秦偉良.離散數(shù)學(xué)習(xí)題解答[M].西安:西安電子科技大學(xué)出版社,1999.

〔7〕左孝凌.離散數(shù)學(xué)理論、分析、題解[M].上海:上海科學(xué)技術(shù)出版社,1988.

G642

A

1673-260X（2013）07-0219-02

安徽省自然基金項(xiàng)目資助(KJ2011z057)