圖論知識在數學競賽中的應用

云南省安寧市安寧中學 劉 勇

圖論知識在數學競賽中的應用

云南省安寧市安寧中學 劉 勇

本文中主要對數學競賽中經常出現的頂點的度和歐拉問題做了探究，在了解了相關知識之后，通過對例題的研究分析來發現這些知識在數學競賽中是如何運用的，增強學生在數學競賽中對此類問題的運用能力。

數學競賽；頂點的度；歐拉問題

一、圖論在數學競賽中的地位

數學競賽起源于匈牙利，我國自1956年舉辦數學競賽以來，一直致力于數學人才的發現與培養，數學競賽的舉辦提高了中學生學習數學的積極性，培養了學生熱愛數學的興趣。數學競賽所涉及的內容主要為四大方面：代數、平面幾何、初等數論、組合。組合在競賽中主要考查的內容為計數、組合最值、圖論、邏輯推理和組合結構，在組合計數和組合結構中，往往需要用到圖論的知識來解決問題，由此可見圖論在組合中的重要性。

圖論的起源和發展離不開趣味數學問題，被大眾所公認的圖論起源是一個有趣的數學問題——哥尼斯堡的七橋問題。數學競賽的舉辦是為了能夠對知識活學活用，解決現實中的實際問題，圖論問題正好具備了這樣的條件，因此出現在了數學競賽中。

近些年以來，圖論在數學競賽中多次出現，一方面是因為圖論自身的不斷發展，圖論的問題也越來越多：另一方面是因為圖論的問題不涉及太深的理論知識，只需要通俗易懂的方式就可以解決問題。圖論滿足了選拔優秀數學人才的宗旨，所以圖論在數學競賽中體現得越來越重要。

二、頂點的度在數學競賽中的應用

例1 某地區網球俱樂部的20名成員舉行了14場單打比賽，每人至少上一場。證明：必有六場比賽，其中12個參賽選手各不相同。

解 ：用20個頂點來表示20條邊，成員之間如果進行了單打比賽，就在對應的兩頂點之間連一條邊，從而得到圖。設各頂點的度為并且有di≥1。可得：

例2 國際乒乓球男女混合雙打大獎賽有24對選手參加，賽前一些選手握了手，但是同一對選手之間不握手。賽后某個男選手問每個選手的握手次數，每人的回答各不相同，問這名男選手的女搭檔和多少人握了手？

三、歐拉問題在數學競賽中的應用

例3 如圖1是一棟房子的平面圖，現在客人需要從A出發，走過所有的門和所有的房間，最后從B出來，請問是否存在這樣的走法？

圖1

圖2

解：不存在這樣的走法。

我們把A和B以及每間房都用一個點來表示，兩房間之間有門的地方用一條邊來連接，這樣就可以得到了圖G，如圖2所示。在圖中，奇頂點的個數為4，所以圖不存在一筆畫完，即客人不能夠從A通過所有的門走遍所有的房間。

例4 設n＞3，考慮在同一圓周上的（2n-1）個互不相同的點所成的集合E。將E中一部分點染成黑色，其余的點不染色。如果至少有一對黑點，以它們為端點的兩條弧中有一條的內部（不包含端點）恰含中個點，則稱這種染色方式為“好的”。如果將E中個點染黑的每一種染色方式都是好的，求的最小值。

（1）當2n-1能夠整除3時，圖G正好由3個圈組成，每個圈的頂點分別為：

[1]喬友付．圖論在數學競賽中的應用[J]．科技視界，2012（1）．

[2]熊斌，鄭仲義．數學奧林匹克小叢書高中卷．圖論[M]．上海：華東師范大學出版社，2011(12)．