孫培　劉凱　曾俊杰　楊本朝

[摘 要]基于圖論教學(xué)的重要性及圖論課程的教學(xué)現(xiàn)狀，可以將教學(xué)建模的思想和方法融入圖論教學(xué)中，以開拓學(xué)生的視野，培養(yǎng)學(xué)生學(xué)習(xí)數(shù)學(xué)的興趣和應(yīng)用意識，提高學(xué)生應(yīng)用數(shù)學(xué)知識和方法解決實(shí)際問題的能力。

[關(guān)鍵詞]圖論 數(shù)學(xué)建模 優(yōu)化問題 教學(xué)改革

[中圖分類號] G642 [文獻(xiàn)標(biāo)識碼] A [文章編號] 2095-3437（2015）08-0118-02

一、引言

圖論是離散數(shù)學(xué)和組合數(shù)學(xué)的重要分支，它以圖為研究對象，這種圖由若干給定的點(diǎn)及連接兩點(diǎn)的邊所構(gòu)成，通常用來描述某些事物之間的某種特定關(guān)系。圖論起源于18世紀(jì)著名的哥尼斯堡七橋問題，現(xiàn)已發(fā)展成為一門應(yīng)用數(shù)學(xué)課程。由于自然科學(xué)中許多領(lǐng)域的問題可以轉(zhuǎn)化為圖論問題，故圖論越來越得到相關(guān)領(lǐng)域和專家的廣泛關(guān)注。下面筆者談?wù)剤D論課程的教學(xué)現(xiàn)狀以及在圖論課程中融入數(shù)學(xué)建模思想的教學(xué)實(shí)踐。

二、圖論課程的教學(xué)現(xiàn)狀

圖論和其他數(shù)學(xué)課程一樣，有著大量抽象的、深奧的概念與理論。如果教師按常規(guī)的教學(xué)方法，將授課重點(diǎn)放在圖論基本理論的傳授上，放在定理的證明中，學(xué)生往往會感到枯燥乏味，缺乏學(xué)習(xí)興趣。另外，學(xué)生學(xué)習(xí)圖論這門課的目的是通過對圖論中各種算法的學(xué)習(xí)，培養(yǎng)自己的編程能力和解決實(shí)際問題的能力。這就對我們的圖論教學(xué)提出了新的要求。數(shù)學(xué)建模是聯(lián)系數(shù)學(xué)理論與實(shí)際的一座橋梁，是解決實(shí)際問題的強(qiáng)有力的工具。因此，我們在圖論教學(xué)中可融入數(shù)學(xué)建模思想，突出知識的應(yīng)用，讓學(xué)生帶著問題來，在解決問題的過程中與教師交流，課后帶著問題去，把數(shù)學(xué)建模的意識、思想貫穿在圖論的每一個(gè)問題的解決過程中，最后歸納總結(jié)出數(shù)學(xué)思想和方法，讓學(xué)生學(xué)會如何運(yùn)用數(shù)學(xué)理論去解決實(shí)際問題[1]，從“學(xué)數(shù)學(xué)”到“用數(shù)學(xué)”，培養(yǎng)學(xué)生分析問題、解決問題的能力。

三、在圖論課程中融入數(shù)學(xué)建模思想的教學(xué)實(shí)踐

1.充分利用網(wǎng)絡(luò)資源，進(jìn)行資源型學(xué)習(xí)。隨著計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)的飛速發(fā)展，互聯(lián)網(wǎng)所承載的信息量越來越大，更新速度越來越快，這就使得學(xué)習(xí)的資源由傳統(tǒng)的課本向豐富的網(wǎng)絡(luò)資源擴(kuò)充。學(xué)生可利用網(wǎng)絡(luò)查詢知識，共同討論。教師的教學(xué)手段也發(fā)生了改變，從傳統(tǒng)的傳道授業(yè)變成了注重教給學(xué)生如何利用網(wǎng)絡(luò)獲取知識，查找文獻(xiàn)。筆者在教學(xué)中充分利用網(wǎng)絡(luò)資源，不僅提高了教學(xué)效率，而且培養(yǎng)了學(xué)生的自學(xué)能力和創(chuàng)新能力。

