汪 毅

(安徽大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，合肥 230601)

?

論“圖論”教學(xué)中的創(chuàng)新性引導(dǎo)

汪 毅

(安徽大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，合肥 230601)

“圖論”是組合數(shù)學(xué)的一個(gè)重要分支，是數(shù)學(xué)專業(yè)本科高年級(jí)一門必修或選修課程。以一個(gè)實(shí)例為視角，介紹如何通過課堂教學(xué)中的創(chuàng)新性引導(dǎo)， 結(jié)合當(dāng)今科研前沿， 教會(huì)學(xué)生發(fā)現(xiàn)科學(xué)問題，激發(fā)學(xué)生的科研興趣，提高創(chuàng)新能力，為學(xué)生今后從事科研工作打下堅(jiān)實(shí)的基礎(chǔ)。

“圖論”；啟發(fā)式教學(xué)；創(chuàng)新性引導(dǎo)

1 研究現(xiàn)狀

“圖論”是組合數(shù)學(xué)的一個(gè)重要分支，是研究對(duì)象與對(duì)象之間二元關(guān)系的一門學(xué)科。18世紀(jì)初期，東普魯士的哥尼斯堡城(今立陶宛的加里林格勒)普雷格爾河中有兩個(gè)小島，有七座橋連接兩岸和小島。哥尼斯堡居民沿河散步，提出這樣一個(gè)問題：能否從一個(gè)地方出發(fā)，經(jīng)過每座橋一次而且僅一次最后回到出發(fā)地。這就是著名的哥尼斯堡七橋問題，這一問題吸引了著名數(shù)學(xué)家Euler的關(guān)注。Euler創(chuàng)造性地將兩岸和小島抽象成頂點(diǎn)，將七座橋抽象成連接頂點(diǎn)之間的邊，得到一個(gè)圖，將該問題轉(zhuǎn)化為“圖論”中的Euler回路問題，并證明不存在這樣的回路。由此誕生了一個(gè)全新的數(shù)學(xué)分支——“圖論”。此后“圖論”蓬勃發(fā)展，大量知名的“圖論”問題相繼被提出，如四色問題、Hamilton問題、最短路問題等。經(jīng)過200多年的發(fā)展，“圖論”已成為一個(gè)理論與應(yīng)用兼有的數(shù)學(xué)領(lǐng)域。除經(jīng)典的結(jié)構(gòu)“圖論”外，“圖論”與代數(shù)結(jié)合形成代數(shù)“圖論”，與拓?fù)浣Y(jié)合形成拓?fù)洹皥D論”，與概率論幾何形成隨機(jī)“圖論”，與譜幾何結(jié)合形成譜圖理論。20世紀(jì)50年代以來，“圖論”與其他新興學(xué)科相互交叉、相互促進(jìn)，如理論計(jì)算機(jī)科學(xué)、量子化學(xué)、生物信息學(xué)、網(wǎng)絡(luò)科學(xué)等。一方面，“圖論”方法是解決這些新興學(xué)科問題的基本研究方法；另一方面，這些學(xué)科發(fā)展過程中提出的新問題為現(xiàn)代“圖論”高速發(fā)展提供了充沛的源動(dòng)力。

