淺析圖論教學(xué)

翟明清

(滁州學(xué)院數(shù)學(xué)系,安徽滁州 239000)

淺析圖論教學(xué)

翟明清

(滁州學(xué)院數(shù)學(xué)系,安徽滁州 239000)

圖論是《離散數(shù)學(xué)》課程的重要組成部分,也是數(shù)學(xué)專業(yè)高年級的選修課程.本文介紹了從事圖論教學(xué)和研究的一些心得,探討了如何在該課程的教學(xué)過程中激發(fā)學(xué)生的學(xué)習(xí)興趣和培養(yǎng)學(xué)生的發(fā)現(xiàn)問題及解決問題能力,從而為學(xué)生今后作畢業(yè)論文或者進(jìn)一步從事科學(xué)研究打下基礎(chǔ).

離散數(shù)學(xué);圖論;教學(xué)

1 引 言

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

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

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

2 設(shè)計好第一次課

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

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

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

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

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

3 激發(fā)學(xué)生的學(xué)習(xí)興趣

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

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

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

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

4 如何發(fā)現(xiàn)問題

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

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

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

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

5 如何解決問題

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

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

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

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

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

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

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

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

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

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

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

下面證明對任一顆樹T,α(T)=γ(T).為此,設(shè)計一算法產(chǎn)生一個2-穩(wěn)定集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