圖論在數(shù)學(xué)競(jìng)賽中的應(yīng)用

喬友付

（河池學(xué)院數(shù)學(xué)系 廣西 宜州 546300）

圖論在數(shù)學(xué)競(jìng)賽中的應(yīng)用

喬友付

（河池學(xué)院數(shù)學(xué)系 廣西 宜州 546300）

本文利用圖論的思想和基本知識(shí)，有效的解決了數(shù)學(xué)競(jìng)賽中的有關(guān)某些對(duì)象以及這些對(duì)象之間的某幾種關(guān)系的問(wèn)題，從而讓學(xué)生了解應(yīng)用圖論解決數(shù)學(xué)競(jìng)賽問(wèn)題的思想方法和技巧。

圖論；數(shù)學(xué)競(jìng)賽；應(yīng)用

圖論起源于民間的“數(shù)學(xué)游戲”，其中最著名的是歐拉關(guān)于哥尼斯堡七橋問(wèn)題的論文，并由此確立了他在圖論領(lǐng)域的創(chuàng)始人的地位。圖論的產(chǎn)生解決了許多用傳統(tǒng)數(shù)學(xué)方法難以解決的問(wèn)題。經(jīng)過(guò)三百多年的發(fā)展，圖論已是當(dāng)代應(yīng)用數(shù)學(xué)領(lǐng)域最活躍的學(xué)科之一，圖論思想對(duì)于提高分析，解決問(wèn)題的能力是十分有益的，在中學(xué)數(shù)學(xué)競(jìng)賽中，經(jīng)常出現(xiàn)一些以圖論為背景的試題。這些問(wèn)題一般不需要高深的數(shù)學(xué)工具，往往需要深入的思考，和圖論的思想方法。如果研究的問(wèn)題是關(guān)于若干個(gè)對(duì)象以及這些對(duì)象之間的若干種關(guān)系，并且要證明它們具有某種性質(zhì)P，可把問(wèn)題轉(zhuǎn)化為有關(guān)圖論的問(wèn)題，為了證明原問(wèn)題具有性質(zhì)P，則歸結(jié)為證明該“圖”具有某種結(jié)構(gòu)Q即可。下面討論圖論中的一些簡(jiǎn)單概念和基本知識(shí)在數(shù)學(xué)競(jìng)賽題中的應(yīng)用。

1 度在某些問(wèn)題的應(yīng)用

在數(shù)學(xué)競(jìng)賽遇到的問(wèn)題涉及到多個(gè)對(duì)象（人或事物等），而對(duì)象之間又恰好有且僅有兩種不同的關(guān)系。運(yùn)用其他方法難以解決或不能解決，這時(shí)就可以嘗試用圖論中度數(shù)的有關(guān)知識(shí)去著手思考和幫助解決這些問(wèn)題。

定理1 設(shè)G是n階圖，則G中n個(gè)頂點(diǎn)的度之和等于邊數(shù)e的兩倍，即

例1 某地區(qū)網(wǎng)球俱樂(lè)部的20名成員舉行14場(chǎng)單場(chǎng)，每人至少上場(chǎng)一次。證明：必有六場(chǎng)比賽，其中12個(gè)參賽者各不相同。

證明：用20個(gè)點(diǎn)ν1,ν2,…,ν20代表20名成員，兩名選手比賽過(guò)，則在相應(yīng)的頂點(diǎn)間連一條邊，得圖G。由題意，圖G中有14條邊，且d(νi)≥1,i=1,2,…,20.

由定理1可得d(ν1)+d(ν2)+…+d(ν20)=2×14＝28.

在每個(gè)頂點(diǎn)νi處抹去d(νi)-1條邊，由于一條邊可能同時(shí)被兩個(gè)端點(diǎn)抹去，所以抹去的邊數(shù)最多為(d(ν1)-1)+…+(d(ν20)-1)=28-20=8.

故抹去這些邊后所得的圖G′至少還有14-8=6條邊，且圖G′中每個(gè)頂點(diǎn)的度至多是1，從而這6條邊所相鄰的12個(gè)頂點(diǎn)是各不相同的。即，這6條邊所對(duì)應(yīng)的6場(chǎng)比賽的參賽者各不相同。

