圖論在數(shù)學競賽中的應用

喬友付

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

圖論在數(shù)學競賽中的應用

喬友付

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

本文利用圖論的思想和基本知識，有效的解決了數(shù)學競賽中的有關某些對象以及這些對象之間的某幾種關系的問題，從而讓學生了解應用圖論解決數(shù)學競賽問題的思想方法和技巧。

圖論；數(shù)學競賽；應用

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

1 度在某些問題的應用

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

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

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

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

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

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

故抹去這些邊后所得的圖G′至少還有14-8=6條邊，且圖G′中每個頂點的度至多是1，從而這6條邊所相鄰的12個頂點是各不相同的。即，這6條邊所對應的6場比賽的參賽者各不相同。

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

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

定理2 （歐拉公式）設圖G是有ν個頂點，e條邊和f個面的連通平面，則

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

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

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

證明：n個車站用n個頂點表示，每兩個車站有公路相同，則相應兩頂點間連一邊，得圖G，由題意知，G中每一點度≥6。若G是平面圖，則由于6n≤2e,即，所以有

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

3 拉姆賽定理

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

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

例3 證明在任何6個人中總有三個人相互認識，或者互不認識。

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

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

4 匹配的應用

匹配理論中，主要關注二部圖，具體來說，設圖G是二部圖，X和Y是圖G的頂點集合的一個分劃，其中X中頂點之間以及Y中頂點之間都不連邊。如果圖G具有匹配 ，使得X中每個頂點都是M飽和的。也就是說，X中每個頂點在M下都和Y中頂點匹配，則說X可以匹配到Y中。

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

例4 有n位紳士與n位太太參加一次舞會，每一位紳士恰好認識δ位太太，每位太太也恰好認識δ位紳士。證明可以適當安排，使得每位太太均與她所認識的紳士跳舞。

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

我們只要驗證圖G滿足定理4的條件即可。而事實上，對?S?X，每個頂點的度數(shù)均為δ，從而問題得證。

5 結束語

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

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

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

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

［4］魏暹蓀.數(shù)學競賽中的圖論問題[J].陜西師范大學繼續(xù)教育學報,2002,19(2)：100-102.

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

［6］方倩珊.探究數(shù)學趣題滲透圖論思想[J].思茅師范高等?？茖W校學報,2006,22 (6)：56-58.

［7］呂同富.拉姆賽型問題的研究及應用[J].佳木斯大學學報,2004,22(2)：281-283.

喬友付（1978—），男，安徽霍邱人，碩士，講師，主要研究方向為圖論及其應用。

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

江廣霞］