計(jì)算機(jī)專業(yè)研究生圖論課程的探討

摘要：本文根據(jù)計(jì)算機(jī)專業(yè)碩士研究生的具體情況結(jié)合圖論課程自身的特點(diǎn)，以作者多年講授這門(mén)課程的經(jīng)驗(yàn)，立足于同學(xué)們以后的學(xué)習(xí)和工作，對(duì)圖論課程的教學(xué)提出了一些改革的建議。

關(guān)鍵詞：圖論；圖論及其應(yīng)用；計(jì)算機(jī)專業(yè)；研究生

中圖分類號(hào)：G643 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1674-9324（2013）18-0197-02

目前在絕大多數(shù)的高校，都對(duì)計(jì)算機(jī)專業(yè)的研究生開(kāi)設(shè)有《圖論》或《圖論及其應(yīng)用》的課程。由于是非數(shù)學(xué)專業(yè)的學(xué)生，課程的學(xué)時(shí)較少，根據(jù)我們的調(diào)查，學(xué)時(shí)多在32～48學(xué)時(shí)之間。本文根據(jù)作者多年給計(jì)算機(jī)專業(yè)的研究生講授圖論課的教學(xué)經(jīng)驗(yàn)，結(jié)合學(xué)生的具體情況以及圖論課程自身的特點(diǎn)，提出了在教學(xué)中的一些改革思路。

一、圖論中的定理及其證明的教學(xué)問(wèn)題[1]

由于圖論課程中的定理、結(jié)論特別多，證明方法千差萬(wàn)別，有些證明既難又長(zhǎng)。這給老師的教學(xué)帶來(lái)一定的困難，也使學(xué)生學(xué)習(xí)難度增大、變得枯燥乏味。以往我們?cè)谑谡n中沿用其它數(shù)學(xué)課程的教學(xué)方式，只要教學(xué)大綱里有的內(nèi)容，幾乎對(duì)所有的定理都給予證明。但通過(guò)多次的教學(xué)實(shí)踐，我們發(fā)現(xiàn)效果并不理想，主要表現(xiàn)在同學(xué)們學(xué)習(xí)圖論課時(shí)把絕大多數(shù)的精力花在定理的證明上，因而覺(jué)得這門(mén)課很枯燥，還有一部分同學(xué)為此產(chǎn)生了畏難情緒。通過(guò)與學(xué)生及其導(dǎo)師的交流，結(jié)合圖論課程的特點(diǎn)，我們認(rèn)識(shí)到所教學(xué)生是非數(shù)學(xué)專業(yè)的學(xué)生、加之學(xué)時(shí)又有限（成都信息工程學(xué)院為計(jì)算機(jī)專業(yè)研究生所開(kāi)設(shè)的圖論課程，為40個(gè)學(xué)時(shí)），對(duì)理論證明方面的要求不必太高，他們更感興趣的是圖論的基本概念、基本理論、重要的結(jié)論以及應(yīng)用。因此，在以后的教學(xué)中采取少講或不講一些不重要的定理及其結(jié)論，對(duì)不重要的定理均不予證明，而對(duì)一些雖然重要，但證明太難或太冗長(zhǎng)的定理證明也不講，只是把結(jié)論告訴大家。例如在平面圖的開(kāi)始部分，重點(diǎn)講解“Euler公式，K5與K3，3是不可平面的”這些定理的內(nèi)容及證明。之所以這樣是因?yàn)檫@些結(jié)論的內(nèi)容很重要，在證明“K5與K3，3是不可平面的”要用到Euler定理，而在介紹Kuratowski定理時(shí)又要用到“K5與K3，3是不可平面的”這些結(jié)論。這三個(gè)結(jié)論的證明有十分簡(jiǎn)潔的方法，如對(duì)Euler定理的證明我們選擇的是對(duì)面數(shù)用歸納法的證明方法，[2]這種方法在圖論的證明中很具有代表性，其證明方法也很容易理解。而對(duì)其它眾多的結(jié)論我們只是有選擇地說(shuō)明其意義，而不一一地加以證明。在講匹配理論時(shí)，我們只講Tutte定理，[3，4]而不講定理的證明，此定理雖然重要，但其證明過(guò)于繁復(fù)和冗長(zhǎng)。對(duì)Kuratowski定理，我們也只介紹定理，并通過(guò)例題幫助學(xué)生加深對(duì)此定理的理解，對(duì)定理不加以證明。這樣一來(lái)，學(xué)生的學(xué)習(xí)負(fù)擔(dān)減輕了，學(xué)起來(lái)也不會(huì)太抽象，老師也有更多的時(shí)間傳授學(xué)生們感興趣的問(wèn)題，如在平面圖中的平面性算法等。