當(dāng)前“圖論”已成為數(shù)學(xué)專業(yè)本科高年級(jí)的必修或選修課程?！皥D論”研究所需的前期知識(shí)儲(chǔ)備相對(duì)不多，而且問題大都源于實(shí)際，有較強(qiáng)的應(yīng)用背景，直觀易懂。鑒于這些特點(diǎn)，“圖論”課程應(yīng)當(dāng)成為培養(yǎng)學(xué)生的創(chuàng)新性、解決實(shí)際問題的能力和初步科研能力的一個(gè)平臺(tái)。然而，在實(shí)際教學(xué)中卻存在一定程度的偏差。例如：過于注重理論知識(shí)的傳授，缺乏解決實(shí)際問題的培養(yǎng)，缺乏對(duì)學(xué)生創(chuàng)新能力的培養(yǎng)等。作者認(rèn)為，在“圖論”教學(xué)中應(yīng)該采用基于創(chuàng)新性培養(yǎng)的引導(dǎo)式教學(xué)方法，在傳授基本知識(shí)的同時(shí)，通過課堂教學(xué)引導(dǎo)，結(jié)合當(dāng)今科研前沿，教會(huì)學(xué)生如何發(fā)現(xiàn)科學(xué)問題，激發(fā)學(xué)生的探究欲望和學(xué)習(xí)興趣，引導(dǎo)學(xué)生積極思考，讓學(xué)生體會(huì)到提出問題和解決問題的樂趣， 從而培養(yǎng)他們解決實(shí)際問題的能力和創(chuàng)新能力。下面將從一個(gè)實(shí)例出發(fā)，介紹作者在實(shí)際“圖論”教學(xué)中針對(duì)這些目標(biāo)所做的一些有益的嘗試與探索。

2 實(shí) 例

2.1 問題的引入

所有頂點(diǎn)的度均相同的圖稱為正則圖。眾所周知，正則圖是“圖論”中最為重要的圖類之一。 它定義簡(jiǎn)單，性質(zhì)優(yōu)美，是所有“圖論”教材的必修內(nèi)容。注意到正則圖中所有頂點(diǎn)具有相同的度，可以引導(dǎo)學(xué)生探究一個(gè)自然的問題：刻畫所有頂點(diǎn)的度互不相同的圖。

由此，引出下面定義。

定義1[1]非平凡圖G稱為是不規(guī)則圖，若G中任意兩點(diǎn)都具有不同的度。

為激發(fā)學(xué)生興趣，可以介紹不規(guī)則圖的起源與背景——宴會(huì)定理。宴會(huì)定理是英國(guó)數(shù)學(xué)教育家 David Wells[1]所列出最優(yōu)美的24個(gè)數(shù)學(xué)定理中排名第15位的定理，具體如下。

宴會(huì)定理[1]在任何宴會(huì)上，總有兩個(gè)人在該宴會(huì)上恰有相同的朋友數(shù)。

建立圖模型，設(shè)G為一個(gè)圖，頂點(diǎn)表示出席宴會(huì)的人。若兩個(gè)人是朋友關(guān)系，則在對(duì)應(yīng)的頂點(diǎn)之間連一條邊。宴會(huì)定理可以重新被描述為如下定理。

定理1[1]非平凡的不規(guī)則圖是不存在的。

2.2 啟發(fā)式延伸

至此，關(guān)于不規(guī)則圖的討論看似已經(jīng)結(jié)束，這是因?yàn)椴淮嬖诜瞧椒驳牟灰?guī)則圖。然而通過仔細(xì)分析不難發(fā)現(xiàn)，宴會(huì)定理中討論的圖均為簡(jiǎn)單圖，即不含重邊和自回路的圖。如果將問題的討論范圍推廣到多重圖(允許含有重邊的圖)上，情形又將如何？ 如圖1所示，不規(guī)則的多重圖是存在的。

圖1

既然存在不規(guī)則的多重圖，那么對(duì)于多重圖而言，什么問題才是一個(gè)值得研究的科學(xué)問題？ 如何發(fā)現(xiàn)科學(xué)問題對(duì)于培養(yǎng)學(xué)生的創(chuàng)新性和科研能力而言是至關(guān)重要的。

設(shè)M為一個(gè)多重圖, 若將M中的多重邊用一條邊代替，所得的圖稱為M的基礎(chǔ)圖，記為G，如圖2所示。將G中的每條邊分配一個(gè)正整數(shù)代表多重圖中連接對(duì)應(yīng)頂點(diǎn)之間多重邊的個(gè)數(shù)，所得的圖稱為M對(duì)應(yīng)的賦權(quán)圖，記為W，如圖2所示。因此，不規(guī)則的多重圖可認(rèn)為是不規(guī)則的賦權(quán)圖。

