孔翔宇　王貞　孫瀅

【摘要】本文針對圖論的教學(xué)現(xiàn)狀，結(jié)合信息專業(yè)的特點，提出了建立課程群，講義編寫等教學(xué)改革措施。同時也提出了課堂教學(xué)和實踐教學(xué)的教學(xué)方法。

【關(guān)鍵詞】圖論 教學(xué)改革 教學(xué)方法

【基金項目】寧夏回族自治區(qū)高等學(xué)校教育教學(xué)改革項目：《神經(jīng)網(wǎng)絡(luò)計算》專題研究型教學(xué)模式探索與實踐（寧教高[2012]348號）。

【中圖分類號】G633.67 【文獻(xiàn)標(biāo)識碼】A 【文章編號】2095-3089（2014）01-0140-01

圖論是組合數(shù)學(xué)和離散數(shù)學(xué)的重要組成部分。圖論起源于著名的哥尼斯堡七橋問題[1-2]。它以圖為研究對象，把研究的事物抽象成若干點，將事物間存在的關(guān)系用線來表示，如果兩事物間存在關(guān)系，就用一條邊將它們連接起來，經(jīng)過上述方法所做的圖形就是圖論中的圖。自然科學(xué)和社會科學(xué)中諸多領(lǐng)域的關(guān)系都可以用圖論中的圖來表示，對于這些問題建立相應(yīng)模型之后再去研究往往能夠得到良好的結(jié)果，故對于圖論中圖的研究就顯得特別重要，得到了眾多專家和學(xué)者的關(guān)注。

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

由于圖論在許多領(lǐng)域有著重要的應(yīng)用[3-4]，許多大學(xué)都把圖論作為一門專業(yè)課單獨開設(shè)，作為數(shù)學(xué)、計算機、電子、管理等專業(yè)高年級本科生和研究生的必修或選修課。圖論在教學(xué)過程中具有如下特點：

1.圖論中基本概念、定理非常多，概念不易理解，定理證明又特別難，這就在一定程度上使教學(xué)枯燥難懂。

2.圖論研究的許多問題都具有實際應(yīng)用背景，但往往很難轉(zhuǎn)化成圖論模型，不容易求解，從而造成了學(xué)生對圖論學(xué)習(xí)很有興趣，但因為不能求解而產(chǎn)生厭學(xué)心理。

3.圖論課程涉及的算法非常多，對于每個問題幾乎都有不同的算法。例如最小生成樹的求法就有克魯斯克爾算法，管梅谷的破圈法、Prim算法等十幾種算法，如果要求學(xué)生編程求解實際問題，那么對學(xué)生的算法分析能力以及程序設(shè)計能力就提出了很高的要求。

通過在本校講授該課程發(fā)現(xiàn)學(xué)生并不滿足于圖論算法的證明和紙上求解，迫切需要掌握如何利用計算機來實現(xiàn)算法并求解實際問題。這就促使我們探討圖論課程的教學(xué)改革。

二、圖論課程的教學(xué)改革

根據(jù)信息與計算科學(xué)專業(yè)人才培養(yǎng)要求以及圖論課程的教學(xué)現(xiàn)狀，提出如下教學(xué)改革措施。

1.建立課程群

任何一門課程都不是孤立的，總是存在一門或者若干門課程與它相關(guān)，因此很多高校通過建設(shè)課程群來構(gòu)建完整的知識體系，優(yōu)化課程安排，在較少的人力物力下達(dá)到最高的教學(xué)目標(biāo)。圖論課程的教學(xué)目標(biāo)是培養(yǎng)學(xué)生算法分析、設(shè)計和實際問題的應(yīng)用能力，而“程序設(shè)計”、“數(shù)據(jù)結(jié)構(gòu)”、“算法分析設(shè)計”等課程也是培養(yǎng)學(xué)生的算法分析、設(shè)計能力，這和圖論課程的教學(xué)目標(biāo)是相同的。所以，可以將這些課組合在一起建立課程群。通過課程學(xué)習(xí)，學(xué)生不但掌握了豐富的圖論知識，算法分析與設(shè)計能力也將會得到進(jìn)一步鞏固和加強。

2.做好教材建設(shè)，編寫適合教學(xué)目標(biāo)的圖論講義、教材

教材建設(shè)是任何一門課程建設(shè)的重中之重，教材主要包括教學(xué)中使用的教材或講義、輔導(dǎo)教材等。為適應(yīng)新的更高的教學(xué)目標(biāo)編寫課程講義。具體教材改革如下：

