圖論課程的教學(xué)感悟

隋麗麗，張守成，韓元良，于 健

(華北科技學(xué)院基礎(chǔ)部，北京東燕郊 101601)

0 背景

我校開設(shè)這門課程已有7年時間，是一門比較有歷史的理工專業(yè)的公共選修課。圖論方法一直是科學(xué)家追求的目標之一。正如每個數(shù)學(xué)家必須精通微積分一樣，每個有作為的計算機科學(xué)技術(shù)工作者必須要有圖論方面的較高造詣。圖論的應(yīng)用領(lǐng)域及其廣泛，凡是涉及排列組合優(yōu)化問題的，都可以用圖論中的知識去解決。因此有人說圖論的重要性不論怎樣估計，也不會過分。圖論已經(jīng)是國內(nèi)很多高校理工科專業(yè)必修的一門課程，用來提高學(xué)生分析問題的能力，并為解決專業(yè)問題提供一種工具。

1 教學(xué)中的方式方法

1.1 圖論學(xué)習(xí)的必要性

圖論在計算機中的應(yīng)用已廣為人知，除此之外，在實際的生活生產(chǎn)中，也有大量問題可以用圖論的知識和方法來解決，高校里面的很多專業(yè)都要用到圖論的方法。例如，在工程管理中，為完成某項任務(wù)，各工序之間怎樣銜接，才能使得生產(chǎn)任務(wù)完成得既快又好;一個地區(qū)的通訊網(wǎng)絡(luò)要如何架設(shè)，交通網(wǎng)絡(luò)要如何布局?在經(jīng)濟管理中，一個旅行團要參觀多個景點，應(yīng)該如何安排路線?物質(zhì)的運輸要如何安排才能使得運輸成本最低?在計算機技術(shù)方面，圖論中的各種算法是程序設(shè)計的基礎(chǔ)和原理。為了讓施工人員能夠?qū)κ┕び媱澋臅r間，先后順序一目了然，我們可以根據(jù)施工計劃繪制相應(yīng)的雙代號網(wǎng)絡(luò)圖，圖論的研究對象是離散型的變量，在現(xiàn)實生活生產(chǎn)中，學(xué)生感受的離散型變量比微積分中的連續(xù)型變量更多，更普遍。

例如，價格，收費，工期(按天數(shù))等，那么相應(yīng)地，對離散型變量的體會也更加深刻，學(xué)習(xí)起來更加自然親切。圖論的研究工具直觀形象，一個由點和邊組成的圖表示現(xiàn)實世界的各種關(guān)系，簡單明了，學(xué)生易于理解。

《圖論及其應(yīng)用》是全院工程類各專業(yè)的一門選修課。此門課程的教學(xué)目的是使學(xué)生掌握圖論中常用的基礎(chǔ)理論知識，并掌握以此為基礎(chǔ)的常用的圖論算法及其應(yīng)用，使學(xué)生能夠靈活運用常見的計算機基本方法，從而在今后的工作中能夠具有獨立地分析和解決各類實際問題的能力。

1.2 結(jié)合教學(xué)經(jīng)驗，應(yīng)用案例教學(xué)

案例教學(xué)首創(chuàng)于哈佛大學(xué)商學(xué)院，在經(jīng)貿(mào)、管理、法學(xué)等學(xué)科領(lǐng)域的相關(guān)專業(yè)得到應(yīng)用并取得顯著成效。目前理工科專業(yè)還較少運用案例教學(xué)方法，主要困難是:理工科專業(yè)的案例教學(xué)實踐較晚，可供借鑒的成功經(jīng)驗較少;難以獲得兼顧真實性和教學(xué)時限等要求的教學(xué)案例;理工科領(lǐng)域體系龐大，專業(yè)繁多，不同專業(yè)之間案例共享性較差。作為我校工工程類專業(yè)的一門選修課——圖論及其應(yīng)用，因其專業(yè)背景廣，應(yīng)用多面，而存在眾多成功的應(yīng)用案例，若將這些成功案例用于實踐教學(xué)環(huán)節(jié)，《圖論及其應(yīng)用》課程將在培養(yǎng)高素質(zhì)的應(yīng)用型人才方面發(fā)揮更大的作用。