圖 2

在所有非平凡的連通圖中，顯然2階完全圖K2不能作為不規(guī)則賦權(quán)圖的基礎(chǔ)圖。一個(gè)自然的問題是：K2是否是僅有的不能作為不規(guī)則賦權(quán)圖基礎(chǔ)圖的圖？

由此，可以引出下面定理。

定理2[1]設(shè)G是階至少為2的連通圖，則G是一個(gè)不規(guī)則多重圖(賦權(quán)圖)的基礎(chǔ)圖當(dāng)且僅當(dāng)G不同構(gòu)于K2。

2.3 前沿問題導(dǎo)入

下面我們換個(gè)角度看賦權(quán)圖的不規(guī)則性。設(shè)G為簡(jiǎn)單圖，頂點(diǎn)集為V，邊集為E。設(shè)f:E(G)→R+為從邊集到正整數(shù)集的一個(gè)函數(shù)，定義函數(shù)

?f:V(G)→R+，

V→,

其中e～v表示邊e和頂點(diǎn)v關(guān)聯(lián)。用上述符號(hào)，定理2可被重新描述如下。

定理3 對(duì)任意不同構(gòu)于K2的簡(jiǎn)單連通圖G，存在函數(shù)f:E(G)→R+，使得對(duì)于任意兩個(gè)不同的頂點(diǎn)u,v，?f(u)≠?f(v)。

如果將定理3中的結(jié)論弱化為 “存在函數(shù)f:E(G)→R+，使得對(duì)于任意兩個(gè)不鄰接的頂點(diǎn)u,v，?f(u)≠?f(v)”， 可得下面的命題。顯然，命題是成立的。

命題 對(duì)任意不同構(gòu)于K2的簡(jiǎn)單連通圖G，存在函數(shù)f:E(G)→R+，使得對(duì)于任意兩個(gè)不鄰接的頂點(diǎn)u,v，?f(u)≠?f(v)。

因?yàn)橛懻摰膶?duì)象均為有限圖，所以函數(shù)f可看成從邊集E(G)到{1,2,…k}上的映射。 一個(gè)自然問題是使得命題成立的最小的k是多少？ 2002年，Karoński等人[3]猜想最小的k為3。這就是著名的1-2-3猜想，具體如下。

1-2-3猜想[3]對(duì)任意不同構(gòu)于K2的簡(jiǎn)單連通圖G，存在函數(shù)

f: E(G)→{1,2,3}，

使得對(duì)于任意兩個(gè)不鄰接的頂點(diǎn)u,v，?f(u)≠?f(v)。

這里可以向?qū)W生介紹關(guān)于1-2-3猜想的最新研究進(jìn)展，鼓勵(lì)學(xué)生在一些特殊圖類上驗(yàn)證1-2-3猜想，激發(fā)學(xué)生的科研興趣。最后，介紹1-2-3猜想的最新研究成果1-2-3-4-5定理。

定理4(1-2-3-4-5定理)[4]對(duì)任意不同構(gòu)于K2的簡(jiǎn)單連通圖G，存在函數(shù)

f: E(G)→{1,2,3,4,5}，

使得對(duì)于任意兩個(gè)不鄰接的頂點(diǎn)u,v，?f(u)≠?f(v)。

2.4 有益的科學(xué)探索

