淺談圖論教學(xué)

摘 要：隨著網(wǎng)絡(luò)的發(fā)展，圖論的作用越來越重要?，F(xiàn)如今，國內(nèi)許多高校都將圖論作為一門重要課程開設(shè)。本文以具體實例為視角談?wù)剤D論教學(xué)中的理論聯(lián)系實際，讓學(xué)生真正感受到圖論的實用價值，激發(fā)學(xué)生的學(xué)習(xí)興趣。

關(guān)鍵詞：圖論;組合數(shù)學(xué);理論聯(lián)系實際

1 前言

離散數(shù)學(xué)是應(yīng)用數(shù)學(xué)的一個重要組成部分，圖論是離散數(shù)學(xué)的重要分支。圖論在各方面有很重要的應(yīng)用，尤其是數(shù)學(xué)建模方面，大部分社會實際問題都是離散問題。圖論教學(xué)也越來越受到大家的重視。 如何教好圖論課程是一個值得思考的問題。

圖論既然作為數(shù)學(xué)分支，理應(yīng)用數(shù)學(xué)嚴(yán)格的表達(dá)式給一個明確定義，而不是用文字描述或者畫個實際圖舉例說明。因此針對數(shù)學(xué)專業(yè)的學(xué)生，教師來教授圖論這門課時用數(shù)學(xué)化的嚴(yán)格定義。培養(yǎng)學(xué)生用數(shù)學(xué)的語言來描述問題，而數(shù)學(xué)也能加深對圖的定義的理解，對將來做圖論相關(guān)方面的研究打下良好的基礎(chǔ)。

圖論是以圖為研究對象，圖論中的圖是由若干給定的頂點及連接兩頂點的邊所構(gòu)成的圖形，這種圖形通常用來描述某些事物之間的某種特定關(guān)系，用頂點代表事物，用連接兩頂點的邊表示相應(yīng)兩個事物間具有這種關(guān)系。國內(nèi)外大部分圖論教材都是如下定義的：

圖是指有序的三元組G=（V，E，Ф），其中V稱為頂點集，E稱為邊集，而Ф是V到E中元素?zé)o序?qū)Υ豓×V的函數(shù)，稱為關(guān)聯(lián)函數(shù)。

在計算機科學(xué)和互聯(lián)網(wǎng)技術(shù)的推動下，近幾十年里圖論取得了一系列發(fā)展成果。許多大師級數(shù)學(xué)家都因為在圖論領(lǐng)域的突出貢獻(xiàn)而斬獲國際大獎，比如1984年Wolf獎得主Erd?s，1998年Fields獎得主Gowers，2006年Fields獎得主Tao，2012年Abel獎得主Szemerédi。圖論尤其是極值圖論方面的研究產(chǎn)生了一些革命性的方法，比如概率方法，正則引理，離散傅里葉分析等?，F(xiàn)如今，圖論的理論和方法越來越受到各行各業(yè)的關(guān)注，它已逐漸成為解決工程、信息、交通、經(jīng)濟等領(lǐng)域?qū)嶋H問題的重要工具[1，3]。因此國內(nèi)許多高等院校都將圖論作為一門重要課程開設(shè)，面向高年級本科生以及研究生。

圖論的問題往往聽上去很容易，但是要解決卻是非常棘手。一段時間下來，很多學(xué)生就會產(chǎn)生厭學(xué)心理。如果能在圖論教學(xué)中做到理論聯(lián)系實際（事實上，圖論中的很多問題都來源于現(xiàn)實生活），讓學(xué)生真正感受到圖論的實用價值，或許會好很多。伴隨著計算機的發(fā)展，圖論學(xué)科也有了長足的進(jìn)步。圖論最重要的就是應(yīng)用，圖論中很重要的一部分內(nèi)容，就是其中的經(jīng)典問題及其有效算法，例如最短路問題的 Dijsktra 算法，最小生成樹的 Kruskal 算法和 Prim 算法，二部圖最大匹配的匈牙利算法，最大流的標(biāo)號算法等等。在教學(xué)過程中，要求學(xué)生深刻理解這些基本算法，并嘗試去編寫算法的程序代碼。同時，在此基礎(chǔ)上，也可以適當(dāng)?shù)靥岢鲆恍┡缮鷨栴}，啟發(fā)學(xué)生學(xué)習(xí)如何設(shè)計算法，比如在學(xué)習(xí)最小生成樹的算法時，可以要求學(xué)生設(shè)計求最小森林的算法。在現(xiàn)實生活中，解決其它實際問題的算法往往是以這些基本算法作為子算法，或在此基礎(chǔ)上進(jìn)行適當(dāng)修改而成的。因此，通過圖論的學(xué)習(xí)，可以提高學(xué)生對算法的理解和設(shè)計能力，強化程序代碼的編寫能力。

