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

孫培　劉凱　曾俊杰　楊本朝

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

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

[中圖分類號] G642 [文獻標識碼] A [文章編號] 2095-3437（2015）08-0118-02

一、引言

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

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

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

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

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

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

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

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

min■wijxij；

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

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

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

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

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

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

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

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

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

四、結束語

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

[ 參 考 文 獻 ]

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

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

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

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

[責任編輯：鐘偉芳]