1-2-3猜想是圖的標(biāo)號(hào)與染色理論中一個(gè)重要的猜想，很多階段性成果都發(fā)表在“圖論”頂級(jí)期刊上。從圖的染色角度，1-2-3猜想可被理解為：對(duì)于對(duì)任意不同構(gòu)于K2的簡(jiǎn)單連通圖G，存在定義在正整數(shù)集上的邊權(quán)函數(shù)，使得該邊權(quán)函數(shù)誘導(dǎo)的點(diǎn)權(quán)函數(shù)是圖G上的正常點(diǎn)染色。這里可以鼓勵(lì)學(xué)生大膽地向未知領(lǐng)域探索，提出一些有趣的科學(xué)問題。 例如：是否可以將1-2-3猜想中 “存在的邊權(quán)函數(shù)” 換成 “存在點(diǎn)權(quán)函數(shù)”，提出類似的問題？ 設(shè)f:V(G)→{1,2,…,k}為從頂點(diǎn)集到正整數(shù)集的一個(gè)函數(shù)。 重新定義函數(shù)

?f:V(G)→R+，

v→,

其中u～v表示頂點(diǎn)u,v是鄰接的。按照此定義，是否可以找到一個(gè)最小的k，使得對(duì)于所有的連通圖G， 由點(diǎn)權(quán)函數(shù)f誘導(dǎo)的點(diǎn)權(quán)函數(shù)?f是G的一個(gè)正常點(diǎn)染色？顯然不行，這是因?yàn)閷?duì)于完全圖Kn而言，所需的最小k等于n，當(dāng)n→+∞，k→+∞。 自然地，我們只能對(duì)于確定圖G，找對(duì)應(yīng)k的上界。這里的上界應(yīng)該和圖G的某個(gè)或某些結(jié)構(gòu)參數(shù)相關(guān)的。 具體是什么樣的上界才是合適的，可以留給學(xué)生探索。這一推廣想法，在國(guó)內(nèi)外文獻(xiàn)上尚未見報(bào)道。

當(dāng)然，還可以鼓勵(lì)學(xué)生查閱相關(guān)文獻(xiàn)，了解1-2-3猜想的若干變形形式，了解標(biāo)號(hào)理論的核心研究問題。 這些對(duì)于培養(yǎng)學(xué)生的創(chuàng)新能力和科研能力都是相當(dāng)有益的。

3 結(jié)束語(yǔ)

本文的實(shí)例是作者近年來在一線教學(xué)工作中發(fā)現(xiàn)的典型實(shí)例。 在“圖論”教學(xué)過程中， 像這樣的實(shí)例還有很多。 如何利用好這樣的實(shí)例，在有限的教學(xué)時(shí)間內(nèi)，激發(fā)學(xué)生的科研興趣，提高創(chuàng)新能力成立，仍然值得進(jìn)一步探討。

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

[2] Wells D.Are These the Most Beautiful[J].Math Intelligencer, 1990,12(3):37-41.

[3] Karoński M, Luczak T, Thomason A.Edge Weights and Vertex Colours[J].Combin Theory Ser:B, 2004,91:151-157.

[4] Kalkowski M, Karoński M, Pfender F.Vertex-coloring Edge-weightings: Towards the 1-2-3-conjecture[J]. J Combin Theory Ser:B, 2010, 100:347-349.

[責(zé)任編輯：張永軍]

On Innovative Guiding Methods inGraphTheoryTeaching

WANG Yi

(School of Mathematical Sciences,Anhui University, Hefei 230601,China)

GraphTheoryis an important branch in combinatorics, is also a compulsory course or elective course for senior students in school of mathematical science. In this paper, using an example, author introduces that how to teach students to find scientific problems, stimulate students’ interest in scientific research, and improve the ability of innovation by teaching guidance in classroom, combining scientific research. It is good for students in future research work.

GraphTheory；heuristic teaching；innovative guiding

2016-04-24

2016-07-20

2014年度國(guó)家社會(huì)科學(xué)基金項(xiàng)目“佛教對(duì)理學(xué)批判的回應(yīng)與調(diào)適研究”(14XZJ016)階段性成果之一。

汪 毅(1982— )，男,安徽壽縣人，安徽大學(xué)數(shù)學(xué)科學(xué)學(xué)院副教授、博士。

G642.1

A

2096-2371(2016)04-0127-04