《圖論及其應(yīng)用》優(yōu)質(zhì)課程建設(shè)的探索與實踐

張清華　陳六新

摘要：針對我校研究生公共基礎(chǔ)課《圖論及其應(yīng)用》優(yōu)質(zhì)課程建設(shè)的實際情況以及教學(xué)中存在的問題，該文總結(jié)了我們在《圖論及其應(yīng)用》課程的教學(xué)改革、教材建設(shè)、師資隊伍建設(shè)、網(wǎng)站建設(shè)等方面建設(shè)研究生優(yōu)質(zhì)核心課程的經(jīng)驗。通過近幾年的建設(shè)，目前課程在教學(xué)目標(biāo)、教學(xué)內(nèi)容、教學(xué)手段和考核評價等方面具有一定的優(yōu)勢和特色。

關(guān)鍵詞：課程建設(shè)；圖論；教學(xué)改革；教學(xué)內(nèi)容

1概述

大量事物以及事物之間的關(guān)系，常可用圖形來描述，如物質(zhì)結(jié)構(gòu)、通信網(wǎng)絡(luò)、交通規(guī)劃、工作調(diào)配、算法流程等都可以用點和線連起來所組成的圖形來模擬。圖論是數(shù)學(xué)的一個重要分支，是研究自然科學(xué)、工程技術(shù)、社會科學(xué)等問題的一個重要的現(xiàn)代數(shù)學(xué)工具。國內(nèi)外有許多高等院校已為數(shù)學(xué)、計算機科學(xué)、通信工程、控制與管理科學(xué)等學(xué)科的研究生和信息與計算科學(xué)專業(yè)的本科生開設(shè)了圖論課程。我校通信類、計算機類、自動化類、經(jīng)管類、物理類、系統(tǒng)科學(xué)類等學(xué)科的研究生培養(yǎng)方案把《圖論及其應(yīng)用》作為學(xué)位課來開設(shè)。教學(xué)規(guī)模逐年擴大，每年有近600人愿意修這門課程，而大約有400人成功選課，受益面非常廣泛。

然而，隨著我校研究生規(guī)模擴大，研究生教育教學(xué)改革得深化，在著力提升研究生教學(xué)質(zhì)量的關(guān)鍵時期，迫切需要加強課程建設(shè)，特別是《圖論及其應(yīng)用》這門公共基礎(chǔ)課程的建設(shè)，更新和優(yōu)化教學(xué)內(nèi)容，實現(xiàn)信息化教學(xué)，以致培養(yǎng)新世紀(jì)的IT創(chuàng)新人才?！秷D論及其應(yīng)用》課程的開設(shè)正是為著這個目的，它對拓寬學(xué)生的知識面，優(yōu)化學(xué)生的知識和能力結(jié)構(gòu)具有極其重要的意義。

隨著最近教育部《關(guān)于全面提高高等教育質(zhì)量的若干意見》和重慶市教委《關(guān)于推進協(xié)同創(chuàng)新，全面提高高等教育質(zhì)量的若干意見》的改革舉措相繼出臺，很多高校在面臨擴大研究生規(guī)模、深化研究生教育教學(xué)改革、提升研究生教育質(zhì)量和培養(yǎng)研究生創(chuàng)新能力的關(guān)鍵時期，迫切需要加強公共基礎(chǔ)課的教學(xué)質(zhì)量，夯實工科學(xué)生數(shù)學(xué)基礎(chǔ)，特別是急需加強研究生課程建設(shè)，尤其是量大面廣的公共基礎(chǔ)課程的建設(shè)。為此，學(xué)校高度

重視該課程的建設(shè)和教學(xué)團隊的發(fā)展，2011年學(xué)校將《圖論及其應(yīng)用》課程列為重慶郵電大學(xué)研究生教育創(chuàng)新計劃重點項目來加以建設(shè)，目前該課程在教學(xué)內(nèi)容體系、教學(xué)大綱、網(wǎng)絡(luò)資源、教材建設(shè)等方面取得突出成果，課程教學(xué)團隊年齡、學(xué)歷、職稱結(jié)構(gòu)顯著改善，該課程已初現(xiàn)優(yōu)質(zhì)課程的特征。

2《圖論及其應(yīng)用》課程當(dāng)前存在的主要問題

就目前來講，我?！秷D論及其應(yīng)用》課程教學(xué)雖然取得了長足的進步，基本能夠適應(yīng)學(xué)生對課程基本知識的需求。但是，在課程建設(shè)、教材建設(shè)、信息化建設(shè)、師資隊伍建設(shè)等方面還需要進一步完善，特別是作為以信息學(xué)科為特色的教學(xué)研究型大學(xué)的研究生教育的一門公共基礎(chǔ)課，主要存在如下問題：

2.1教學(xué)內(nèi)容需要進一步凸顯工科專業(yè)特色

