淺談圖論教學

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

關鍵詞：圖論;組合數學;理論聯系實際

1 前言

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

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

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

圖是指有序的三元組G=（V，E，Ф），其中V稱為頂點集，E稱為邊集，而Ф是V到E中元素無序對簇V×V的函數，稱為關聯函數。

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

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

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

2 實例

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

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

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

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

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

下面再看一個與社交網絡緊密聯系的圖論問題。

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

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

3 結束語

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

參考文獻

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

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

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

作者簡介

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