淺談數學競賽中的圖論問題

錢培星

【摘要】 圖論作為一門數學分支歷史悠久，從哥尼斯堡城的七橋問題至今，發展迅速，也受到數學競賽的青睞。本文從2016年數學聯賽的第三題談起，介紹了圖論的相關概念及一般的解題方法，最后再給出該題的較為簡便的解法。

【關鍵詞】圖論問題 數學競賽 解題方法

【中圖分類號】G633.6 【文獻標識碼】A 【文章編號】2095-3089（2017）07-0123-02

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

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

在解決這道圖論問題前，我們先來介紹一下圖論的一些定義和概念：

一、圖論相關的基本定義和基本概念

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

為了研究圖的相關性質，我們還需要一些圖的相關概念：

度：一個頂點的度是指與該頂點相關聯的邊的條數，頂點v的度記作d（v）

平行邊：若有若干條邊連著相同的兩個頂點，則稱這些邊是平行邊

環：兩端連接著同一端點的邊稱為環

簡單圖：既不含平行邊也不含環的圖稱為簡單圖

完全圖：任意兩個頂點間都有邊相連的簡單圖稱為完全圖，n階完全圖記為Kn

在高中數學競賽中，常見的都是簡單圖。

二、解決圖論問題的基本方法

在常見的圖論問題中，我們主要研究一個圖的邊數，頂點數，這自然離不開計數方法的運用，使用最頻繁的當屬富比尼原理，這通常通過對頂點的度與圖的邊數的兩次計數來實現。而其他如反證法、數學歸納法、抽屜原理等方法在圖論中也有豐富的應用。

例題：

例1（1985年全國高中數學聯賽試題）某足球邀請賽有十六個城市參加，每市派出甲、乙兩個隊，根據比賽規則，比賽若干天后進行統計，發現除A市甲隊外，其它各隊已比賽過的場數各不相同.問A市乙隊已賽過多少場？請證明你的結論。

證明：用32個點表示這32個隊，如果某兩隊比賽了一場，則在表示這兩個隊的點間連一條線，否則就不連線。

由于，這些隊比賽場次最多30場，最少0場，共有31種情況，現除A市甲隊外還有31個隊，這31個隊的比賽場次互不相同，故這31個隊比賽的場次恰好為0到30場，就在表示每個隊的點旁注上這隊的比賽場次。

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

該題是一道典型的頂點的度的應用，轉化成圖論問題之后，使我們對條件的理解更加直觀，清晰了解題思路。

例2：證明任意六個人中，必有三個人相互認識或三個人相互不認識？

這道題將它用圖論的語言轉述即為：將一個6階的圖用兩種顏色把其中的點兩兩連線（認識和不認識分別代表兩種顏色），必有一個同色三角形。這就是著名的Ramsey定理。一種較為常見證明的過程是對由一個頂點出發對同色邊的條數運用抽屜原理進行討論，在此不再贅述。有趣的是，如果轉而對同色角的個數去討論，我們能得到一個更強的結論：

對K6完全圖二染色，一定存在兩個同色三角形

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

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

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

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

推論：任何圖中，奇度頂點的個數是偶數。

證：所有頂點的度數和（2m=偶數）=偶度頂點的度數之和（偶數）+奇度點的頂點度數之和，所以奇度點的頂點度數之和是一個偶數，而奇數個奇數為奇數，故奇數點的個數必為偶數。

這實際上是一個簡單的算兩次。

2.托蘭定理：對一個有n個頂點的圖，若其少有+1的點，則必構成一個三角形。

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

3.定理：任意的9個人中，必有3個人互相認識或4個人互相不認識。

一般的，在圖論中我們將這類問題稱之為拉姆塞問題。這個定理實際上說的是：在有n個頂點的圖G中，存在一個K3（即三角形），或在它的補圖中（在Kn中去掉G的所有邊后余下的圖稱為G的補圖）有一個K4，二者必有一成立，n=9是保證這一個結論成立的n的最小值。更一般的，要確保在一個有t個頂點的圖中存在Km，或在其補圖中存在Kn，t的最小值是多少？這就是拉姆賽問題。記滿足上述要求的t的最小值為r（m，n），稱為對應的拉姆塞數。拉姆塞數有許多有趣的性質，在此就不在展開了。

四、問題的解決

最后我們回到2016年的競賽題：

證明：以這10個點為頂點，所連的線段為邊，得到十階簡單圖G，下面我們證明G的邊數不超過15。

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

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

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

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

在Vn+2…V10這9—n個頂點之間無三角形，由托蘭定理，至多有條邊。

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

而對于15條邊的圖恰有一種構造方式，如下：

參考文獻：

[1]張垚著.數學競賽中的組合問題，華東師范大學出版社（ 第1版）

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

[3]單樽著.數學競賽研究教程.江蘇教育出版社，2009，2

[4]單樽著.從簡單入手.中等數學.2011，9