本文以具體實例為視角談?wù)勅绾卧趫D論教學(xué)中做到理論聯(lián)系實際，引導(dǎo)學(xué)生積極思考，讓學(xué)生體會到發(fā)現(xiàn)問題和解決問題的樂趣，從而激發(fā)學(xué)生的學(xué)習(xí)興趣。

2 實例

下面這個例子來自[2]，一般稱為宴會定理。

問題[1]在任何宴會上，總有兩個人在該宴會上恰有相同的朋友數(shù)。

學(xué)生看到這個定理的時候，或多或少會有些驚訝。這個定理與當(dāng)下很時髦的社交網(wǎng)絡(luò)（比如微信朋友圈）聯(lián)系很緊密。下面給出簡潔證明。

證明：不妨記參加宴會的人分別為。每個認(rèn)識的人數(shù)只能是，由于和不能同時出現(xiàn)。這樣每個人認(rèn)識的人數(shù)只有種可能。把這種可能性作為籠子，個人作為鴿子運用鴿籠原理可知必然存在兩個人認(rèn)識的人數(shù)一樣多。

上述證明用到組合數(shù)學(xué)中一個重要原理—鴿籠原理，也稱抽屜原理，最早是由德國數(shù)學(xué)家狄利克雷發(fā)現(xiàn)的。其本質(zhì)是在用平均值思想，比如班上這次數(shù)學(xué)考試平均分為80分，那么一定有人成績大于等于80分，也一定有人成績小于等于80分。但是究竟誰的成績大于等于80分，誰的成績小于等于80分并不清楚。

下面再看一個與社交網(wǎng)絡(luò)緊密聯(lián)系的圖論問題。

問題[2]假設(shè)認(rèn)識是相互的，任意6人集會一定有3人互相認(rèn)識或者有3人互相不認(rèn)識。

證明：不妨記這6個人為，下面考慮與認(rèn)識的人構(gòu)成的集合以及與不認(rèn)識的人構(gòu)成的集合。由鴿籠原理可知或者或者。若，若S中有兩人認(rèn)識，則他們與一起構(gòu)成三人互相認(rèn)識，否則S中任意兩人都不認(rèn)識，這樣會產(chǎn)生三人互相不認(rèn)識。若，若T中有兩人不認(rèn)識，則他們與一起構(gòu)成三人互相不認(rèn)識，否則T中任意兩人都認(rèn)識，這樣會產(chǎn)生三人互相認(rèn)識。

3 結(jié)束語

圖論是一門很重要的學(xué)科，有很重要的應(yīng)用。目前，國內(nèi)很多高校都有圖論的教學(xué)課程和從事圖論研究的科研工作者。學(xué)好了圖論課程，學(xué)生在以后的工作中，會增加一門很重要的技能，在利用數(shù)學(xué)模型解決實際問題的時候，能夠開拓思路，建立比較好的數(shù)學(xué)模型。以上兩個例子只是圖論與現(xiàn)實世界緊密聯(lián)系的一些例子的代表。如果我們能在圖論教學(xué)中多舉這樣的例子，相信會逐步消除學(xué)生的厭學(xué)心理，讓學(xué)生真正感受到圖論的作用，真正體會到學(xué)習(xí)圖論的樂趣。

參考文獻(xiàn)

[1]范益政，汪毅，龔世才，等.圖論導(dǎo)引[M].北京：人民郵電出版社，2007：35.

[2]Wells D.Are These the Most Beautiful[J].Math Intelligencer，1990，12（3）：37-41.

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

作者簡介

劉猛（1990-），男，漢族，河南信陽人，博士，安徽大學(xué)數(shù)學(xué)科學(xué)學(xué)院，講師，主要從事組合數(shù)學(xué)與圖論方向研究。