【淺析圖論在中學(xué)數(shù)學(xué)競賽中的應(yīng)用7700字（論文）】

圖論在中學(xué)數(shù)學(xué)競賽中的應(yīng)用研究目錄TOC\o"1-3"\h\u4261前言 1278902圖論的基本概念 1115383數(shù)學(xué)競賽中的圖論問題 2261683.1度在數(shù)學(xué)競賽中的應(yīng)用 240713.1.1度的基本概念和歐拉定理 236863.1.2應(yīng)用舉例 2285393.2歐拉回路和歐拉跡在數(shù)學(xué)競賽中的應(yīng)用 422943.2.1通路、跡、道路、閉通路、圈和連通圖的基本概念 4202303.2.2連通圖的判斷定理 5110753.2.3歐拉回路和歐拉跡的概念 665153.2.4歐拉回路和歐拉跡的判斷定理 6234553.2.5應(yīng)用舉例 7283083.3哈密爾頓圈和哈密爾頓路在數(shù)學(xué)競賽中的應(yīng)用 10271873.3.1哈密爾頓圈和哈密爾頓路 10222873.3.2應(yīng)用舉例 10147894結(jié)束語 1231862參考文獻 131前言圖論這一學(xué)科較常見于數(shù)學(xué)領(lǐng)域，是該領(lǐng)域的重要組成部分。圖論的研究對象是圖，這種圖是以某些點和某些連接這些點中的某兩個點的線所構(gòu)成的，其中我們所說的點可以用來代表某一事物，而用來連接特定兩點之間的線，說明兩點事物之間存在一定的關(guān)聯(lián)。圖論的發(fā)展歷程很長，在十八世紀，人們一直熱烈的討論著一個七橋問題，即如何才能在不重復(fù)且不遺漏的情況下走完七座橋并回到出發(fā)點，這就是我們所說的著名的哥尼斯堡七橋問題，而著名的瑞士數(shù)學(xué)家Euler在1736年解決了這一問題，所有我們認為這是圖論的起源，而Euler被譽為圖論之父。在這以后，科學(xué)技術(shù)的不斷創(chuàng)新，使數(shù)學(xué)與其分支學(xué)科在社會發(fā)展和科學(xué)研究中的作用越來越大。2圖論的基本概念圖G包括了V(G)、E(G)與是的在內(nèi)的有序三元組。其中非空頂點集用V(G)表示，而E(G)與V(G)屬于不同的邊集，關(guān)聯(lián)函數(shù)用表示，它的作用在于G的不同邊與無序頂點相對應(yīng)，同時處于不相異狀態(tài)。假如圖G的一條邊設(shè)為e，若u、v與e相連接，則表示頂點公式為(e)=uv；e的端點即為u與v的頂點。圖繪制是指在平面上設(shè)置已知圖頂點位置，并連接對應(yīng)點與其邊。而歐幾米德圖表示的是在應(yīng)用地圖時，鑒于已知圖頂點與平面點相對應(yīng)，同時與圖繪制距離密切相關(guān)。G的項交替用頂點與邊表示，并滿足1≤i≤k條件，它是指一個有限非空序列，且用與表示端點。同時到的途徑用w表示，且兩個分別代表的是w的起點與終點，而其內(nèi)部頂點用，，，表示。w長度用k表示，并保持整數(shù)狀態(tài)。如果w與e（W）長度相同，表示其邊，，…，不盡相同。再次假設(shè)w起點與終點為路，且相同表示 其頂點，，，存在差異性，則途徑w呈現(xiàn)出環(huán)屬性。設(shè)圖中頂點到另一個頂點均具有一條路徑，表示該圖屬性為連通圖。大量的樹組成了森林環(huán)境，同時用無環(huán)連通圖來表示。在眾多樹繪制成的連通圖中，涉及了圖中所有子圖頂點，且用單一樹表示。另外森林圖是指圖中所有子圖頂點，表示的是整片森林情況。哈密爾頓圖在社會各領(lǐng)域的運用較廣，特別是在LRP行業(yè)中，較常見于處理VRP問題。圖G具有Hamilton圖特性，表示其中存在一條長為|V(G)|的圈。截止到目前，學(xué)者所研究的圖皆為無向圖范疇。另外邊為單向的是有向圖，其中在規(guī)定的頂點對邊中指定了單向連接方式，且視為有序?qū)?。其中在有向圖中，其邊被稱為有向邊，而該邊的第一個點與最后一個點，分別被稱為源尾與弧首，也被大家叫做弧t。入度是指在有向邊弧首中，一個頂點的數(shù)量，而出度表示的在弧尾的數(shù)量。3數(shù)學(xué)競賽中的圖論問題3.1度在數(shù)學(xué)競賽中的應(yīng)用3.1.1度的基本概念和歐拉定理前面已經(jīng)介紹了圖論中的基本概念，因此，這里不再重復(fù)度的概念了.設(shè)圖G是n階圖，在圖G中得到的度和邊數(shù)之間存在著密切的聯(lián)系，即有下面的定理和推論.定理1：圖G邊數(shù)的2倍量，即為整體點的度總和。定理1是圖論中最早出現(xiàn)的一個基本定理，它最早出現(xiàn)在著名數(shù)學(xué)家歐拉為解決哥尼斯堡七橋問題而撰寫并于1736年發(fā)表的論文里，是解決哥尼斯堡七橋問題的主要依據(jù).這個定理有許多重要的應(yīng)用，因此，它是解決數(shù)學(xué)競賽中有關(guān)問題的一個有力工具.推論：圖中奇次頂總數(shù)是偶數(shù).3.1.2應(yīng)用舉例例1：團體人數(shù)為1982名，其中隨機挑選4個人，且滿足其他三個人最少被一個人所熟悉。則問題是在團體中，其他所有成員被認識的最少人數(shù)。解：該團體整體人數(shù)用V表示，并以頂點方式來表示其中成員。設(shè)u、v為相鄰頂點，表示成員雙方是認識的，反之兩頂點不相鄰，且滿足u，v∈V，求解出在圖G中階簡單圖個數(shù)為1982。在分析上述已知條件過程中發(fā)現(xiàn)，假設(shè)4個頂點的1982階簡單圖，滿足最少有一個頂點相鄰于其他三個頂點。則問題是1981頂點最少數(shù)量是多少？設(shè)圖G為完全圖時，圖G的每個頂點的度都是1981.所以有1982個度為1981的頂點.當(dāng)圖G為非完全圖時，表示u與v頂點必然存在且處于不相鄰狀態(tài)，另外d（u）與d（v）滿足小于等于1980條件。所以在圖G的度中，頂點1981數(shù)量小于等于1980。假設(shè)在圖G中不止u與v兩個頂點，還包括不相鄰的x與y，則表示這四個頂點與圖G性質(zhì)相沖突，也沒有和其他三個頂點都相鄰頂點的存在。所以在圖G中，隨機都相鄰兩個頂點的說法，且不包括u與v。這反映出在圖G中，任意頂點范圍均不小于1979，并用x表示，這是排除u與v兩定點外而言的。同時當(dāng)任意頂點d（x）值為1981時，表示u與v均和x相鄰。在此過程中，圖G中1981的度的頂點數(shù)量為1980。如果不包括u與v兩個頂點，且與頂點x都不相鄰，則表示與題意相符；另外假設(shè)圖G中不包括u、v與x頂點，且y與之都處于相鄰狀態(tài)，得出d（u）、d（v）與d（x）都不大于1980，并滿足d（y）值為1981。因此在圖G中，1981的度頂點數(shù)量為1879，,這表明，如果1982階簡單圖G中任意四個頂點中必有一個頂點和其他三個頂點都相鄰，則G中至少有1979個度為1981的頂點.所以，該團體中認識其他所有人的成員最少是1979.例2：在一次舞會中，男性與女性數(shù)量均為7人，并按照每人跳舞次數(shù)從低到高順序排列如下：3，3，3，3，3，4，6，6，6，6，6，6，6，6（1）則說明此次統(tǒng)計數(shù)據(jù)有誤。證明：跳舞人的數(shù)量用點來表示，將兩個點連接為一條線，表示兩個人合作過一次跳舞。而圖中不同點的度的總和表示跳舞總次數(shù)，其中總數(shù)為奇數(shù)，而（1）中的奇數(shù)數(shù)量為5個，因此與定理1事實存在出入。例3：綜上例2所述，其結(jié)論真實性有待甄別。同時統(tǒng)一規(guī)定跳舞雙方的性別是男女搭配，禁止同性一起跳舞。解釋：在繪制圖中，男生與女生性別的不同，分別用黑點與紅點來表示。根據(jù)兩個人跳舞次數(shù)，標注相應(yīng)的邊的次數(shù)。同時按照約定內(nèi)容，紅點與黑點之間不允許相連。從而繪制出二部圖情況，得出所有黑點的度之和=所有紅點的度之和=圖中的邊數(shù)（2）在題中的14個數(shù)中，不被3整除的數(shù)有5個，同時保障（2）的一邊可以被3整除；而與之相反的一邊不被3整除的數(shù)量有1個，因此存在不相符情況。例4：晚會上大家握手言歡，試證握過奇次手的人數(shù)是偶數(shù).（全國初中數(shù)學(xué)競賽試題）證：構(gòu)作一圖，以參加晚會的人為頂，僅當(dāng)二人握手之時，在相應(yīng)的二項間加一條邊.于是沒人握手的次數(shù)即為所造的圖的相應(yīng)頂之次數(shù).由定理1的推論，奇次頂?shù)膫€數(shù)是偶數(shù)，所以握過手的人數(shù)為偶數(shù).3.2歐拉回路和歐拉跡在數(shù)學(xué)競賽中的應(yīng)用3.2.1通路、跡、道路、閉通路、圈和連通圖的基本概念圖（1）設(shè)G是一個圖，x0，x1，···，xk是圖G的某些頂點.如果圖G含有邊e1=x0x1，e2=x1x2，···，ek=xk-1xk，則由x0，x1，···，xk和e1，e2，···ek組成的點邊交錯序列（x0，e1，x1，e2，x2，···，xk-1，ek，xk）叫做圖G的一條長為k的通路，記作x0x1x2···xk.如果一條通路中所有的邊都不同，則稱它是一條跡，如圖（1），x1e1x2e8x2x4就是一條跡.如果通路中所有的頂點都不同，則稱它是一條道路，則圖（1）中x1e1x2x4x5是一條道路，始點和終點重合的通路叫做閉通路，則圖（1）中x1e1x2e8x2x4x5e5x1是一條閉通路，如果一條閉通路除始點和終點相重合外，其他頂點都不相同，則稱它為圈，則圖（1）中x1e1x2x4x5e5x1是圈.設(shè)G是一個圖，如果圖G是一階圖，或者圖G的階大于1，并且對圖G中任意兩個頂點u和v，總有一條以u為始點且以v為終點的通路，則圖G叫做連通圖，否則圖G叫做不連通的.圖（1）就是一個不連通的根據(jù)直觀感受，可以想到，對給定的圖G，它的頂點的度越大，它的邊數(shù)也就越大，任意兩個頂點之間的通路相連接的可能性就越大，因此圖G越有可能是連通的.當(dāng)然，這僅僅是一種直觀的想象.事實上，圖G的連通性和它的頂點的度之間確實存在密切的聯(lián)系.3.2.2連通圖的判斷定理遵循定理2可知，假如G的階簡單圖用n表示。若圖G中頂點的最小度δG滿足δ（G）≥n?1例5：有2n部電話交換臺，每部電話交換臺都至少和n部電話交換臺有直接線路連接.證明，其中任意兩部電話交換臺都可以進場一次通話（允許通過別的交換臺）.（“希望杯”邀請賽試題）證明：用頂點表示交換臺，其集合記作V.對于u，v∈V，當(dāng)且僅當(dāng)u和v表示的兩部交換臺有直通線連接時令u和v相鄰，得到的是2n階簡單圖.由于每部交換機都至少和n部交換臺連接直通線路，所以圖G中每個頂點的度至少是n.即圖G的頂點的最小度δG≥2n?12.由定理2可知，圖G屬于連通圖性質(zhì)。因此根據(jù)定義推斷，圖G中u與v頂點在隨機選擇狀態(tài)下，總有一條以u為起點且以v為終點的通路x0x1···xk，其中x0=u，xk=v，由于連接頂點xi+1和xi（i=1，2，···，k）的邊即是交換臺xi+1和xi的直通線路，所以只要接線人員按照直通線路x0x1，x1x2，···，xk-1xk例6：圓周上有13個點，能否用自然數(shù)1，2，3，···，13給這些點編號，使得任意兩個相鄰的點的號碼之差的絕對值至少是3，最多是5？（1986年匈牙利數(shù)學(xué)競賽試題）解：答案是“不能”.現(xiàn)在用反證法證明之.假設(shè)存在一種編號方法，使得任意兩個相鄰的點的號碼之差的絕對值至少是3，最多是5，把圓周上13個點視為13個頂點，其集合記作V.對于頂點u和v，當(dāng)且僅當(dāng)u和v所表示的兩個點相鄰時令頂點u和v相鄰，得到的是一個長為13的圈C13.很明顯，C13是連通的.用頂點所表示的點的編號表示頂點.將頂點集合V分劃為兩個子集X={1，2，3，11，12，13}和Y={4，5，6，7，8，9，10}.由于C13是一個圈，所以每個頂點的度都是2，又集合X中不相鄰的隨意的兩個頂點，因此在連接X與Y頂點時，邊的數(shù)量為12條，而C13恰有13條邊.因此Y的頂點之間必有一條邊.Y中的頂點4在X中只和頂點1相鄰，由于頂點4的度為2，所以頂點4必和Y中另一個頂點相鄰.同理.Y中頂點10必和Y中另一個頂點相鄰.但是頂點4和10不相鄰.這表明，Y中頂點之間至少連有兩條邊，矛盾.因此不存在合乎條件的編號方式.3.2.3歐拉回路和歐拉跡的概念在熟悉了圖的連通概念之后，現(xiàn)在再來談?wù)剼W拉關(guān)于哥尼斯堡七橋問題的研究.首先，把哥尼斯堡管轄只下的四個城區(qū)A，B，C，D視為4個頂點，連接城區(qū)的沒做橋都視為邊，得到的是4階圖G（圖（2））.于是問題化為：從圖G中每個頂點出發(fā)，能否存在一條通路，經(jīng)過每條邊恰好一次，然后回到原來的頂點.換句話說，圖G中是否含有圖G所有的邊的回路.圖（2）一般來說，n階圖G中含有所有邊的回路叫做歐拉回路。其中歐拉圖是指圖G中含有歐拉回路的圖像。然后將存在的問題進一步轉(zhuǎn)化為：圖（2）中的四階圖是否是歐拉圖.歐拉圖和所謂的一筆畫問題有著密切的聯(lián)系.所謂一筆畫問題就是，紙面上給定的一個圖G,能否從圖G的一個頂點出發(fā)，筆不離開紙，而且連續(xù)地沿著每條邊恰好一次，然后回到原來的頂點，從而畫出整個圖G？很顯然，如果圖G是歐拉圖，則可以一筆畫出整個圖G，否則就不能.圖（2）不是歐拉圖，則不能一筆畫出整個圖G.3.2.4歐拉回路和歐拉跡的判斷定理定理3：設(shè)G是連通圖，則G為歐拉圖的充分必要條件是，圖G中的每個頂點的度是偶數(shù).有了定理3，哥尼斯堡七橋問題的答案就是顯而易見的.從圖（2）可以看出，其中的圖G是連通的，而且圖G中每個頂點都不是偶頂點，因此，由定理3，圖G不是歐拉圖，則說明哥尼斯堡七橋所得出的答案是否定的。同時對上述問題進一步分析，既然不能得到肯定的答案，那么是否可以退而求其次呢？即考慮如下的問題：能否從哥尼斯堡某個城區(qū)出發(fā)，經(jīng)每座橋恰好一次，然后達到另一個城區(qū)？那么這個問題就相當(dāng)于是對于給定一個圖G，對其中某個頂點u，是否存在以u為端點的一條跡，使得圖G中每條邊恰好在其中出現(xiàn)一次.如果這樣的跡存在，則稱它為圖G的一條歐拉跡.歐拉跡和歐拉回路的差別在于，后者是處于閉通路的狀態(tài)。定理4：假如u和v兩個頂點，與圖G相連接，則圖G具有一條連接頂點u和v的歐拉跡的充分必有條件是，u和v是奇頂點，其他所有頂點都是歐拉點.綜合定理3和定理4，可得到以下的推論.推論：有限圖G可以一筆畫成的充要條件是連接G，同時滿足奇頂點數(shù)量為0或者2。當(dāng)奇頂點與圖G連接，形成一個圈時，則表示奇頂點數(shù)量為0。通過觀察推論可以看出，所謂的退而求其次形式的哥尼斯堡七橋問題的答案也是否定的，因為圖（2）中的圖G中不含有偶頂點.3.2.5應(yīng)用舉例例8：有一天小明在完成作業(yè)后，正在享受音樂帶來的輕松愉悅感。并在紙上隨意寫下了田、日與中三個字。忽然他想到一個有趣的問題，那就是一筆能寫出這幾個字嗎？于是在沒有重復(fù)筆劃情況下，順利寫下了日與中兩個字，而在反復(fù)實驗田字時卻屢次失敗。這是一道關(guān)于小學(xué)的奧林匹克競賽試題。圖（3）圖（4）圖（5）解把“中”這個字的每一個重合的地方看作頂點，如圖（3）所示，分別把各個頂點記作a、b、c、d、e、f、g、h.由圖可知，各個頂點的度依次為2、4、2、2、4、2、1、1，則可以知道它其中的6個頂點的度為偶數(shù)，另外兩個為奇數(shù)，即奇頂點的個數(shù)為2，由推論可知，“中”字可以一筆畫成，且起點和終點分別為g和h（或h和g），則可按圖（6）所示方法一筆畫成（方法不唯一）,即從gbcfedabeh.圖（6）同樣的，把“日”的每一個重合的地方看作頂點，如圖（4）所示，分別把各個頂點記作a、b、c、d、e、f.由圖所知，各個頂點的度依次為2、2、3、3、2、2，則可以知道它的各個頂點中有兩個奇頂點和四個偶頂點，由推論可知，“日”可以一筆畫出，且起點和終點分別為c和d（或d和c），則可按圖（7）所示方法一筆畫出（方法不唯一）,即cabdcefd.圖（7）把“田”這個字的每一個重合的地方看做頂點，如圖（5）所示，分別把各個頂點記作a、b、c、d、e、f、g、h、i.由圖所知，各個頂點的度依次為2、3、2、3、4、3、2、3、2，則可以知道它的各個頂點中有四個奇頂點和五個偶頂點，由圖論可知，“田”不能一筆畫出.例8：指出圖（8），圖（9）和圖（10）中哪一個圖，可以從圖中的某個點出發(fā)，用鉛筆不離開紙面，一筆畫出整個圖？圖（8）圖（9）圖（10）圖（11）解：把圖（8）中圓周的交點視為頂點，其集合記V.對于頂點u，v∈V，當(dāng)且僅當(dāng)交點u和v有圓弧相連接時令頂點u和v相鄰，得到的是6階圖G1，詳情見12示意圖。其中在圖G1中，不同頂點的度均為4，通過定理3總結(jié)出其存在歐拉回路效應(yīng)。因此，可以從圖（8）中的某個交點出發(fā)，按照一條歐拉回路上頂點的順序，沿著圓弧，一筆畫出整個圖，最后回到原來的交點上.把圖（9）中的交點視為頂點.當(dāng)且僅當(dāng)交點間有線段連接時，令相應(yīng)的頂點相鄰，得到的圖記作G2,.圖G2中恰有兩個3度頂點x和y，其他頂點都是偶頂點，有定理4，圖G2含有一條以x和y為端點的歐拉跡，于是，從點x出發(fā)，按照這條歐拉跡中頂點的順序，一筆畫出整個圖，最后到達點y.和圖（9）相似，圖（10）中含有四個奇頂點x，y，z和w，因此不能一筆畫出圖（11）.3.3哈密爾頓圈和哈密爾頓路在數(shù)學(xué)競賽中的應(yīng)用3.3.1哈密爾頓圈和哈密爾頓路哈密爾頓圖是指在圖G中，頂點與圈的接觸次數(shù)為一次所形成的圖，如果形成的是圈的形狀則被稱為哈密爾頓圈。而哈米爾頓路則表示的是在圖G中，頂點與路的接觸次數(shù)為一次，所形成的路。愛爾蘭物理學(xué)家哈密爾頓提出了圖論研究的一個重要課題，也就是對哈密爾頓圖的甄別。在觀察淺層面過程中顯示出，哈密爾頓圈和一筆畫很相似，其實質(zhì)卻迥然不同，對于圖G的哈密爾頓圈C，只要求圖G的每個頂點都在圈C上出現(xiàn)，而且只出現(xiàn)一次.至于圖G的邊，則不作任何要求，即允許在圈C上出現(xiàn)，也可以再圈C上不出現(xiàn).對于圖G的歐拉回路C*，則正相反，它要求圖G的每條邊都要在回路C*上出現(xiàn)一次，而且只出現(xiàn)一次，而對圖G的頂點，則不計其出現(xiàn)與否.前面已經(jīng)知道判斷一個圖是否是歐拉圖問題已經(jīng)徹底、干凈的解決了.但判斷一個圖是否是哈密爾頓圖問題，至今仍未解決.它是圖論問題的一個難題，是世界各國許多圖論專家所關(guān)注的研究課題之一.在這里，我只介紹一個比較簡單、比較實用的物理學(xué)界定理.定理5：假如G的階簡單圖用n表示。選擇圖G中u與v，同時兩個頂點為任意不相鄰的頂點，則關(guān)系式如下du+d則說明圖G表示的是哈密爾頓圖.總結(jié)出在圖G中，其定點數(shù)最小度范圍為≥n2,3.3.2應(yīng)用舉例例9：傳說英國有一位國王，叫亞瑟王，在王宮內(nèi)傳喚了2n名騎士，并在少數(shù)騎士中心存仇怨.已知每名騎士的仇人不超過n-1個.證明，亞瑟王的謀士摩爾林一定有辦法讓這2n名騎士圍著圓桌入座，使得每名騎士都不和他的仇人坐在一起.（波蘭數(shù)學(xué)競賽試題）證：用頂點表示騎士，當(dāng)且僅當(dāng)騎士x和y互不成仇時頂點x和y相鄰，得到的2n階簡單圖記作G.由于騎士之間仇人數(shù)量小于n-1個，因此圖G中所有頂點的度都至少是n.由定理5的推論，圖G是哈密爾頓圖，即圖G具有哈密爾頓圈.于是只要讓這2n名騎士按照這條哈密爾頓圈的頂點順序就座，每名騎士兩旁就座的就不是他的仇人.例10：舉行一個國際會議，依次存在A-F不同情況的7個人。同時所了解到的事實如下：A擅長英語；B在A的基礎(chǔ)上增加了漢語；C懂得俄語、英語與意大利語；D精通漢語與日語；E會使用意大利語與德語交流；F占據(jù)俄語、日語與法語優(yōu)勢；G善于德語與法語知識。那么，綜上所述這7人應(yīng)該如何安排座位，才能使每個人都能和他身邊的人交談？（小學(xué)奧林匹克數(shù)學(xué)競賽試題）解：依據(jù)已知條件建立一個圖的模型，我們用點表示人，于是得到點集V={A，B，C，D，E，F(xiàn)，G}.對于任意兩點，若有共同語言，就在他們之間連一條線，可以得到邊集E，得出圖G=（V，E），詳情見（12）示意圖：圖（12）為了便于身邊人開展交流，需要有