淺析圖論教學

翟明清

(滁州學院數學系,安徽滁州 239000)

淺析圖論教學

翟明清

(滁州學院數學系,安徽滁州 239000)

圖論是《離散數學》課程的重要組成部分,也是數學專業高年級的選修課程.本文介紹了從事圖論教學和研究的一些心得,探討了如何在該課程的教學過程中激發學生的學習興趣和培養學生的發現問題及解決問題能力,從而為學生今后作畢業論文或者進一步從事科學研究打下基礎.

離散數學;圖論;教學

1 引 言

圖論是離散數學和組合數學的重要分支.它以圖為研究對象,這種圖由若干給定的點及連接兩點的邊所構成,通常用來描述某些事物之間的某種特定關系,以點代表事物,以連接兩點的邊表示兩個事物間具有這種關系.

圖論起源于著名的柯尼斯堡七橋問題.當時哥尼斯堡城的居民有郊游的習慣,在城郊的普雷格爾河中有兩個小島,有七座橋將兩個小島和兩邊河岸連接起來,問一個人能否從其中某一塊陸地出發不重復地走遍七座小橋,再回到起點?然而無數次的嘗試都沒有成功.瑞士數學家歐拉在1736年證明了這個問題沒有解,他用抽象分析法將這個問題轉化為一個圖論問題：即把每一塊陸地看成一點,每一座橋看成一條邊,從而得到一個圖.歐拉關于該問題的研究《依據幾何位置的解題方法》也被公認為圖論領域的第一篇論文.此后,一些著名的圖論問題,如四色猜想,哈密頓問題,Rem sey數問題,圖的重構問題等陸續被提出,它們推動了圖論理論研究的日益完善和深入.上世紀中期,隨著計算機科學的飛速發展,圖論成為數學中發展最快的分支之一.圖論從它誕生開始就顯示了它的應用價值.如今,圖論在計算機理論科學,運籌學,系統科學,化學,生物學等很多學科領域都有著重要的應用.

圖論有別于一些數學基礎課程,它與實際問題密切聯系,強調數學應用能力的培養,它解決問題的方法沒有連續性和固定套路,非常靈活,往往一個問題一種解法.這些特征促使教師在教學中要避免填鴨式的講授,而應在講解知識的過程中激發學生的學習興趣和創造性思維能力.那么如何在教學中達到這種理想的目的呢?我認為關鍵詞就是“興趣”和“問題”.因為最好的學習動機是興趣,最好的學習方式是帶著問題學習.下面將圍繞它們談一談圖論教學中的體會.文中涉及到的一些概念和術語如無詳細說明,可參見[1-3].

2 設計好第一次課

很多同學經過一、二年級的數學基礎課和專業課學習之后,很容易對數學產生這樣的印象：枯燥,難懂,脫離實際.甚至認為如果以后不當教師或從事科研,數學學得再好也沒什么用.這些想法容易傷害學習積極性,是非常要不得的,圖論課為我們改變學生的這些想法提供了一個契機.為此,第一次課要出奇制勝,要讓學生從第一次課開始就產生這樣的想法：原來數學課程也可以這么輕松有趣,這么貼近現實生活.為了達到此目的,我們不妨從一個童年時期的智力題或故事開始.

例1傳說楚漢時期的著名將領韓信不光是一個軍事家還是一個數學天才.一次行軍途中,他看到路邊兩位老農在爭吵,上前了解原因,原來是為了分油不均而相持不下.他們手中有一個裝滿了油(容量10斤)的油簍,以及一個容量7斤的空油罐和一個容量3斤的空油葫蘆,但是3個容器上都沒有刻度,也沒有測量工具.韓信略一思考,丟下一句話便匆匆上路,兩位老農稍稍一愣,方然領悟.原來韓信說的是“葫蘆歸罐罐歸簍”.“葫蘆歸罐罐歸簍”的意思是：一次次的將油從油簍中倒向油葫蘆,油葫蘆裝滿就向油罐里倒,油罐裝滿就向油簍里倒,如此反復,若干次后,就可以將油均分為兩份.韓信給出了該問題的一種可行解,那么還有沒有其他辦法呢?韓信的辦法是不是最優的呢?

例2獵人帶著一擔白菜,一只羊和一條狼要過河.但是只有一條小船,只有獵人會劃船并且他一次至多只能帶白菜,羊,狼三者之一過河.如果讓狼和羊在一起,而獵人不在旁邊的話,狼就會把羊吃掉.如果讓羊和白菜在一起,而獵人不在旁邊的話,羊就會把白菜吃掉.問如何讓他們都平安過河?