2 平面圖中歐拉公式的巧用

圖論中的歐拉公式的應(yīng)用在數(shù)學(xué)競(jìng)賽中卻經(jīng)常出現(xiàn)，對(duì)歐拉公式的靈活應(yīng)用有利于解決解決圖論平面圖的數(shù)學(xué)競(jìng)賽問(wèn)題。

定理2 （歐拉公式）設(shè)圖G是有ν個(gè)頂點(diǎn)，e條邊和f個(gè)面的連通平面，則

歐拉公式的一個(gè)重要應(yīng)用就是可以決定一個(gè)平面簡(jiǎn)單圖中最多的邊數(shù)。因?yàn)橐粋€(gè)面上至少有3條邊，f個(gè)面的邊界至少有3f條邊。另外，一條邊最多是2個(gè)面的邊界，所以2e≥3f，即。代入歐拉公式，有,從而可得e≤3ν-6。

例2 有n個(gè)車(chē)站組成的公路網(wǎng)，每個(gè)車(chē)站至少有6條公路引出，求證：必有兩條公路在平面上相交。

分析：“車(chē)站”和兩站連接的“公路”可以看做圖論中的二元關(guān)系，要證明兩條公路在平面上相交，可轉(zhuǎn)化為證圖 具有某些性質(zhì)。

證明：n個(gè)車(chē)站用n個(gè)頂點(diǎn)表示，每?jī)蓚€(gè)車(chē)站有公路相同，則相應(yīng)兩頂點(diǎn)間連一邊，得圖G，由題意知，G中每一點(diǎn)度≥6。若G是平面圖，則由于6n≤2e,即，所以有

這個(gè)矛盾表明G不是平面圖。所以，至少有兩條公路在平面上相交。

3 拉姆賽定理

對(duì)于一些二元關(guān)系的問(wèn)題可以用度數(shù)的有關(guān)知識(shí)加以解決，但是在一些問(wèn)題中我們作圖G時(shí)只考慮兩元素之間連線(xiàn)或不連線(xiàn)，可能不方便問(wèn)題的思考，我們可以用另外的刻畫(huà)方式進(jìn)行處理，對(duì)邊染紅、藍(lán)兩色，這樣就得到了n階完全圖Kn，再根據(jù)n階完全圖Kn的性質(zhì)就可以用來(lái)解決此類(lèi)型的數(shù)學(xué)競(jìng)賽問(wèn)題。

定理3 設(shè)n≥6，則任何一個(gè)兩色完全圖Kn一定含有一個(gè)單色三角形。

例3 證明在任何6個(gè)人中總有三個(gè)人相互認(rèn)識(shí)，或者互不認(rèn)識(shí)。

分析：該問(wèn)題反映出人與人之間或相互認(rèn)識(shí)或或相互不認(rèn)識(shí)這種二元關(guān)系，這正好符合用圖論方法研究問(wèn)題的特征。由于所證結(jié)果是存在三人相互認(rèn)識(shí)或相互不認(rèn)識(shí)，若兩人握手，就在相應(yīng)頂點(diǎn)之間連一條邊，否則，就不連邊，這樣在論述方面不是很方便。于是若兩人認(rèn)識(shí)，在相應(yīng)頂點(diǎn)之間連一條邊，并染成紅色（即連一條紅邊）；若兩人不認(rèn)識(shí)，也在相應(yīng)頂點(diǎn)之間連條邊，并染成藍(lán)色（即連一條藍(lán)邊），從而就形成了一個(gè)染有紅、藍(lán)兩色的K6。于是，可將待證問(wèn)題轉(zhuǎn)化為：在二色K6中一定存在同色三角形。

證明：6個(gè)頂點(diǎn)表示6個(gè)人，6個(gè)頂點(diǎn)間任意兩點(diǎn)之間連線(xiàn)，得到6階完全圖 。設(shè)x和y是6階完全圖K6的兩個(gè)頂點(diǎn)。如果x和y表示的兩個(gè)人認(rèn)識(shí)，則xy邊染成紅色，否則邊xy染成藍(lán)色，于是K6是—2色完全圖。根據(jù)定理3知K6含有單色三角形。設(shè)為Δuνw，如果Δuνw是紅色，則頂點(diǎn)u,ν,w所表示的三個(gè)人相互認(rèn)識(shí)；如果Δuνw是藍(lán)色，則頂點(diǎn)u,ν,w所表示的三個(gè)人相互不認(rèn)識(shí)；即表明在任何6個(gè)人中，總有三個(gè)人認(rèn)識(shí)，或者不認(rèn)識(shí)。

