在圖論課程中融入數(shù)學(xué)建模思想的教學(xué)改革初探

孫培　劉凱　曾俊杰　楊本朝

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

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

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

一、引言

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

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

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

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

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

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

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

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

min■wijxij；

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

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

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

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

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

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

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

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

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

四、結(jié)束語(yǔ)

總之，在圖論教學(xué)中融入數(shù)學(xué)建模的思想和方法，順應(yīng)了數(shù)學(xué)教學(xué)改革的方向，調(diào)動(dòng)了學(xué)生的學(xué)習(xí)主動(dòng)性和積極性。教師通過(guò)布置大作業(yè)、上討論課，使學(xué)生對(duì)所學(xué)知識(shí)進(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é)任編輯：鐘偉芳]