離散數學中圖論教學的探討

呂誠，孫秀華

（安徽建筑大學數理系，安徽合肥230022）

離散數學中圖論教學的探討

呂誠，孫秀華

（安徽建筑大學數理系，安徽合肥230022）

離散數學圖論部分具有概念多，定理多，內容豐富，學習難度大等特點，但其對計算機科學等相關專業大學生的后續課程又極為重要，因此本文試圖探索如何激發貫穿整個課程的各種興趣點，引導學生自發式學習.同時也探討類比式的教學方式在該課程的具體實施方法.

離散數學；圖論；歐拉圖；哈密爾頓圖；教學

1 引言

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

2 興趣帶動教學的方式

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

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

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

3 類比教學的方式

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

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

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

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

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

初學者看到此類練習,很少能有清晰的思路,眾多輔導書或習題解答常給出較為繁瑣的圖例[6],不太容易構造也不利學生理解,有的學生甚至還需花上一些時間來判斷為什么這種圖符合條件.我們在此給出簡易的結論，并輔以適當簡潔的圖例,找出其中的規律，同時可加深對歐拉回路與哈密爾頓回路的區分.

定理1[2]圖G具有一條歐拉路徑當且僅當G具有零個或兩個奇數次數的頂點.

定理2[2]一個連通圖是歐拉圖當且僅當該圖的頂點次數都是偶數.

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

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

結論5由定理3可知判斷一個圖是不是哈密爾頓圖,可采用刪除結點的方法.

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

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

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

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

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

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

〔3〕徐俊明.圖論及其應用[M].合肥:中國科學技術大學出版社,1998.

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

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

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

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

G642

A

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

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