4 匹配的應(yīng)用

匹配理論中，主要關(guān)注二部圖，具體來(lái)說(shuō)，設(shè)圖G是二部圖，X和Y是圖G的頂點(diǎn)集合的一個(gè)分劃，其中X中頂點(diǎn)之間以及Y中頂點(diǎn)之間都不連邊。如果圖G具有匹配 ，使得X中每個(gè)頂點(diǎn)都是M飽和的。也就是說(shuō)，X中每個(gè)頂點(diǎn)在M下都和Y中頂點(diǎn)匹配，則說(shuō)X可以匹配到Y(jié)中。

定理4 二部圖G＝(X,Y)，則G中有飽和X中的所有頂點(diǎn)的匹配M的充分必要條件為對(duì)?S?X，有表示S中頂點(diǎn)的度的和)。

例4 有n位紳士與n位太太參加一次舞會(huì)，每一位紳士恰好認(rèn)識(shí)δ位太太，每位太太也恰好認(rèn)識(shí)δ位紳士。證明可以適當(dāng)安排，使得每位太太均與她所認(rèn)識(shí)的紳士跳舞。

證明：紳士和太太均用點(diǎn)表示，分別組成點(diǎn)集Y，X，在相認(rèn)識(shí)的人之間連線(xiàn)，得二部圖G=(X,Y)，圖中每個(gè)點(diǎn)的度數(shù)均為δ，要使每位太太均與她認(rèn)識(shí)的紳士跳舞，即轉(zhuǎn)化為證明G中存在一個(gè)匹配M，使M飽和X中的所有頂點(diǎn)。

我們只要驗(yàn)證圖G滿(mǎn)足定理4的條件即可。而事實(shí)上，對(duì)?S?X，每個(gè)頂點(diǎn)的度數(shù)均為δ，從而問(wèn)題得證。

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

從以上例證來(lái)看，在運(yùn)用圖論知識(shí)解決數(shù)學(xué)競(jìng)賽問(wèn)題，可基本分為三個(gè)步驟：首先，對(duì)競(jìng)賽問(wèn)題進(jìn)行數(shù)學(xué)抽象，做出相應(yīng)的圖G；其次，根據(jù)圖論的有關(guān)理論，把問(wèn)題轉(zhuǎn)化為有關(guān)的圖論問(wèn)題；最后，證明該圖 G具有某些特定的性質(zhì)，回到競(jìng)賽問(wèn)題本身，得出結(jié)論。

［1］陳傳理,張同君.競(jìng)賽數(shù)學(xué)教程[M].北京：高等教育出版社,2005.

［2］王朝瑞.圖論.[M].3版.北京：北京理工大學(xué)出版社,2001.

［3］黃國(guó)勛.奧林匹克數(shù)學(xué)方法選講[M].上海：上海教育出版社,2002.

［4］魏暹蓀.數(shù)學(xué)競(jìng)賽中的圖論問(wèn)題[J].陜西師范大學(xué)繼續(xù)教育學(xué)報(bào),2002,19(2)：100-102.

［5］降毅.用圖論的方法解兩道智力題[J].河套大學(xué)學(xué)報(bào),2004,1(1)：14-16.

［6］方倩珊.探究數(shù)學(xué)趣題滲透圖論思想[J].思茅師范高等專(zhuān)科學(xué)校學(xué)報(bào),2006,22 (6)：56-58.

［7］呂同富.拉姆賽型問(wèn)題的研究及應(yīng)用[J].佳木斯大學(xué)學(xué)報(bào),2004,22(2)：281-283.

喬友付（1978—），男，安徽霍邱人，碩士，講師，主要研究方向?yàn)閳D論及其應(yīng)用。

本文由廣西新世紀(jì)教改項(xiàng)目(2010JGB070; 2011JGB321)資助。

江廣霞］