當(dāng)前，《圖論及其應(yīng)用》課程教學(xué)內(nèi)容還是有些重理論、重推導(dǎo)，對圖論中的原理在信息學(xué)科中的應(yīng)用滲透不夠，應(yīng)用背景挖掘不夠。圖論的概念、公式和定理比較多，定理的證明通常相對較難，在一定程度上造成教學(xué)枯燥難懂。因此，在教學(xué)中往往忽略了圖論與多學(xué)科的橫向交叉聯(lián)系和實際應(yīng)用背景，使得學(xué)生難以靈活運用圖論模型來解決各種實際問題，特別是在授課過程中如何將圖論算法的分析、復(fù)雜度分析、最大流算法、最短路徑算法和網(wǎng)絡(luò)優(yōu)化等方面與電子信息學(xué)科的專業(yè)背景有機結(jié)合方面還有些欠缺，究其原因在于兩個方面，第一很多教材對應(yīng)用內(nèi)容涉及太少，第二授課教師的學(xué)科背景知識本身較為缺乏。因此，加強教材建設(shè)和擴充教師相關(guān)學(xué)科背景知識是我們需要解決的問題。

2.2教學(xué)資源需要進一步完善

隨著學(xué)校推出的一系列提高研究生教學(xué)質(zhì)量舉措，《圖論及其應(yīng)用》課程被列為校研究生創(chuàng)新計劃重點項目進行建設(shè)，教學(xué)資源得到有效補充。雖然我們開發(fā)創(chuàng)建了圖論課程教學(xué)網(wǎng)站，并有基本的教學(xué)內(nèi)容，但是如何充分發(fā)揮課程網(wǎng)站的功能，急需補充優(yōu)質(zhì)課程要求的更高層次的教學(xué)資源：習(xí)題庫、教學(xué)錄像、試題庫、實踐討論題庫、考評系統(tǒng)等，需要進一步補充相應(yīng)的教學(xué)資源。當(dāng)前，課程網(wǎng)站的教學(xué)互動模塊需要開發(fā)利用，實現(xiàn)更加有效的網(wǎng)絡(luò)答疑、師生互動；同時需要共享課程資源、課程錄像、多媒體教學(xué)課件等；開發(fā)系統(tǒng)實現(xiàn)遠程訪問與教學(xué)探討，擴大課程的影響力，發(fā)揮課程輻射示范作用。因此，進一步完善教學(xué)資源，實現(xiàn)優(yōu)質(zhì)課程資源共享是需要重點解決的問題之一。

2.3教學(xué)研究和教學(xué)改革需要進一步深入

圖論是一門覆蓋內(nèi)容非常廣泛的交叉學(xué)科，圖論的產(chǎn)生和發(fā)展得益于各學(xué)科的交叉和滲透。因此，圖論提供的理論和方法應(yīng)用于不同學(xué)科，各學(xué)科的發(fā)展又為圖論提供新的概念、新的研究課題和新的研究方法。目前來講，我們的教學(xué)還是主要圍繞圖論的基本數(shù)學(xué)理論，在教學(xué)內(nèi)容上還需要進一步與通信工程、計算機科學(xué)與技術(shù)、軟件工程、電子信息、系統(tǒng)科學(xué)、管理科學(xué)等學(xué)科進行交叉和滲透，追溯教學(xué)內(nèi)容的根源，然后反哺不同學(xué)科的專業(yè)知識，提高學(xué)生積極性，力爭打通圖論知識與學(xué)生后繼專業(yè)知識的通道，縮短基礎(chǔ)知識與專業(yè)知識的距離。因此，需要從教學(xué)內(nèi)容、教學(xué)方法、教學(xué)手段、考核方式等方面開展教學(xué)研究，加快教學(xué)改革步伐，探索適合信息類工科研究生的圖論教學(xué)新模式。

3《圖論及其應(yīng)用》課程建設(shè)探索與實踐

針對目前《圖論及其應(yīng)用》課程建設(shè)存在的一些典型問題，我們從教學(xué)目標(biāo)、教學(xué)內(nèi)容、教學(xué)方式和考試改革等方面進行探索和改革。

3.1重新擬定教學(xué)目標(biāo)