例如，在備課時(shí)，充分利用互聯(lián)網(wǎng)，獲取大量的圖論信息資源，特別是國家精品課程等網(wǎng)站，提供了教學(xué)大綱、教學(xué)錄像、電子教案等教學(xué)素材，教師可參考、借鑒同行的教學(xué)思路和課件，博采眾長，提高備課的效率和質(zhì)量[2]。同時(shí)，圖論中的許多問題有多種算法，教師授課時(shí)不可能面面俱到，而應(yīng)重點(diǎn)講解比較經(jīng)典和基礎(chǔ)的算法，對于其他算法，可以給出名字，鼓勵學(xué)生課后自己查找文獻(xiàn)資料。這樣，既講清楚了如何解決問題，又培養(yǎng)了學(xué)生的自學(xué)能力。

2.以解決實(shí)際問題為目的，注重建立問題的數(shù)學(xué)模型。圖論起源于實(shí)際問題，與實(shí)際生活聯(lián)系非常緊密，圖論中的許多問題都可以建立數(shù)學(xué)模型，從而優(yōu)化問題。授課中，我們不僅要講授解決問題的經(jīng)典算法，而且要建立問題的數(shù)學(xué)模型，將數(shù)學(xué)建模思想融入其中，鼓勵學(xué)生用多種方法解決問題。

例如，對于最短路問題，有經(jīng)典的Dijkstra算法，同時(shí)我們經(jīng)過分析，可以引入0-1決策變量xij，即當(dāng)邊（i，j）在最后選定的最短路徑上時(shí)，xij=1，否則為0，因此可以建立如下的數(shù)學(xué)模型[3]：

min■wijxij；

s.t.■xij=■xji，（1對于這兩種方法，要講清楚優(yōu)缺點(diǎn)：Dijkstra算法對權(quán)為負(fù)的問題不適用，但是可以求一固定點(diǎn)到其他點(diǎn)的最短路徑；而建立數(shù)學(xué)模型的方法不受權(quán)為負(fù)的限制，但稍顯死板，如果變換一個(gè)頂點(diǎn)，就要重新編程求解。

再如，對于最小生成樹問題，有Kruskal算法和Prim算法，兩種算法的復(fù)雜度分別為O（mlogm）和O（n2）[4]，其中m為邊數(shù)，n為點(diǎn)的個(gè)數(shù)。因此，他們的適用范圍是不同的，前者適用于邊比較少的圖，后者適用于點(diǎn)比較少的圖。經(jīng)過這樣以應(yīng)用為目的的教學(xué)，使學(xué)生更加深刻地理解了問題，并為其以后的學(xué)習(xí)和工作中打下基礎(chǔ)。

3.在教學(xué)過程中強(qiáng)調(diào)數(shù)學(xué)思想。在教學(xué)過程中，要培養(yǎng)大學(xué)生的創(chuàng)造性思維，就要以數(shù)學(xué)思想為靈魂，統(tǒng)帥整個(gè)教學(xué)過程，圖論的教學(xué)更不例外。我們既然強(qiáng)調(diào)用數(shù)學(xué)建模思想解決圖論問題，就要將這個(gè)理念貫穿教學(xué)的全過程，同時(shí)注意歸納總結(jié)。

例如，在對許多問題進(jìn)行建模的過程中，我們都是建立了一個(gè)決策變量xij，然后用這個(gè)決策變量來分析問題，得出數(shù)學(xué)模型。因此，這種引入決策變量，巧妙地將圖論中的問題用矩陣表示出來的思想和方法值得我們學(xué)習(xí)。這樣的教學(xué)讓學(xué)生感受和了解數(shù)學(xué)知識的發(fā)生和形成過程，引導(dǎo)學(xué)生如何將實(shí)際問題轉(zhuǎn)化成數(shù)學(xué)問題，然后用數(shù)學(xué)思想和方法來解決。

4.結(jié)合課程特點(diǎn)，精選教學(xué)內(nèi)容，對傳統(tǒng)內(nèi)容優(yōu)化組合，推陳出新。對于傳統(tǒng)的圖論教材，可刪除陳舊的內(nèi)容和復(fù)雜的推理過程，將授課重點(diǎn)放在圖論思想的講述和算法實(shí)現(xiàn)上。

例如，大部分教材將最小生成樹問題單獨(dú)作為一章來講解，將歐拉問題和旅行商問題作為一章來講解。但由于我們在教學(xué)過程中注重啟發(fā)學(xué)生建立數(shù)學(xué)模型，并用Lingo數(shù)學(xué)軟件編程進(jìn)行解決，因此我們對內(nèi)容進(jìn)行了重新優(yōu)化組合。由于最小生成樹問題和旅行商問題的數(shù)學(xué)模型、數(shù)學(xué)思想大致相同，因此我們將這兩部分作為一章來講解，使學(xué)生在建立數(shù)學(xué)模型的過程中深刻理解這兩個(gè)問題。

