錢培星

【摘要】 圖論作為一門數(shù)學(xué)分支歷史悠久，從哥尼斯堡城的七橋問(wèn)題至今，發(fā)展迅速，也受到數(shù)學(xué)競(jìng)賽的青睞。本文從2016年數(shù)學(xué)聯(lián)賽的第三題談起，介紹了圖論的相關(guān)概念及一般的解題方法，最后再給出該題的較為簡(jiǎn)便的解法。

【關(guān)鍵詞】圖論問(wèn)題 數(shù)學(xué)競(jìng)賽 解題方法

【中圖分類號(hào)】G633.6 【文獻(xiàn)標(biāo)識(shí)碼】A 【文章編號(hào)】2095-3089（2017）07-0123-02

圖論作為一個(gè)重要的數(shù)學(xué)分支，幾千年前，我國(guó)的河圖、洛書(shū)就已經(jīng)涉及到一些簡(jiǎn)單有趣的圖論問(wèn)題。18世紀(jì)，哥尼斯堡七橋問(wèn)題使得圖論作為一門真正的學(xué)科進(jìn)入學(xué)者們的視野。而近二十年來(lái)，由于計(jì)算機(jī)科學(xué)、編碼理論、規(guī)劃論、數(shù)字通訊、實(shí)驗(yàn)設(shè)計(jì)等學(xué)科的迅猛發(fā)展，提出了一系列的需要離散數(shù)學(xué)解決的理論和實(shí)際問(wèn)題，使得圖論的研究更為活躍。由于圖論蘊(yùn)含的數(shù)學(xué)思想豐富，圖形簡(jiǎn)潔美觀，證明巧妙，方法千變?nèi)f化，非常靈活，因而備受數(shù)學(xué)競(jìng)賽的青睞。今年的高中數(shù)學(xué)聯(lián)賽加試第三道題就是一道以圖論為背景的題：

給定空間中10個(gè)點(diǎn)，其中任意四點(diǎn)不在一個(gè)平面上，將某些點(diǎn)之間用線段相連，若得到的圖形中沒(méi)有三角形也沒(méi)有空間四邊形，試確定所連線段數(shù)目的最大值。

在解決這道圖論問(wèn)題前，我們先來(lái)介紹一下圖論的一些定義和概念：

一、圖論相關(guān)的基本定義和基本概念

圖由一個(gè)點(diǎn)集合V和一個(gè)連接某些點(diǎn)對(duì)的線段的集合E構(gòu)成的圖形稱為圖。記作G（V，E）.其中，V中的點(diǎn)稱為頂點(diǎn)，E中的線段（不一定是直線段）稱為邊。通常|V|和|E|表示頂點(diǎn)個(gè)數(shù)和邊的數(shù)量。有n個(gè)頂點(diǎn)的圖稱為n階圖。值得注意的是圖中頂點(diǎn)一定不能為空，而邊可以為空。

為了研究圖的相關(guān)性質(zhì)，我們還需要一些圖的相關(guān)概念：

度：一個(gè)頂點(diǎn)的度是指與該頂點(diǎn)相關(guān)聯(lián)的邊的條數(shù)，頂點(diǎn)v的度記作d（v）

平行邊：若有若干條邊連著相同的兩個(gè)頂點(diǎn)，則稱這些邊是平行邊

環(huán)：兩端連接著同一端點(diǎn)的邊稱為環(huán)

簡(jiǎn)單圖：既不含平行邊也不含環(huán)的圖稱為簡(jiǎn)單圖

完全圖：任意兩個(gè)頂點(diǎn)間都有邊相連的簡(jiǎn)單圖稱為完全圖，n階完全圖記為Kn

在高中數(shù)學(xué)競(jìng)賽中，常見(jiàn)的都是簡(jiǎn)單圖。

二、解決圖論問(wèn)題的基本方法

在常見(jiàn)的圖論問(wèn)題中，我們主要研究一個(gè)圖的邊數(shù)，頂點(diǎn)數(shù)，這自然離不開(kāi)計(jì)數(shù)方法的運(yùn)用，使用最頻繁的當(dāng)屬富比尼原理，這通常通過(guò)對(duì)頂點(diǎn)的度與圖的邊數(shù)的兩次計(jì)數(shù)來(lái)實(shí)現(xiàn)。而其他如反證法、數(shù)學(xué)歸納法、抽屜原理等方法在圖論中也有豐富的應(yīng)用。

例題：