本校開設(shè)的圖論及其應(yīng)用課程要求學(xué)生掌握的原理相對來說也比較淺顯，只需要學(xué)生了解這個有力工具，為今后的繼續(xù)學(xué)習(xí)提供一種可參考的工具。譬如最小生成樹原理，如果按照數(shù)學(xué)專業(yè)學(xué)生的教學(xué)要求，原理內(nèi)容，證明方法，證明過程，以及相關(guān)算法都需詳細講解，但作為選修課，在講解過程中，只需聯(lián)系工程實際問題，講解其應(yīng)用方向，這樣的內(nèi)容淺顯易懂，不至于讓學(xué)生望而生畏。教學(xué)過程中，為了激發(fā)學(xué)生的興趣和動力，應(yīng)該結(jié)合現(xiàn)實生活和專業(yè)實際，從案例分析引入基本概念和原理，在簡明扼要，直觀形象地講解概念和原理以后，再回到案例分析，解決實際問題。一般引入的案例追求普遍性，典型性，生活化，而應(yīng)用的案例則偏向?qū)I(yè)性，生產(chǎn)化，挑戰(zhàn)性。

如在第一堂課就可以簡單介紹圖論中很典型的有趣問題，像(立陶宛)哥尼斯堡城七橋問題，也包括愛爾蘭數(shù)學(xué)家哈密頓(Halmiton)提出的“周游世界”的游戲，一筆畫問題，最短郵路問題等，介紹這些案例的背景，內(nèi)容，保留結(jié)論，極大地激發(fā)學(xué)生的求知探索欲，向?qū)W生傳輸圖論源于自然，也源于簡單，消除他們的畏難情緒［1－4］。在后續(xù)的教學(xué)中，可在講解圖的連通性和連通度內(nèi)容時，和同學(xué)一起解決緒論中提出的問題;在講解匹配章節(jié)時，就可引入像人員安排問題，貨郎送貨等問題;在講解連通度時，可介紹投遞員問題;講染色問題時，可提出地圖染色至少需要幾種顏料的問題［5－8］。這些實際有趣的問題會讓學(xué)生真正的參與到教學(xué)活動中，主動思考得到的答案更深刻，從而收獲更多，提高了教學(xué)質(zhì)量。

1.3 與專業(yè)的結(jié)合

圖論的應(yīng)用幾乎滲透到了每個理工專業(yè)，因此教師在講課中注意和學(xué)生專業(yè)的結(jié)合，會使選修這門課的相關(guān)專業(yè)學(xué)生有主人翁意識，增強學(xué)習(xí)欲望。目前圖論知識的應(yīng)用比比皆是。比如在講解圖的頂點和邊的時候，就可以介紹利用這一節(jié)的內(nèi)容去描述巖石的裂隙縫網(wǎng)，刻畫其特征，這在安全、采礦以及土木建筑專業(yè)都是非常關(guān)鍵的一個處理片段;在講最短路徑算法的時候，就可以講解其思想方法在編程方面的應(yīng)用，計算機、管理等專業(yè)的同學(xué)都會受益匪淺。

2 結(jié)論

1)每種圖論方法理論的產(chǎn)生與發(fā)展都有一個不同尋常的開始，讓一個個活生生的應(yīng)用案例貫穿課堂教學(xué)中，啟發(fā)學(xué)生的興趣，鼓勵他們在案例的展開中發(fā)現(xiàn)問題，尋找規(guī)律，從而達到教學(xué)目的。

2)當(dāng)今社會的高速發(fā)展，圖論已經(jīng)滲透到現(xiàn)實生活的各個領(lǐng)域，因此圖論教學(xué)也面臨著考驗，在教學(xué)過程中，要讓圖論為選課學(xué)生的專業(yè)服務(wù)，結(jié)合專業(yè)背景介紹圖論內(nèi)容，體現(xiàn)出這門選修課的重要與實用性。

［1］ 馬奎香.圖論教學(xué)方法研究［J］.教育學(xué)研究，2012，(10):37－38.

［2］ 王樹禾.圖論教學(xué)思想［J］.教育與現(xiàn)代化，1987，(1):18－23.

［3］ 胡傳峰.圖論教學(xué)方法探析［J］.中國科技信息，2012，(1):235.

［4］ 錢建國.淺談算法實例在圖論教學(xué)中的作用［J］.莆田學(xué)院學(xué)報，2004，(11):70 －71.

［5］ 楊朝鳳.基于接受學(xué)習(xí)與探究學(xué)習(xí)的圖論教學(xué)設(shè)計與實踐［J］. 保山師專學(xué)報，2007，(2):30－32.

［6］ 曲晚玲，耿素云，張立昂.離散數(shù)學(xué)［M］.北京:高等教育出版社，2008.

［7］ 魏麗俠，王濤，隋麗麗，等.圖論及其應(yīng)用［M］.北京:中國礦業(yè)大學(xué)出版社，2012.

［8］ 王樹禾.圖論［M］.北京:科學(xué)出版社，2008.