（1）將目前各大高校普遍使用的圖論教材中50%左右的定理證明略去，不再詳細(xì)證明，僅對一些經(jīng)典證明進(jìn)行詳細(xì)闡述，重點分析圖論課程所涉及的算法思想。

（2）在課程課時有限的條件下，如何發(fā)掘?qū)W生的自學(xué)能力是教師要思考的問題。這就要求教師為學(xué)生提供實例較多的參考書籍。

（3）對同一問題采用不同的算法，分析所得結(jié)果的差異。重點討論為什么會產(chǎn)生這種差異。

三、圖論課程的教學(xué)方法

一種新的課程教學(xué)思路必須有一套新穎的、行之有效的教學(xué)方法與之配套，所以必須重視探索恰到好處的教學(xué)方法。

1.課堂教學(xué)

課堂教學(xué)是教學(xué)過程的重中之重，在教學(xué)中可以采取如下方法加強課堂教學(xué)效果：

（1）上好圖論課程的第一次課。第一次課的教學(xué)效果往往會決定學(xué)生是否會對這門課程有興趣，是否愿意認(rèn)真學(xué)習(xí)這門課。對圖論課程的第一次課，可以從一些有趣的實際問題入手，如哥尼斯堡七橋問題、中國旅行商問題、中國郵路問題、圖的著色等。這些問題簡單易懂，清晰明了，十分有趣。更主要的是，這些實際問題可以把圖論中的主要研究內(nèi)容串聯(lián)在一起，從而讓使學(xué)生對圖論這門課程有直觀的了解。

（2）加強課堂互動。圖論的很多問題來源于現(xiàn)實世界的生產(chǎn)生活，在學(xué)生的校園學(xué)習(xí)生活中也能找到相應(yīng)的例子。在課堂上，使學(xué)生成為課堂教學(xué)的主體，讓學(xué)生在黑板上演示問題相應(yīng)算法的求解步驟，這對學(xué)生理解算法思想和求解過程將起到重要作用。

（3）加強算法的分析對比實驗。為了使學(xué)生對圖論中的算法復(fù)雜度有直觀認(rèn)識，通常在分析完圖論算法復(fù)雜度之后，對部分問題進(jìn)行計算機仿真實驗，通過反饋回來的算法運行時間來驗證算法的復(fù)雜度。

2.實踐教學(xué)

為了促進(jìn)學(xué)生對圖論的學(xué)習(xí)興趣，要積極引導(dǎo)學(xué)生閱讀論文和文獻(xiàn)綜述，為今后的專業(yè)發(fā)展夯實基礎(chǔ)，在教學(xué)中要開展豐富的實踐教學(xué)內(nèi)容。這里討論的實踐教學(xué)不單指實驗課。具體在實踐教學(xué)中可以采取如下方法：

（1）在求解問題時，通過培養(yǎng)學(xué)生查閱文獻(xiàn)的能力，指導(dǎo)學(xué)生閱讀相關(guān)論文。

（2）圖論中有許多至今仍沒得到解決的問題或者是解決得不好的問題，國內(nèi)外相關(guān)專家和學(xué)者對這些問題的研究一直沒有中斷，可以向?qū)W生介紹相關(guān)問題，一起探討，培養(yǎng)學(xué)生產(chǎn)生濃厚的學(xué)習(xí)興趣。

（3）在學(xué)習(xí)完一章或者一部分內(nèi)容之后，可以對這些教學(xué)內(nèi)容以小論文的形式提交作業(yè)，作為考試成績的一部分。

四、結(jié)束語

通過對圖論課程的一系列教學(xué)改革，提高了學(xué)生的學(xué)習(xí)熱情，更好的實現(xiàn)了教學(xué)目標(biāo)。如何更深層次的解決圖論課程改革問題是進(jìn)一步需要解決的問題。

參考文獻(xiàn)：

[1]徐俊明. 圖論及其應(yīng)用[M]. 2 版. 合肥：中國科學(xué)技術(shù)大學(xué)出版社，2004.

[2]杜承銘. 本科應(yīng)用型人才培養(yǎng)目標(biāo)的選擇、構(gòu)建及實現(xiàn)[J]. 教育與職業(yè)，2006，（32）：20-22.

[3]張憲超，陳國良，萬穎瑜. 網(wǎng)絡(luò)最大流問題研究進(jìn)展[J]. 計算機研究與發(fā)展，2003，40（9）：1281-1292.

[4]錢建國. 淺談算法實例在圖論教學(xué)中的作用[J]. 莆田學(xué)院學(xué)報，2004，11（3）：70-71.

作者簡介：

孔翔宇（1982-），男，吉林榆樹人，在讀博士，講師，主要研究方向最優(yōu)化理論、智能算法、高等教育學(xué)。