例1（1985年全國(guó)高中數(shù)學(xué)聯(lián)賽試題）某足球邀請(qǐng)賽有十六個(gè)城市參加，每市派出甲、乙兩個(gè)隊(duì)，根據(jù)比賽規(guī)則，比賽若干天后進(jìn)行統(tǒng)計(jì)，發(fā)現(xiàn)除A市甲隊(duì)外，其它各隊(duì)已比賽過(guò)的場(chǎng)數(shù)各不相同.問(wèn)A市乙隊(duì)已賽過(guò)多少場(chǎng)？請(qǐng)證明你的結(jié)論。

證明：用32個(gè)點(diǎn)表示這32個(gè)隊(duì)，如果某兩隊(duì)比賽了一場(chǎng)，則在表示這兩個(gè)隊(duì)的點(diǎn)間連一條線，否則就不連線。

由于，這些隊(duì)比賽場(chǎng)次最多30場(chǎng)，最少0場(chǎng)，共有31種情況，現(xiàn)除A市甲隊(duì)外還有31個(gè)隊(duì)，這31個(gè)隊(duì)的比賽場(chǎng)次互不相同，故這31個(gè)隊(duì)比賽的場(chǎng)次恰好為0到30場(chǎng)，就在表示每個(gè)隊(duì)的點(diǎn)旁注上這隊(duì)的比賽場(chǎng)次。

考慮比賽場(chǎng)次為30的隊(duì)，這個(gè)隊(duì)除自己與同城的隊(duì)外，與不同城有隊(duì)都進(jìn)行了比賽，于是，它只可能與比賽0場(chǎng)的隊(duì)同城；去掉這兩支隊(duì)伍以及這兩支隊(duì)伍的比賽場(chǎng)次（即這時(shí)候其他隊(duì)伍的比賽場(chǎng)次都減少1），在剩下的30支隊(duì)伍中，再考慮比賽28（29-1）場(chǎng)的隊(duì)伍，這個(gè)隊(duì)除與同城隊(duì)不比賽外，與其他隊(duì)伍都比賽過(guò)了，原先賽了1場(chǎng)的隊(duì)此時(shí)記為0場(chǎng)了，同理，它和賽了29場(chǎng)的是一個(gè)城市的；依次類推，知比賽k場(chǎng)的隊(duì)與比賽30-k場(chǎng)的隊(duì)同城，這樣，把各城都配對(duì)后，只有比賽15場(chǎng)的隊(duì)沒(méi)有與其余的隊(duì)同城，故比賽15場(chǎng)的隊(duì)就是A城乙隊(duì)。即A城乙隊(duì)比賽了15場(chǎng)。

該題是一道典型的頂點(diǎn)的度的應(yīng)用，轉(zhuǎn)化成圖論問(wèn)題之后，使我們對(duì)條件的理解更加直觀，清晰了解題思路。

例2：證明任意六個(gè)人中，必有三個(gè)人相互認(rèn)識(shí)或三個(gè)人相互不認(rèn)識(shí)？

這道題將它用圖論的語(yǔ)言轉(zhuǎn)述即為：將一個(gè)6階的圖用兩種顏色把其中的點(diǎn)兩兩連線（認(rèn)識(shí)和不認(rèn)識(shí)分別代表兩種顏色），必有一個(gè)同色三角形。這就是著名的Ramsey定理。一種較為常見(jiàn)證明的過(guò)程是對(duì)由一個(gè)頂點(diǎn)出發(fā)對(duì)同色邊的條數(shù)運(yùn)用抽屜原理進(jìn)行討論，在此不再贅述。有趣的是，如果轉(zhuǎn)而對(duì)同色角的個(gè)數(shù)去討論，我們能得到一個(gè)更強(qiáng)的結(jié)論：

對(duì)K6完全圖二染色，一定存在兩個(gè)同色三角形

證明：由一個(gè)頂點(diǎn)出發(fā)，引出5條邊，則以每個(gè)頂點(diǎn)可做出C個(gè)角，至少有4個(gè)兩邊同色的角，故圖.K6中至少有24個(gè)同色角。而每個(gè)同色三角形有3個(gè)同色角，不同色的三角形有1個(gè)同色角。K6中一共有20個(gè)三角形。因此，至少有兩個(gè)同色三角形。

在解決一些圖論問(wèn)題中，我們還需要用到一些圖論的定理。

三、一些圖論的基本（著名的）定理

1.握手定理：設(shè)G有n個(gè)頂點(diǎn)，則該圖中所有頂點(diǎn)的度之和為邊數(shù)的兩倍。即設(shè)G中的n個(gè)頂點(diǎn)為v1，v2…vn，總邊數(shù)為e，則d（v1）+d（v2）+…d（vn）=2e

推論：任何圖中，奇度頂點(diǎn)的個(gè)數(shù)是偶數(shù)。

