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