二、關(guān)于概念名稱不統(tǒng)一的問(wèn)題

近幾年出版的圖論教材和圖書(shū)比較多，但有一個(gè)共同的問(wèn)題就是概念的名稱不統(tǒng)一，不同的書(shū)對(duì)同樣的概念使用不同的名稱。如：偶圖[2]、二部圖[3]、二分圖[4]說(shuō)的都是同一個(gè)概念，又如匹配[2]、對(duì)集[5]也是相同的概念，像這樣的例子可以舉很多。這給老師的教學(xué)和學(xué)生的學(xué)習(xí)帶來(lái)了一定的困難。因此，我們?cè)诮虒W(xué)中給出它的英文名稱，如偶圖、二部圖、二分圖的英文都是bipartite graph，而匹配和對(duì)集的英文名稱是matching。在講述這些概念時(shí)首先講清楚它的意思，并畫(huà)圖加以說(shuō)明，同時(shí)將它們的英文名稱告訴大家，最后給學(xué)生介紹用得比較多的中文名稱。在學(xué)生掌握了這些概念的意思后，對(duì)不同的中文翻譯就可以較容易理解了。這樣在以后的學(xué)習(xí)和工作中，若遇到這個(gè)概念，無(wú)論是中文的哪個(gè)名稱還是英文的理解起來(lái)都比較容易。特別是在閱讀參考書(shū)及參考文獻(xiàn)時(shí)，對(duì)學(xué)過(guò)的概念，若用不同的中文名稱，也能很快的理解。而在教學(xué)過(guò)程中，有些學(xué)生反映，一些概念的英文名稱更容易理解和記憶。

三、突出重點(diǎn)，避免重復(fù)

雖然計(jì)算機(jī)專業(yè)的研究生來(lái)自于不同的學(xué)校和專業(yè)，但是許多學(xué)生在讀本科時(shí)已經(jīng)學(xué)習(xí)過(guò)《離散數(shù)學(xué)》、《數(shù)據(jù)結(jié)構(gòu)》等課程，這些課程會(huì)講授一些圖論的知識(shí)，有的會(huì)涉及到圖論課程中的內(nèi)容。因此在第一次上課時(shí)，我們首先向?qū)W生了解以前學(xué)習(xí)圖論知識(shí)的情況，在教學(xué)中突出重點(diǎn)，避免重復(fù)。例如，最短道路問(wèn)題在《離散數(shù)學(xué)》、《數(shù)據(jù)結(jié)構(gòu)》、《運(yùn)籌學(xué)》等課程均做過(guò)介紹，大家都知道求解最短道路的Dijkstra算法，因此在講課時(shí)主要講解最短道路的意思，最短道路問(wèn)題在現(xiàn)實(shí)中的應(yīng)用，最后再多介紹幾種求最短道路的算法。在闡明最短道路的意思后，列舉一些例題，說(shuō)明最短道路的應(yīng)用，如Cisco路由器中的IOS軟件就要用到求最短道路的算法，這讓同學(xué)們覺(jué)得，他們現(xiàn)在學(xué)習(xí)的知識(shí)不僅僅是純理論的東西，而是與他們生活和工作是緊密聯(lián)系在一起的。在近幾年的教學(xué)中，我們發(fā)現(xiàn)雖然許多學(xué)生在以前的學(xué)習(xí)中接觸過(guò)求最短道路的Dijkstra算法，但他們對(duì)Dijkstra算法具體是怎樣實(shí)現(xiàn)的并不清楚，因此近幾年我們?cè)谥v授Dijkstra算法時(shí)的另一個(gè)工作是講解算法的思想及具體的實(shí)施過(guò)程。最后再簡(jiǎn)單介紹求最短道路的Warshall-Floyd算法、Dantzig算法、最優(yōu)化原則，說(shuō)明它們能解決的問(wèn)題，運(yùn)算復(fù)雜度。在最短道路這一部分，我們的重點(diǎn)是向?qū)W生闡明它的應(yīng)用。因?yàn)榇蠹叶紝W(xué)過(guò)最短道路的Dijkstra算法，而對(duì)算法的內(nèi)容我們不做詳細(xì)地講解。這樣既節(jié)約了時(shí)間，又可以介紹更多大家感興趣的知識(shí)。

四、理論與應(yīng)用相結(jié)合

