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

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

1 前言

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

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

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

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

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

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

本文以具體實例為視角談談如何在圖論教學中做到理論聯(lián)系實際，引導學生積極思考，讓學生體會到發(fā)現(xiàn)問題和解決問題的樂趣，從而激發(fā)學生的學習興趣。

2 實例

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

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

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

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

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

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

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

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

3 結(jié)束語

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

參考文獻

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

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

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

作者簡介

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