類似上述的問題有很多,方法往往也不止一種,摸索一下,我們也不難找到某種可行的辦法.但要找出所有的可行解以及最優解,就需要建立圖的模型.以例1為例,我們可以將油所在的狀態用一些有序3元組表示,其中第一、二、三個分量分別表示當前時刻簍、罐、葫蘆中油的儲量.如初始狀態為〈10,0,0〉,其他可能狀態為〈7,3,0〉,〈7,0,3〉,〈1,6,3〉,〈3,7,0〉,〈3,4,3〉,〈5,5,0〉,〈5,4,1〉,〈5,3,2〉,〈2,5,3〉等等.然后將這些有序3元組看成頂點,從一個頂點A到另一個頂點B連一條有向邊當且僅當A所代表的狀態可以一次到達B所代表的狀態,這樣得到一個有向圖.圖中從頂點〈10,0,0〉到頂點〈5,5,0〉的所有有向路構成了所有的可行解.而最短有向路則為最優解.

這樣的問題生動而有趣,同時能反映圖論的“神奇”——實際問題可以轉化為圖的模型求解.

3 激發學生的學習興趣

圖論的每一章節往往以某個概念為中心展開,介紹與之相關的其他概念,定理,公式或算法等等.這個概念就是這一章節的關鍵詞,要激發學生的學習興趣,就必須事先告訴大家這個概念的實際背景,研究它有什么用.為此,在給出這個概念之前,我們同樣可以從日常生活中的一個小問題入手.例如,在引入平面圖定義之前,可給出下述問題.

例3有3個野人住在一個原始森林里的3個不同地方,他們每天都要到另外3個不同的地方獲取果實,水和柴火.然而由于山路崎嶇狹窄,當他們在路上相遇時,經常發生爭吵甚至打架.為了他們能夠長期和諧相處,能否為他們設計路線,使得他們永遠也不在途中相遇?

這個問題抽象成圖模型就是完全二部圖K3,3是否存在一種平面畫法,使得任意兩條邊不交叉?這個問題是無解的.同學們自然要問為什么——找不到并不能說明沒有啊.接著告訴大家這個“為什么”的答案就在這一章節的內容中并隨即引入平面圖的概念：一個圖稱為平面圖,如果它可以畫在平面上使得任意兩條邊不交叉.

在引入色數,控制數,匹配數,哈密頓圖等中心概念之前,我們也不難找到一些實際問題與之對應.這些日常生活中的小問題,有時比高談闊論更有用,它能讓同學們立即產生興趣并對所要研究的概念印象深刻.

4 如何發現問題

前文已經強調了問題在學習中的重要性.然而,要提高學生對學習的主動積極性,就必須讓學生自己想出一些問題并試著解決它.授人以魚不如授人以漁.給學生一個好問題,不如教會學生如何發現問題.一位數學家也曾經說過,發現問題有時比解決問題更為重要.如何在圖論教學過程中培養學生的發現問題能力呢?在講解一個圖的概念,模型及其相關性質時,我們應該經常提醒學生發散自己的思維,去建立一個新的概念,模型并研究其性質.當然,這種發散不是漫無邊際的發散,通常是基于原有概念(模型)的推廣或者遷移.

以圖的著色概念為例,圖G的一個k-著色是指用{1,2,…,k}中的元素對圖G的所有頂點標號,使得任意兩個相鄰頂點標號不同.圖G的色數是指能使圖G存在一個k-著色的最小整數k.色數模型的實際應用有很多,比如,電臺的頻率分配問題.一些城市的廣播電臺需要分配頻率,為了盡可能避免相互干擾而又不占用過大的頻寬,可以讓鄰近的城市使用不同頻率,而相距甚遠的城市則不做要求.在學習了色數的概念和性質后,可以啟發同學們:頻率分配問題抽象成色數模型有些簡單化,很多情況下并不能滿足避免干擾的要求,為了更好的降低干擾,我們該怎么辦?

可將該問題留作課后作業,鼓勵大家提出改進模型的辦法.并提醒大家注意兩個原則:合理性和可行性.合理性就是建立的模型要盡可能好的達到我們的目的,可行性就是模型不能太復雜,要便于求解.二者很多情況下是矛盾的,需要在它們之間尋求平衡.事實上,上述問題就是一個典型的模型推廣問題.我們可以定義一種k-L(p,q)著色:用{1,2,…,k}中的元素對圖G的所有頂點標號,使得任意兩個相鄰頂點(距離為1的頂點)標號之差不小于p,任意兩個較為接近的頂點(如距離為2的頂點)標號之差不小于q,這里p≥q為非負整數.顯然,普通著色就是L(p,q)著色的一個特例,即L(1,0)著色.

又如,在平面圖內容中,歐拉公式,極大平面圖的性質等都是重要知識點.可以啟發同學們:既然完全圖K5和完全二部圖K3,3都不能嵌入平面,它們能否嵌入環面呢,如何嵌入呢?更一般地,環面圖的歐拉公式應該是什么樣的?極大環面圖又有那些性質以及如何證明呢?這些問題都是典型的模型遷移問題——從平面圖到環面圖.