通過本課程學(xué)習(xí)，要求學(xué)生掌握圖論的基本理論及推理方法，為通信網(wǎng)絡(luò)、電路設(shè)計、邏輯設(shè)計、人工智能、形式語言、計算機制圖、程序涉及、信息安全以及信息檢索等知識的學(xué)習(xí)打下堅實的理論基礎(chǔ)。課程要求研究生掌握圖論的基本理論和基本方法，工科研究生需要掌握：圖的相關(guān)概念、歐拉圖、漢密爾頓圖、最短路徑、樹及其最優(yōu)二叉樹、平面圖與著色、二部圖與匹配、網(wǎng)絡(luò)流與網(wǎng)絡(luò)優(yōu)化等基本內(nèi)容，并用這些理論與方法解決一些科學(xué)研究中的實際問題，理解如何用圖論知識解決現(xiàn)代信息科學(xué)和現(xiàn)代通信系統(tǒng)中實際問題的基本原理。學(xué)生通過本課程的學(xué)習(xí)，培養(yǎng)優(yōu)良的數(shù)學(xué)素養(yǎng)、提升科學(xué)研究能力，提高科學(xué)計算能力，并能運用學(xué)到的知識和方法解決一些科研實際問題，為電子信息類研究生在后續(xù)的專業(yè)課程學(xué)習(xí)和科研工作奠定扎實的理論基礎(chǔ)。

3.2優(yōu)化教學(xué)內(nèi)容體系與結(jié)構(gòu)

本課程根據(jù)學(xué)校工科類研究生各專業(yè)對圖論的要求，選擇了較為系統(tǒng)的教學(xué)內(nèi)容，突出圖論的基本理論與方法，培養(yǎng)學(xué)生對離散對象的抽象思維與解決實際問題的能力，并為學(xué)習(xí)后繼相關(guān)專業(yè)課程及從事科學(xué)研究和工程實踐奠定理論基礎(chǔ)。主要內(nèi)容包括：

圖論學(xué)習(xí)的預(yù)備知識：主要介紹圖論學(xué)習(xí)中需要用到的等價關(guān)系、偏序關(guān)系、算法與復(fù)雜度分析等。

圖的基本概念：主要介紹圖論涉及的基本概念和基本理論，如同構(gòu)、握手定理、簡單圖、圖的矩陣表示、圖的連通性等。

歐拉圖與和漢密爾頓圖：主要介紹歐拉圖的定義及其判定，漢密爾頓圖的定義及其判定，歐拉圖和漢密爾頓圖的應(yīng)用。

樹及其最短路徑問題：主要介紹樹的相關(guān)概念、二叉樹、最優(yōu)二叉樹、有向圖的最短路徑算法等。

網(wǎng)絡(luò)優(yōu)化與Petri網(wǎng)：主要介紹網(wǎng)絡(luò)流與截集，最大流及其算法，最小費用問題等。

獨立集和支配集：主要介紹獨立集與支配集的相關(guān)概念、相互關(guān)系，匹配、最大匹配、最優(yōu)匹配和匈牙利算法等。

平面圖與著色：主要介紹平面圖、極大平面圖和極小非平面圖、對偶圖及其著色等。

3.3教學(xué)方式和考核評價體系改革

《圖論及其應(yīng)用》作為工科研究生（不管學(xué)術(shù)型還是專業(yè)型）的公共基礎(chǔ)課，我們當(dāng)前主要采用教師為主導(dǎo)的教學(xué)模式，嘗試采用分類教學(xué)，即讓不同學(xué)科的學(xué)生組成不同的教學(xué)班（如分為電子信息類、計算機科學(xué)與軟件工程類等），對部分教學(xué)內(nèi)容適當(dāng)調(diào)整。教師主要用我們自己制作的多媒體課件與板書相結(jié)合的教學(xué)方式，既體現(xiàn)了現(xiàn)代教學(xué)手段，也保留傳統(tǒng)的板書效果。同時，采用啟發(fā)式教學(xué)方法，讓學(xué)生撰寫圖論相關(guān)的小論文，作為平時成績，占30%；并利用我們建立的圖論課程網(wǎng)站，公布相應(yīng)的課程信息、考試大綱等?？傮w而言，《圖論及其應(yīng)用》課程經(jīng)過十余年的建設(shè)，已形成了一套較為合理的教學(xué)方法和手段，主要有：

1）結(jié)合工科學(xué)生情況，編寫出版《圖論及其應(yīng)用》教材，制作了一套對應(yīng)的教學(xué)課件，將多媒體教學(xué)手段與傳統(tǒng)教學(xué)手段結(jié)合，提高教學(xué)效率，增強教學(xué)效果。

2）引入一些應(yīng)用實例，增強課程的實用性、趣味性，提高了學(xué)生的學(xué)習(xí)興趣。

3）強調(diào)數(shù)學(xué)建模思想、加強數(shù)學(xué)與圖論知識的融合，提高學(xué)生的問題分析能力。

4）分類教學(xué)，引導(dǎo)學(xué)生將理論知識與自己的專業(yè)研究相結(jié)合。

5）鼓勵學(xué)生從接受學(xué)習(xí)到探究學(xué)習(xí)的轉(zhuǎn)變。旨在培養(yǎng)研究生的創(chuàng)新意識、應(yīng)用知識的遷移能力、對待事實證據(jù)的科學(xué)態(tài)度、對科學(xué)探究的理解、探究所需要的多種知識。