再如，許多教材把匹配問題與指派問題放在了網(wǎng)絡(luò)流問題的前面，但我們通過查閱文獻(xiàn)發(fā)現(xiàn)，二部圖的最大匹配問題可以轉(zhuǎn)化成網(wǎng)絡(luò)的最大流問題，從而可以用網(wǎng)絡(luò)流的算法求解，因此我們將內(nèi)容重新調(diào)整，把網(wǎng)絡(luò)流問題放到匹配問題前面講解。同時(shí)，在講解歐拉問題時(shí)，對不是歐拉圖的圖G求歐拉回路，首先要把它變成歐拉圖，再用Fleury算法求解。在將圖G轉(zhuǎn)化成歐拉圖的過程中，需要求度數(shù)為奇的頂點(diǎn)的最小權(quán)匹配，因此，在授課時(shí)，我們也把匹配問題放到歐拉圖前面講解。

經(jīng)過這樣的組合教學(xué)，學(xué)生感覺到所學(xué)知識是一個(gè)整體，而不是問題與問題是相互獨(dú)立的關(guān)系。同時(shí)，看似兩個(gè)不相關(guān)的問題，經(jīng)過分析，能夠轉(zhuǎn)化成一樣的問題，也鍛煉了學(xué)生思考問題、分析問題和解決問題的能力。

5.增加Lingo數(shù)學(xué)軟件的介紹與應(yīng)用，培養(yǎng)學(xué)生的實(shí)踐創(chuàng)新能力。傳統(tǒng)的基礎(chǔ)教學(xué)注重理論性，缺乏實(shí)際應(yīng)用，對后續(xù)的其他專業(yè)課程幫助不大。我們要在授課中突出知識的應(yīng)用思想，講解相應(yīng)的數(shù)學(xué)軟件，培養(yǎng)學(xué)生的動手能力。圖論中的許多問題都能轉(zhuǎn)化成優(yōu)化問題，而求解優(yōu)化問題非常好用且容易上手的軟件就是Lingo軟件。因此，我們在授課時(shí)將Lingo軟件作為輔助教學(xué)的工具，將理論教學(xué)和實(shí)驗(yàn)演示融為一體，使學(xué)生更加深刻地理解相關(guān)理論和算法，提高課堂教學(xué)效率。實(shí)踐證明，在圖論教學(xué)中使用數(shù)學(xué)軟件，有助于加深學(xué)生對抽象理論與算法的理解，調(diào)動學(xué)生自主學(xué)習(xí)和創(chuàng)新學(xué)習(xí)的積極性，提高學(xué)生的動手能力和科研能力。

四、結(jié)束語

總之，在圖論教學(xué)中融入數(shù)學(xué)建模的思想和方法，順應(yīng)了數(shù)學(xué)教學(xué)改革的方向，調(diào)動了學(xué)生的學(xué)習(xí)主動性和積極性。教師通過布置大作業(yè)、上討論課，使學(xué)生對所學(xué)知識進(jìn)行加工轉(zhuǎn)換、重組再現(xiàn)，鍛煉了學(xué)生的數(shù)學(xué)思維，提高了學(xué)生的編程能力和實(shí)踐創(chuàng)新能力，取得了良好的教學(xué)效果。

[ 參 考 文 獻(xiàn) ]

[1] 裴振奎，徐九韻.MATLAB在“圖論”課程教學(xué)中的應(yīng)用[J].計(jì)算機(jī)科學(xué)，2010，37（7）：108-110.

[2] 康云艷，楊暹，郝振萍.網(wǎng)絡(luò)資源在《蔬菜栽培學(xué)》教學(xué)中的應(yīng)用[J].安徽農(nóng)業(yè)科學(xué)，2011，39（9）：5628-5629.

[3] 謝金星，薛毅.優(yōu)化建模與lindo / lingo軟件[M].北京：清華大學(xué)出版社，2005.

[4] 龔劬.圖論與網(wǎng)絡(luò)最優(yōu)化算法[M].重慶：重慶大學(xué)出版社，2009.

[責(zé)任編輯：鐘偉芳]