證：所有頂點(diǎn)的度數(shù)和（2m=偶數(shù)）=偶度頂點(diǎn)的度數(shù)之和（偶數(shù)）+奇度點(diǎn)的頂點(diǎn)度數(shù)之和，所以奇度點(diǎn)的頂點(diǎn)度數(shù)之和是一個(gè)偶數(shù)，而奇數(shù)個(gè)奇數(shù)為奇數(shù)，故奇數(shù)點(diǎn)的個(gè)數(shù)必為偶數(shù)。

這實(shí)際上是一個(gè)簡(jiǎn)單的算兩次。

2.托蘭定理：對(duì)一個(gè)有n個(gè)頂點(diǎn)的圖，若其少有+1的點(diǎn)，則必構(gòu)成一個(gè)三角形。

證明：反證法，假設(shè)這個(gè)圖沒(méi)有三角形。記它的頂點(diǎn)為v1，v2…vn不妨設(shè)v1的度最大，為k，與它有邊相連的點(diǎn)為v2，v3…vk+1則這k個(gè)點(diǎn)互相不能有邊，否則有三角形。則它們每個(gè)點(diǎn)至多連（n-k）條邊，剩下的n-k-1的點(diǎn)中，每個(gè)點(diǎn)至多有k條邊，所以若這個(gè)n階圖沒(méi)有三角形，它的頂點(diǎn)的度之和不超過(guò)k+k×（n-k）+（n-k-1）k=2（n-k）k由握手定理，它至多有（n-k）k條邊。當(dāng)k=時(shí)，邊數(shù)最大，為。考慮它是個(gè)整數(shù)，所以至多條邊。矛盾，因而命題得證。

3.定理：任意的9個(gè)人中，必有3個(gè)人互相認(rèn)識(shí)或4個(gè)人互相不認(rèn)識(shí)。

一般的，在圖論中我們將這類問(wèn)題稱之為拉姆塞問(wèn)題。這個(gè)定理實(shí)際上說(shuō)的是：在有n個(gè)頂點(diǎn)的圖G中，存在一個(gè)K3（即三角形），或在它的補(bǔ)圖中（在Kn中去掉G的所有邊后余下的圖稱為G的補(bǔ)圖）有一個(gè)K4，二者必有一成立，n=9是保證這一個(gè)結(jié)論成立的n的最小值。更一般的，要確保在一個(gè)有t個(gè)頂點(diǎn)的圖中存在Km，或在其補(bǔ)圖中存在Kn，t的最小值是多少？這就是拉姆賽問(wèn)題。記滿足上述要求的t的最小值為r（m，n），稱為對(duì)應(yīng)的拉姆塞數(shù)。拉姆塞數(shù)有許多有趣的性質(zhì)，在此就不在展開(kāi)了。

四、問(wèn)題的解決

最后我們回到2016年的競(jìng)賽題：

證明：以這10個(gè)點(diǎn)為頂點(diǎn)，所連的線段為邊，得到十階簡(jiǎn)單圖G，下面我們證明G的邊數(shù)不超過(guò)15。

設(shè)G頂點(diǎn)為V1，…V10，他們之間共連了k條邊，用deg（Vi）表示Vi的度，

若deg（Vi）≤3恒成立，則k=deg（Vi）≤×10×3=15

若存在deg（Vi）≥4，不妨設(shè)deg（（V1）=n≥4，且V1與V2…Vn+1相鄰，于是V2…Vn+1之間不再有邊，否則構(gòu)成三角形，所以V1…Vn+1之間恰有n條邊。

對(duì)每個(gè)j（n+2≤j≤10），Vj與V2…Vn+1中的至多一個(gè)頂點(diǎn)相鄰，否則設(shè)Vj與Vs，Vt相鄰，則V1，Vj，Vs，Vt構(gòu)成空間四邊形，故V2…Vn+1與Vn+2…V10之間至多10-（n+1）=9-n條邊。

在Vn+2…V10這9—n個(gè)頂點(diǎn)之間無(wú)三角形，由托蘭定理，至多有條邊。

因此總邊數(shù)為k≤n+（9-n）+≤9+=15，綜上k不大于15。

而對(duì)于15條邊的圖恰有一種構(gòu)造方式，如下：

參考文獻(xiàn)：

[1]張垚著.數(shù)學(xué)競(jìng)賽中的組合問(wèn)題，華東師范大學(xué)出版社（ 第1版）

[2]熊斌，鄭仲義著.圖論.華東師范大學(xué)出版社，2005，4

[3]單樽著.數(shù)學(xué)競(jìng)賽研究教程.江蘇教育出版社，2009，2

[4]單樽著.從簡(jiǎn)單入手.中等數(shù)學(xué).2011，9