5 如何解決問題

盡管如前文所說,圖論解題的具體方法是靈活的,離散的,我們還是可以在教學過程中有意識的訓練學生的宏觀證明思想.通常來說,證明圖論命題有以下五種基本思想:歸納法思想,反證(歸謬)法思想,極圖思想,圖變換思想,構造或算法思想.有時它們需要結合使用.

歸納法適用于以下情形:所研究的圖對某種性質具有遺傳性,即它可以退化為更小的圖而保持該性質.例如樹刪去一個懸掛點仍為樹;完全圖刪去任一個點仍為完全圖.反證法適用于:不符合命題結論的圖比符合命題條件的圖具有更為明確的結構特征或性質.此時考慮不符合命題結論的圖,則容易推出矛盾.極圖思想是指在圖中找一個具有某種特征的極大(小)子圖,利用其極大(小)性來證明結論或推出矛盾.

例4證明每顆非平凡有限樹至少兩個葉子.

證 這個命題可以對頂點數做歸納來證明.下面用更簡單的極圖思想證明.設P是樹中的一條最長路,u和v是其兩個端點.既然P是最長的,u和v均不能有P之外的鄰居.又因為樹中不能有圈,從而u,v均只有一個鄰居,即u,v為葉子.

圖變換思想是指將所面對的圖模型轉換為一個新的圖模型,利用新模型的特征或已有性質來證明結論.圖論中著名的最大流最小割定理就可以圖變換后利用Menger定理來證明.證明一些圖論問題是N P完全的,通常也是將一已知的N P完全問題在多項式時間內圖變換為該問題.

例5 設圖G中每個頂點均為奇度點,則經過G的每條邊的哈密頓圈(即經過所有頂點恰好一次的圈)均有偶數個.

證 先引入一定義:設P=u1u2…un為圖中的一條哈密頓路(即經過所有頂點恰好一次的路),ui (i≠n-1)為un的鄰居,則稱哈密頓路Q=u1u2…ui un un-1…ui+1為P誘導的哈密頓路.顯然,P誘導的哈密頓路的數目是un的鄰居數減去1,且Q也誘導P.

任取邊uv,若無哈密頓圈經過uv,命題成立.否則,設P1,P2,…,Pt為圖G-uv中從u出發的所有哈密頓路,其中P1,P2,…,Ps(s≤t)為從u到v的所有哈密頓路,只需證明s為偶數即可.為此,定義一個新的圖H:以P1,P2,…,Pt為頂點,Pi與Pj在H中鄰接當且僅當在G-uv中Pi誘導Pj.則每個點Pi(1≤i≤s)在H中有奇數個鄰居,每個點Pj(s+1≤j≤t)有偶數個鄰居.由握手定理,H中所有點的鄰居數之和為偶數,從而s為偶數.

構造或算法思想適用于證明某種結構或方案的存在性,尤其是確定圖的一些結構參數的值或界時經常使用.例如,考慮控制數,色數等問題時,直接構造或由算法產生一個我們需要的控制集,著色方案等等.

例6圖G的一個2-穩定集是指G的一個頂點子集使得其中任兩個點之間距離大于2.圖G的一個控制集是指G的一個頂點子集使得G的任何其他點都有鄰居在其中.G的2-穩定數α(G)是指G的最大2-穩定集的基數,G的控制數γ(G)是指G的最小控制集的基數.證明對任一顆樹T, α(T)=γ(T).

證首先證明對任何圖G,α(G)≤γ(G).設S是一最大2-穩定集,則S外每個點在S中至多一個鄰居,從而S就需要|S|個頂點才能控制,故γ(G)≥|S|.

下面證明對任一顆樹T,α(T)=γ(T).為此,設計一算法產生一個2-穩定集S和一個控制集D使得|S|≥|D|(對于樹這個算法是簡單的,這里略去了).于是

這意味著α(T)=γ(T).

[1] Bondy J A,Murty U SR.Graph theo ry w ith applications[M].No rth-Holland：Elsevier,1976.

[2] Chartrand G,Oellermann O R.App lied and algorithmic graph theory[M].New Yo rk：McGraw-Hill,1993.

[3] West D B.Introduction to graph theo ry[M].New Jersey：Prentice Hall,2001.

Brief Talk about Graph Theory Teaching

Zhai Ming-qing
(Department of Mathematics,Chuzhou University,Chuzhou 239000,China)

Graph theo ry is an important component of Discrete Mathematics and an op tional course for higher grade studentsmajo ring in Mathematics,too.Some experience in teaching and studying p ractice is introduced in this paper. And it is exp lo red that how to invite the students’interest in studying Mathematics and train the abilities finding p roblem and solving p roblem.Thus this can make a good base for the students doing paper,studing and researching fo r the further.

discretemathematics;graph theo ry;teaching

G642.1

C

1672-1454(2011)05-0203-04

2009-01-06