6）采用堂上討論、寫小論文等多種形式對課程學(xué)習(xí)進行考，核考查學(xué)生對基本理論的掌握情況以及分析解決問題的實際應(yīng)用能力等。

本課程教師采用我們團隊根據(jù)多年教學(xué)經(jīng)驗并結(jié)合學(xué)校學(xué)生實際情況編寫出版的教材，駕馭課堂能力強，教學(xué)經(jīng)驗豐富，高質(zhì)量完成課程教學(xué)任務(wù)，受到師生好評。

4目前形成的優(yōu)勢和特色

通過5年左右校級研究生優(yōu)質(zhì)課程建設(shè)和市級研究生優(yōu)質(zhì)課程的建設(shè)，目前《圖論及其應(yīng)用》課程已初具特色。

1）本課程是全校電子信息類研究生公共基礎(chǔ)課（學(xué)位課），學(xué)生受益面廣。我校通信類、計算機科學(xué)類、軟件工程類、系統(tǒng)科學(xué)類等學(xué)科的研究生培養(yǎng)方案把《圖論及其應(yīng)用》作為公共基礎(chǔ)課（學(xué)位課）來開設(shè)。教學(xué)規(guī)模逐年擴大，每年有近500人學(xué)生選修這門課程，學(xué)生受益面非常廣泛。

2）學(xué)校高度重視本課程建設(shè)，教學(xué)資源相對完善。隨著學(xué)生選課人數(shù)增加，學(xué)校在201 1年將《圖論及其應(yīng)用》課程作為重郵究生教育創(chuàng)新計劃重點項目進行建設(shè)，成效顯著，擁有相對完善的教學(xué)資源：重新制定的教學(xué)大綱、考試大綱；在清華大學(xué)出版社出版的《圖論及其應(yīng)用》研究生教材（2013）；自編配套的PPT課件；開發(fā)的課程網(wǎng)站（網(wǎng)址http：//slxy.cqupt.edu.cn/tulurd）。當(dāng)前教學(xué)團隊在分類教學(xué)、創(chuàng)設(shè)情境式、探究式教學(xué)等方面進行了教學(xué)改革，獲得重慶市研究生教研項目支持（2012年、2015年各一項），具有一定的研究基礎(chǔ)。

3）本課程有高水平的師資隊伍和良好的教學(xué)條件。本課程教學(xué)團隊的8人中，任課教師6人，學(xué)校教學(xué)管理和網(wǎng)站建設(shè)與維護人員2人，職稱結(jié)構(gòu)和學(xué)歷結(jié)構(gòu)非常好，集中在35-45歲階段的教學(xué)和科研骨干，授課教師高級職稱所占比例是100%，具有海外訪學(xué)經(jīng)歷人員有3人。另外1名剛畢業(yè)的博士作為后備教師，1名中級職稱老師負責(zé)網(wǎng)站建設(shè)與維護；團隊教師具有豐富的教學(xué)經(jīng)驗和良好學(xué)科知識背景，教學(xué)團隊凝聚力強。

4）本課程成為實用性極強的重要的數(shù)學(xué)工具?！秷D論及其應(yīng)用》是通信網(wǎng)絡(luò)、電子技術(shù)、計算機科學(xué)、系統(tǒng)工程與控制、網(wǎng)絡(luò)理論、社會科學(xué)及經(jīng)濟管理等眾多學(xué)科中起著不可替代作用的數(shù)學(xué)工具。通過本門課程的學(xué)習(xí)，使學(xué)生不僅能夠掌握現(xiàn)代計算的一些基本理論知識，而且還能了解信息學(xué)科發(fā)展的前沿動態(tài)（如通信網(wǎng)絡(luò)路由選擇、網(wǎng)絡(luò)規(guī)劃和優(yōu)化資源方法及應(yīng)用等），提高學(xué)生的科研創(chuàng)新能力。

5結(jié)束語

《圖論及其應(yīng)用》作為工科類研究生后續(xù)課程如《算法分析與設(shè)計》、《運籌與控制》、《信號分析》、《人工智能》、《網(wǎng)絡(luò)優(yōu)化》等課程的先修公共基礎(chǔ)課程，其重要性也是不言而喻的，很多研究生導(dǎo)師要求學(xué)生必須選修這門課程。針對該課程中概念比較多、論證方法獨特而又千變?nèi)f化的特征，再加上課時較少（48學(xué)時），而且選修的學(xué)生遍及全校幾乎所有的工科專業(yè)，對這門公共基礎(chǔ)課加以教學(xué)改革是我校研究生教學(xué)改革的重要方向。論文以建設(shè)重慶市優(yōu)質(zhì)課程為主線，介紹了一些相關(guān)作法，期待和大家共勉。