對(duì)大多數(shù)人而言，純理論問(wèn)題總是比較抽象，在教學(xué)中，盡量做到理論與應(yīng)用相結(jié)合，而計(jì)算機(jī)專業(yè)的學(xué)生對(duì)應(yīng)用更感興趣。

在講完樹(shù)的相關(guān)理論后，我們立即講最小生成樹(shù)。首先說(shuō)明最小生成樹(shù)是有解的，在有解的情況下，如何求解——用Kruskal算法。再介紹最小生成樹(shù)的應(yīng)用，最后講一講求解最小生成樹(shù)的其它算法。

在講授完Euler圖的相關(guān)理論后，接著就介紹中國(guó)郵路問(wèn)題（Chinese Postman Problem），明確告訴學(xué)生中國(guó)郵路問(wèn)題是有解的。所有的教材對(duì)此問(wèn)題的具體求解方法沒(méi)有做詳細(xì)的介紹，加之學(xué)時(shí)有限，我們也不講其詳細(xì)的求解方法，只是介紹求解的大概思路。重點(diǎn)是介紹它的應(yīng)用。最后將相關(guān)文獻(xiàn)告訴學(xué)生，以便學(xué)生在以后的工作和學(xué)習(xí)中遇到此問(wèn)題便于查找和求解。最后再將中國(guó)郵路（Chinese Postman Problem）的最新研究情況——多郵遞員中國(guó)郵路問(wèn)題（k-Postman Chinese Postman Problem）給大家做個(gè)簡(jiǎn)介，同樣講清楚它的意思，將相關(guān)文獻(xiàn)告訴學(xué)生。

在講授完Hamilton圖的理論后，說(shuō)明旅行售貨員問(wèn)題——求最優(yōu)的Hamilton圈。告訴學(xué)生：目前還沒(méi)有求解旅行售貨員問(wèn)題的有效算法，但有方法獲得相當(dāng)好（不一定最優(yōu)）的解，最后再告訴學(xué)生相關(guān)參考文獻(xiàn)。

我們發(fā)現(xiàn)這樣的教學(xué)方式學(xué)生學(xué)習(xí)起來(lái)比較容易，同學(xué)們也比較感興趣，對(duì)他們進(jìn)一步的學(xué)習(xí)和工作幫助比較大。如在教學(xué)中我們就遇見(jiàn)這樣的情況，有個(gè)同學(xué)在學(xué)圖論課的同時(shí)，在課題中遇見(jiàn)了求解“旅行售貨員問(wèn)題”。在學(xué)習(xí)了圖論課程后，對(duì)此問(wèn)題有個(gè)清楚的認(rèn)識(shí)，而且很快可以提出解決方案。他明確告訴課題組的同事：目前還沒(méi)有求解旅行售貨員問(wèn)題的有效算法，但有算法獲得相當(dāng)好（不一定最優(yōu)）的解，當(dāng)節(jié)點(diǎn)數(shù)目很有限時(shí)，可以用窮舉的方法得到最優(yōu)解。

由于我們針對(duì)學(xué)生的特點(diǎn)，有選擇地傳授圖論的相關(guān)知識(shí)，加之與學(xué)生及其導(dǎo)師及時(shí)溝通，改進(jìn)我們的教學(xué)內(nèi)容，使得這門(mén)課受到較多學(xué)生的歡迎，選修這門(mén)課程的同學(xué)也逐年增多。看到這樣的結(jié)果，我們也很有成就感。

圖論是一門(mén)很有趣、內(nèi)容很多，又有很廣現(xiàn)實(shí)應(yīng)用的一門(mén)課程。對(duì)計(jì)算機(jī)專業(yè)的研究生來(lái)說(shuō)，如果這門(mén)課程講授得當(dāng)，不僅可以豐富同學(xué)們的數(shù)學(xué)知識(shí)，還可以對(duì)學(xué)生以后的學(xué)習(xí)和工作提供較大的幫助。因此在教學(xué)中不斷地改革和創(chuàng)新，是很有必要的。

參考文獻(xiàn)：

[1]王桂平，馮睿.計(jì)算機(jī)專業(yè)圖論課程教學(xué)改革探索[J].計(jì)算機(jī)教育，2009，（20）：71-72.

[2]張先迪，李正良.圖論及其應(yīng)用[M].北京：高等教育出版社，2005.

[3]王朝瑞.圖論（第3版）[M].北京：北京理工大學(xué)出版社，2004.

[4]王樹(shù)禾.圖論（第2版）[M].北京：科學(xué)出版社，2009.

[5]J.A.邦迪，U.S.R默蒂.圖論及其應(yīng)用[M].北京：科學(xué)出版社，1984.