云南省安寧市安寧中學(xué) 劉 勇

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

云南省安寧市安寧中學(xué) 劉 勇

本文中主要對數(shù)學(xué)競賽中經(jīng)常出現(xiàn)的頂點的度和歐拉問題做了探究，在了解了相關(guān)知識之后，通過對例題的研究分析來發(fā)現(xiàn)這些知識在數(shù)學(xué)競賽中是如何運用的，增強學(xué)生在數(shù)學(xué)競賽中對此類問題的運用能力。

數(shù)學(xué)競賽；頂點的度；歐拉問題

一、圖論在數(shù)學(xué)競賽中的地位

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

圖論的起源和發(fā)展離不開趣味數(shù)學(xué)問題，被大眾所公認的圖論起源是一個有趣的數(shù)學(xué)問題——哥尼斯堡的七橋問題。數(shù)學(xué)競賽的舉辦是為了能夠?qū)χR活學(xué)活用，解決現(xiàn)實中的實際問題，圖論問題正好具備了這樣的條件，因此出現(xiàn)在了數(shù)學(xué)競賽中。

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

二、頂點的度在數(shù)學(xué)競賽中的應(yīng)用

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

解 ：用20個頂點來表示20條邊，成員之間如果進行了單打比賽，就在對應(yīng)的兩頂點之間連一條邊，從而得到圖。設(shè)各頂點的度為并且有di≥1?？傻茫?/p>

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

三、歐拉問題在數(shù)學(xué)競賽中的應(yīng)用

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

圖1

圖2

解：不存在這樣的走法。

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

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

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

[1]喬友付．圖論在數(shù)學(xué)競賽中的應(yīng)用[J]．科技視界，2012（1）．

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