利用圖論知識解決實際問題.doc

淮北師范大學(xué) 2013屆學(xué)士學(xué)位論文 利用圖論知識解決實際問題的方法探究 學(xué)院、專業(yè) 數(shù)學(xué)科學(xué)學(xué)院 數(shù)學(xué)與應(yīng)用數(shù)學(xué) 研 究 方 向 離散數(shù)學(xué) 學(xué) 生 姓 名 楊 波 學(xué) 號 20091101179 指導(dǎo)教師姓名 劉楠楠 指導(dǎo)教師職稱 講 師 2013年3月25日利用圖論知識解決實際問題的方法探究楊 波（淮北師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院，淮北，235000）摘 要圖論是數(shù)學(xué)的一個分支,是近年來發(fā)展迅速而又應(yīng)用廣泛的一門新興學(xué)科。隨著科學(xué)的進(jìn)步，圖論知識越來越貼近于生產(chǎn)和生活，所以利用圖論知識來解決實際問題又成為當(dāng)今的一大熱點。著色、繪圖、運輸最短路徑、集合等都與圖論知識離不開。本課題將重點利用圖論知識來解決實際生活、生產(chǎn)中的問題。本文首先介紹了圖的基本概念，對圖論所涉及的基本知識進(jìn)行簡單的闡述，使讀者對圖論知識有一定的了解；再介紹圖論中兩種特殊的圖形：歐拉圖和哈密頓圖，并用它們分析如何解決最短路問題和貨郎擔(dān)問題；然后介紹著色問題以及其與實際生活的聯(lián)系；最后通過實例來說明圖論知識在日常生產(chǎn)、生活中的運用。關(guān)鍵詞 圖論，歐拉圖，哈密頓圖，最短路徑，著色問題, 應(yīng)用The method of using graph theory knowledge to solve practical problems Yang Bo （College of Mathematical Science, Huaibei Normal University, Huaibei, 235000） Abstract Graph theory is a branch of mathematics that has been developed rapidly and used widely in recent years. With the progress of science, graph theory is increasingly close to the production and life, so using the knowledge of graph theory to solve practical problems has become a focus today. Coloring, drawing, the shortest path of transportation cannot be separated from graph theory knowledge. The article lays press on the using of graph theory to solve the practical problems in production knowledge in real life. This article first introduces the basic concept of graph, and make a further introduction to the basic knowledge of graph theory which involved a simple elaboration, then the reader can have a certain knowledge of graph theory knowledge; Then two kinds of special graphics are referred to: the Eulerian graph and Hamiltonian graph, along with their analysis of how to solve the problem of the short circuit and traveling salesman problem. Then the article discuss the coloring problem and its links with real life; Finally by an example to illustrate the application of graph theory knowledge in daily life and production.Keywords Graph theory, Eulerian graph, Hamiltonian graph, shortest paths,coloring, application 目 錄引 言1（一）預(yù)備知識 1 1 圖的基本概念 1 2 通路與回路4 3 圖的連通性6 4 圖的矩陣表示 8（2） 歐拉圖與哈密頓圖10 1 歐拉圖10 2 哈密頓圖.10 3 最短路問題與貨郎擔(dān)問題.13（三）著色16 1 點著色16 2 邊著色16（四）圖論知識在實際生活、生產(chǎn)中的應(yīng)用18 1 哥尼斯堡七橋問題18 2 哈密頓圖的實際應(yīng)用19 3 教師如何分配課時問題 20 結(jié) 論21 參考文獻(xiàn)21 致 謝23 引言 在現(xiàn)實生活中，我們會遇到很多復(fù)雜的問題，介于此我們希望用到我們所學(xué)過的數(shù)學(xué)方法去簡化它，優(yōu)化它和解決它。圖論知識就是一個很好的工具，將實際問題化為圖后，我們能清楚的觀察到整個局面，方便我們進(jìn)行具體的分析。所以研究和總結(jié)圖的應(yīng)用算法是件有意義且必要的事情。本課題將著重通過圖論知識來解決實際生活、生產(chǎn)中所遇到的著色，最短路徑，繪圖等問題。通過其在實際生活中的應(yīng)用，來認(rèn)識圖論知識在學(xué)習(xí)中的重要性。 （一）、預(yù)備知識 在日常生活、生產(chǎn)活動及科學(xué)研究中，人們常用點表示事物，用點與點之間是否有連線表示事物之間是否有某種關(guān)系，這樣構(gòu)成的圖形就是圖論中的圖。其實，集合論中二元關(guān)系的關(guān)系圖都是圖論中的圖。在這些圖中，人們只關(guān)心是否有連線，而不關(guān)心點的位置，以及連線的曲直，這就是圖論中圖與幾何學(xué)中圖形的本質(zhì)區(qū)別，下面我們先來介紹圖論中圖的一些基本概念，再對來研究用圖論知識解決實際問題的方法。 1圖的基本概念 定義1.1 一個無向圖是一個有序的二元組，其中 是一個非空有窮集，稱為頂點集，其元素稱為頂點或結(jié)點。 是無序積&的有窮多重子集（元素可以重復(fù)出現(xiàn)的集合稱為多重集合。某元素重復(fù)的次數(shù)稱為該元素的重復(fù)度。），稱為邊集，其元素稱為無向邊，簡稱為邊。 定義1.2 一個有向圖是一個有序的二元組，其中 是一個非空有窮集，稱為頂點集，其元素稱為頂點或結(jié)點。 是笛卡爾積的有窮多重子集，稱為邊集，其元素稱為有向邊，簡稱邊。 通常用圖形來表示無向圖和有向圖：用小圓圈（或?qū)嵭狞c）表示頂點，用頂點之間的連線表示無向邊，用帶箭頭的連線表示有向邊。 例1.1 給定無向圖，其中，根據(jù)定義畫出無向圖，如圖1.1中（a）. 給定有向圖，其中，；根據(jù)定義畫出有向圖，如圖1.1中（b）. 圖1.1與定義1.1和1.2有關(guān)的還有下面一些概念和規(guī)定：1. 頂點數(shù)稱為圖的階，個頂點的圖稱為階圖.2. 一條邊也沒有的圖稱為零圖.階零圖記為.1階零圖稱為平凡圖.平凡圖只有一個頂點，沒有邊.3. 當(dāng)用圖形表示圖的時候，如果給每一個頂點和每一條邊指定一個符號（字母或數(shù)字,當(dāng)然字母還可以帶下標(biāo)），則稱這樣的圖標(biāo)定圖，否則稱為非標(biāo)定圖.定義1.3 在無向圖中，如果關(guān)聯(lián)一對頂點的無向邊多于1條，則稱這些邊為平行邊，平行邊的條數(shù)稱為重數(shù)。在有向圖中，如果關(guān)聯(lián)一對頂點的有向邊多于1條，并且這些邊的始點與終點相同（也就是它們的方向相同），則稱這些邊為平行邊。 例如在圖1.1中，中與是平行邊，在中，與是平行邊，而與不是平行邊。，兩個圖不是簡單圖。 例1.2 先將圖1.2中各圖的頂點標(biāo)定順序，然后寫出各圖的集合表示. 圖1.2解 圖1.2中（a）、（b）的頂點標(biāo)定順序如下圖所示（a） 的集合表示為，其中 （b）的集合表示為，其中定義1.4 設(shè)為無向圖，稱作為邊的端點的次數(shù)之和為的度數(shù)，簡稱為度，記作。在不發(fā)生混淆時，略去下標(biāo)，簡稱為。設(shè)為有向圖，稱作為邊的始點的次數(shù)之和為的出度，記作，簡稱。稱作為邊的始點的次數(shù)之和為的入度，記作，簡稱。稱為的度數(shù)，記作，簡記作.定義1.5 設(shè)為一個階無向圖，為的度數(shù)列.對于頂點標(biāo)定的無向圖，它的度數(shù)列是唯一的.反之，對于對于給定的非負(fù)整數(shù)列，若存在以為頂點集的階無向圖，使得，則稱是可圖化的.特別地，若所得到的圖是簡單圖，則稱是可簡單圖化的.下面關(guān)于圖的度數(shù)給出兩個結(jié)論。 定理1.15 非負(fù)整數(shù)列是可圖化的當(dāng)且僅當(dāng)為偶數(shù).定理1.25 設(shè)為任意階無向簡單圖，則（在無向圖中，）. 定義1.6 設(shè)，為兩個無向圖（兩個有向圖），若存在雙射函數(shù)使得，當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)，并且與與的重數(shù)相同，則稱與同構(gòu)，記作. 定義1.7 設(shè)為階無向簡單圖，若中每個頂點均與其余的個頂點相鄰，則稱為階無向完全圖，簡稱階完全圖，記作. 2 通路與回路 定義2.1 設(shè)為無向標(biāo)定圖，中頂點與邊的交替序列稱為到的通路，其中為的端點，分別稱為的始點與終點，中邊的條數(shù)稱為它的長度。若又有，則稱為回路。若的所有邊各異，則稱為簡單通路。若又有，則稱為簡單回路。若所有頂點（除與可能相同外）各異，所有邊也各異。則稱為初級通路或路徑。若又有，則稱為初級回路或圈。將長度為奇數(shù)的圈稱為奇圈，長度為偶數(shù)的圈稱為偶圈。注意，在初級通路與初級回路的定義中，仍將初級回路看成初級通路（路徑）的特殊情況，知識在應(yīng)用中的初級通路（路徑）都是始點與終點不相同的，長為1的圈智能由環(huán)生成，長為2的圈只能由平行邊生成，因而在簡單無向圖中，圈的長度至少為3.另外，若中有邊重復(fù)出現(xiàn)，則稱為復(fù)雜通路.若又有則稱為復(fù)雜回路.定理2.15 在階圖中，若從頂點到存在通路，則從到存在長度小于或等于的通路. 推論5 在階圖中,若從頂點到存在通路，則從到一定存在長度小于或等于的通路（路徑）. 定理2.25 在階圖中,若存在到自身的回路，則一定存在到自身長度小于或等于的回路. 推論5 在階圖中,若存在到自身的簡單回路，則一定存在到自身長度小于或等于的初級回路. 例2.1 無向完全圖中有幾種非同構(gòu)的圈？ 解 長度相同的圈都是同構(gòu)的，因而只有長度不同的圈才是非同構(gòu)的.易知中含長度為的圈，所以中有種非同構(gòu)的圈. 長度相同的圈都是同構(gòu)的，因此在同構(gòu)意義下給定長度的圈只有一個.在標(biāo)定圖中，圈表示成頂點和邊的標(biāo)記序列.如果只要兩個標(biāo)記序列不同，就認(rèn)為這兩個圈不同，稱這兩個圈在定義意義下不同. 例2.2 無向完全圖的頂點依次標(biāo)定為.在定義意義下有多少個不同的圈？ 解 在同構(gòu)意義下，中只有一個長為3的圈.但在定義意義下，不同起點（始點）的圈是不同的，頂點間排列順序不同的圈也看成是不同的，因而中有6個不同的長為3的圈：，.如果只考慮起點（終點）的差異，而不考慮順時針逆時針的差異，應(yīng)該有3種不同的圈，當(dāng)然它們的長度都是3. 3 圖的連通性定義3.1 設(shè)無向圖，若之間存在通路，則稱是連通的，記作.規(guī)定：.若無向圖是平凡圖或中任何兩個頂點都是連通的，則稱為連通圖，否則稱為非連通圖. 定義3.2 設(shè)無向圖，是關(guān)于頂點之間的連通關(guān)系的一個等價類，稱導(dǎo)出子圖為的一個連通分支.的連通分支數(shù)記為. 定義3.3 設(shè)為無向圖中任意兩個頂點，若，則稱之間長度最短的通路為之間的短程線.短程線的長度稱為之間的距離，記作.當(dāng)不連通時，規(guī)定.距離有以下性質(zhì)：，1. ，且當(dāng)且僅當(dāng)時等號成立.2. 具有對稱性：.3. 滿足三角不等式：. 定義3.4 設(shè)無向圖，若存在使得，且對于任意的，均有，則稱是的邊割集，或簡稱為割集.若，則稱為割邊或橋. 定義3.5 設(shè)為無向連通圖且不是完全圖，則稱 為的點割集.為的點連通度，簡稱連通度.有時簡記為.規(guī)定完全圖的點連通度為，非連通圖的點連通度為0.又若，則稱是連通的，為非負(fù)整數(shù).例圖3.1中圖的點連通度為1，此圖為連通圖，的點連通度，所以是連通圖，連通圖.連通圖，連通圖. 定義3.6 設(shè)是無向連通圖，稱 為的邊割集為的邊連通度.有時簡記為.規(guī)定非連通圖的邊連通度為0.又若，則稱邊連通圖. 例3.1 求圖3.2所示各圖的點連通度和邊連通度，并指出它們各是幾連通圖及幾邊連通圖，最后將它們按點連通程度及邊連通程度排序. 圖3.2 解 設(shè)第個圖的點連通度為，邊連通度為容易看出，,. 是連通圖，邊連通圖， 是連通圖，邊連通圖， 是連通圖，邊連通圖， 是連通圖，邊連通圖. 是連通圖，邊連通圖， 是連通圖，邊連通圖， 是連通圖，邊連通圖. 是連通圖，邊連通圖.點連通程度為：.邊連通程度為：.定義3.7 設(shè)無向圖，若能將劃分成和（即， 且），使得中的每條邊的兩個端點都是一個屬于，另一個屬于，則稱為二部圖，稱和為互補頂點子集，常將二部圖記為.又若是簡單二部圖，中每個頂點均與中所有頂點相鄰，則稱為完全二部圖，記為，其中. 4 圖的矩陣表示 圖可以用集合來定義，但多半用圖形來表示，還可以用矩陣來表示。用矩陣表示圖便于用代數(shù)方法研究圖的性質(zhì)。為了用矩陣表示圖，必須指定頂點或邊的順序，使其成為標(biāo)定圖。 定義4.1 設(shè)無向圖，令為頂點與邊的關(guān)聯(lián)次數(shù)，則稱為的關(guān)聯(lián)矩陣，記作。 定義2 設(shè)有向圖中無環(huán)，令 則稱為的關(guān)聯(lián)矩陣，記作。圖4.1所示圖的關(guān)聯(lián)矩陣為 圖4.1有如下各條性質(zhì)：1. 每一列恰好有一個和一個.2. 的個數(shù)等于的個數(shù)，都等于邊數(shù)，這正是有向圖握手定理的內(nèi)容.3. 第行中，的個數(shù)等于，的個數(shù)等于.4. 平行邊所對應(yīng)的列相同. 例4.1 圖4.2的完全關(guān)聯(lián)矩陣為： 圖4.2 設(shè)是無向圖，的完全關(guān)聯(lián)矩陣有如下性質(zhì)： 1.每列元素之和為2.這說明每條邊關(guān)聯(lián)兩個結(jié)點. 2.每行元素之和是對應(yīng)結(jié)點的度數(shù). 3.所有元素之和是圖中各結(jié)點度數(shù)的總和，也是邊數(shù)的2倍. 4.兩列相同則對應(yīng)的兩條邊是平行邊. 5.某行元素全為0，則對應(yīng)的結(jié)點為孤立點.（2） 歐拉圖與哈密頓圖 1 歐拉圖 定義1.1 通過圖（無向圖或有向圖）中所有邊一次且僅一次行遍所有頂點的通路稱為歐拉通路.通過圖中所有邊一次僅一次行遍所有頂點的回路稱為歐拉回路.具有歐拉回路的圖稱為歐拉圖.具有歐拉通路而無歐拉回路的圖稱為半歐拉圖.規(guī)定平凡圖是歐拉圖.下面給出一些判斷無向圖和有向圖是否為歐拉圖或半歐拉圖的方法1。 定理1.1 無向圖是歐拉圖當(dāng)且僅當(dāng)是連通圖且沒有奇度頂點. 定理1.2 無向圖是半歐拉圖當(dāng)且僅當(dāng)是連通圖且且恰有兩個奇度頂點. 定理1.3 有向圖是歐拉圖當(dāng)且僅當(dāng)是強連通的且每個頂點的入度等于出度. 定理1.4 有向圖是半歐拉圖當(dāng)且僅當(dāng)是單向連通的且恰有兩個奇度頂點，其中一個的入度比出度大1，另一個頂點出度比入度大1，而其余頂點的入度等于出度.定理1.5 是非平凡的歐拉圖當(dāng)且僅當(dāng)是連通的且是若干個邊不重的圈的并. 2 哈密頓圖定義2.1 經(jīng)過圖（有向圖或無向圖）中所有頂點一次且僅一次的通路稱為哈密頓通路.經(jīng)過圖中所有頂點一次且僅一次的回路稱為哈密頓回路.具有哈密頓回路的圖稱為哈密頓圖，具有哈密頓通路但不具有哈密頓回路的圖稱為半哈密頓圖.規(guī)定平凡圖是哈密頓圖.下面給出無向圖或有向圖為哈哈密頓圖的一些充分或必要條件。定理2.15 設(shè)無向圖是哈密頓圖，則對于任意且，均有 證 設(shè)是中任意一條哈密頓回路.易知，當(dāng)中頂點在上均不相鄰時，所以有.而是的生成子圖，所以有. 例2.1 在圖2.1中給出的3個圖都是二部圖，它們中的哪些是哈密頓圖？哪些是半哈密頓圖？為什么？ (a) (b) (c) 圖2.1解 在(a）中，互補頂點子集.設(shè)此二部圖為.由定理2.1可知，不是哈密頓圖，也不是半哈密頓圖.設(shè)（b）中圖為，其中.由定理2.1可知，不是哈密頓圖.而是一條哈密頓通路，故是半哈密頓圖.在（c）中，是一條哈密頓回路，所以（c)是哈密頓圖.設(shè)這個圖為，其中.此處有.一般情況下，設(shè)二部圖，且由定理2.1可以得出下面結(jié)論：（1） 若是哈密頓圖，則.（2） 若半哈密頓圖，則.（3） 若，則不是哈密頓圖，也不是半哈密頓圖. 定理2.25 設(shè)是階無向簡單圖，若對于中任意不相鄰的頂點，均有 則中存在哈密頓通路. 推論 設(shè)為階無向簡單圖，若對于中任意不相鄰的頂點，均有 則中存在哈密頓回路. 定理2.35 設(shè)為階無向簡單圖中兩個不相鄰的頂點，且，則為哈密頓圖當(dāng)且僅當(dāng)為哈密頓圖（是加的新邊）. 下面我們舉例來看哈哈密頓圖在實際中的應(yīng)用。 例2.2 在某次國際會議的預(yù)備會中，共有7人參加，他們來自不同的國家.已知他們中任何兩個無共同語言的人，與其余由共同語言的人數(shù)之和大于或等于7，試證明能將這7個人排在圓桌旁，使其任何人能與兩邊的人交談. 解 設(shè)7個人分別為作無向簡單圖，其中，與有共同語言，.為7階無向簡單圖，為與有共同語言的人數(shù).由已知條件，且，均有.由定理2.2的推論可知，中存在哈密頓回路，設(shè)為中一條哈密頓回路，按這條回路的順序安排座次即可. 3 最短路問題與貨郎擔(dān)問題定義3.1 設(shè)圖（無向圖或有向圖），給定，對的每一條邊，稱為邊的權(quán).把這樣的圖稱為帶權(quán)圖，記作.當(dāng)，把記作. 設(shè)是中的一條通路，中所有邊的權(quán)之和稱為的長度，記作，即.類似地，可定義回路的長度.本節(jié)考慮帶權(quán)圖上的兩個問題最短路問題和貨郎擔(dān)問題.設(shè)帶權(quán)圖（無向圖或有向圖），其中每一條邊的權(quán)為非負(fù)實數(shù).當(dāng)和連通（可達(dá))時，稱從到長度最短的路徑為從到的最短路徑，稱其長度為從到的距離，記作.約定：；當(dāng)和不連通（不可達(dá))時，.最短路問題：給定帶權(quán)圖及頂點和，其中每一條邊的權(quán)為非負(fù)實數(shù)，求從到的最短路徑.不難看出，如果是從到的最短路徑，則對每一個，其中表示的后的下標(biāo)是從到的最短路徑.根據(jù)此于1959年給出下述最短路徑算法.算法給出從頂點的起點到每一點的最短路徑.在計算過程中，賦予每一個頂點一個標(biāo)號.標(biāo)號分永久標(biāo)號和臨時標(biāo)號.在的永久標(biāo)號中，是從到的距離，是從到的最短路徑上的前一個頂點.當(dāng)為臨時標(biāo)號時，和分別是當(dāng)前從經(jīng)過永久標(biāo)號的頂點到的長度最短的路徑上的前一個頂點和這條路徑的長度. 例3.1 貨郎擔(dān)問題（旅行商問題） 有n個城市，給定城市之間道路的長度（長度可以為無窮大，對應(yīng)兩個城市之間無交通線）。一個旅行商從某個城市出發(fā)，要經(jīng)過每個城市一次且僅一次，最后回到出發(fā)的城市，問如何走才能使他走的路線最短？這個問題可以用圖論方法描述如下：設(shè)G=為一個n階完全帶權(quán)圖，各邊的權(quán)W（e）非負(fù)且可以.求G中一條最短的哈密頓回路.例如，圖3.1（a）給出一個4階完全帶權(quán)圖.不計起點、也不計順時針和逆時針，只有3條不同的哈密頓回路： a b c d a a b d c a a c b d a分別如(b),(c),(d)所示，其長度分別為8,10,12.因此，是所求的最短路線. 圖3.1 至今還沒有找到解決貨郎擔(dān)問題的有效算法，還需要我們繼續(xù)探討. 例1 求圖3.2所示帶權(quán)圖中的貨郎擔(dān)問題（即求圖中的最短的哈密頓回路）. 解 由于完全圖中共存在條不相同的哈密頓回路.在完全帶權(quán)圖中，設(shè)頂點分別為，回路與回路的權(quán)相同，因而僅要考慮條哈密頓回路.在圖3.2中，因此共有12條回路.分別求出這12條回路的權(quán)，其中權(quán)最小的即為最短的哈密頓回路. 圖3.2 設(shè) ： ，其權(quán) ，其權(quán) ，其權(quán) ，其權(quán) ，其權(quán) ，其權(quán) ，其權(quán) ，其權(quán) ，其權(quán) ，其權(quán) ，其權(quán) ，其權(quán)從結(jié)果可知，最短哈密頓回路為，其權(quán).至今還沒有找到求解貨郎擔(dān)問題的快速算法，當(dāng)較大時，計算量會迅速的增加. （三） 平面圖的著色問題 圖著色問題的研究起源于四色猜想，著色問題包含點著色，邊著色和地圖著色等.點著色和邊著色都是對無環(huán)的無向圖進(jìn)行的，下面我們著重介紹點著色和邊著色 1 點著色 定義1.1 設(shè)無向圖無環(huán)，對的每個頂點涂一種顏色，使相鄰的頂點涂不同的顏色，稱為圖的一種點著色，簡稱著色。若能用種顏色給的頂點著色，則稱是可著色的。若是可著色的，但不是可著色的，則稱的色數(shù)為。的色數(shù)記作，簡記作。定義1.2 對地圖的每個國家涂上一種顏色，使相鄰的國家涂不同的顏色，稱為對地圖的面著色。若能夠用種顏色給的面著色，則稱是可面著色的。若是可面著色的，但不是可面著色的，則稱的面色數(shù)為。的面色數(shù)記作，簡記作。 2 邊著色 定義2.1 對圖的每條邊著一種顏色，使相鄰的邊著不同的顏色，稱為對圖的邊著色。若能用種顏色給的邊著色，則稱是可邊著色的。若是可邊著色的，但不是可邊著色的，則稱的邊色數(shù)為。的邊色數(shù)記作，簡記作。定理2.1定理 簡單圖的邊色數(shù)只可能取兩個值：或者. 定理2.2 n1，其中n4.證明 當(dāng)n=4或5時，不難用3種顏色和4種顏色分別給和的邊著色.如圖4所示。又它們的分別為3和4，因此由定理得證結(jié)論正確。 圖2.1 當(dāng)n6時，中間頂點關(guān)聯(lián)的n1條邊用n1種顏色著色，而外圈上的每一條邊都與4條邊相鄰，總可以從這n15種顏色中找到一種顏色給它著色，所以，又由定理，得證. 定理2.3 當(dāng)為奇數(shù)時，而當(dāng)為偶數(shù)時，. 證明： 為奇數(shù)且，由定理可知，.下面證明. 如下畫：先畫正邊形，將上不相鄰得頂點之間都連線段就得到.在中共有組平行線，每組條邊.條平行邊關(guān)聯(lián)個頂點，因而在的邊著色中至多有條邊同色，故，得. 圖2.2 為偶數(shù)時，由定理，.下面證明.可如下獲得：先畫出為奇數(shù)，然后在的中心放置一個頂點，連接中心點與上的所有頂點.時的情況如圖5所示.用種顏色給的邊著色，然后給與中心點關(guān)聯(lián)的邊著中與它垂直的邊的顏色，就完成了的邊著色. 圖著色在實際中的應(yīng)用設(shè)學(xué)校共有們功課需要進(jìn)行期末考試，因為不少學(xué)生不止選修一門課，所以不能把同一學(xué)生選修的兩門課放在同一場次進(jìn)行考試.問期末考試最少需要多少場次才能完成？解： 我們以每門功課為一個頂點當(dāng)且僅當(dāng)兩門課被同一學(xué)生選修時，在兩個頂點之間連一條邊，得到一個圖.我們將門課程劃分為個子集兩兩子集的課程都不相同.每個子集的頂點不相鄰，即子集內(nèi)的任何兩門課程都不能被一個學(xué)生選修.要求劃分的子集數(shù)最少，即不能將門課程劃分成個子集.然后我們對每個子集內(nèi)的頂點涂一種顏色.同色頂點對應(yīng)的課程安排在同一場次考試，顏色總數(shù)即為考試所需要的場次數(shù)，即所求的值.（四）圖論知識在實際生活、生產(chǎn)中的運用 例1 哥尼斯堡七橋問題18世紀(jì)中葉在歐洲普魯士的哥尼斯堡城內(nèi)有一條貫穿全市的普雷格爾河，河中有兩個島，由七座橋相連（如圖1.1中（a）所示）.當(dāng)時一直有一個難題困擾著人們：一個人怎么樣不重復(fù)的走完七座橋，最后回到出發(fā)地點？這就是所謂的哥尼斯堡七橋問題. （a) (b) 圖1.1很長時間沒有人能解決這個問題.1736年，瑞士數(shù)學(xué)家歐拉發(fā)表論文，他用4個點分別表示兩個島和兩岸，用連接兩點的線段表示橋，如圖1.1（b).即用到了圖論中所涉及的歐拉圖.哥尼斯堡七橋問題就是要求在這個圖中走一條歐拉回路.歐拉在這篇論文中證明了定理1.1即無向圖是歐拉圖當(dāng)且僅當(dāng)是連通圖且沒有奇度頂點.由于圖（b）中4個頂點均是奇度頂點，所以哥尼斯堡七橋問題無解.歐拉當(dāng)時發(fā)表的論文現(xiàn)在被公認(rèn)為是第一篇關(guān)于圖論的論文.這也正是歐拉回路和歐拉圖名字的由來.而哥尼斯堡七橋問題中所涉及的歐拉圖知識即是圖論知識在實際生活中的應(yīng)用.例2 哈密頓圖的實際應(yīng)用現(xiàn)有個人，已知他們其中的任意兩個人合起來認(rèn)識其余的個人.證明： （1）當(dāng)時，這個人能站成一列使得其中任何兩個相鄰的人都互相能認(rèn)識. （2）當(dāng)時，這個人能站成一個圈使得其中任何兩個相鄰的人都互相能認(rèn)識. 證 做階無向簡單圖，且與認(rèn)識.由已知條件可知，均有 下面討論與是否認(rèn)識. （1）若與認(rèn)識，則由知 （2）若與不認(rèn)識，則對任意的，與必與都認(rèn)識.否則，假如與不認(rèn)識，則與和都不認(rèn)識，所以與合起來至多認(rèn)識其余的個人，這與已知條件矛盾.因而 當(dāng)時，有 于是，當(dāng)時，由，與式（根據(jù)定理2.2）中存在哈密頓通路，所有的人按在通路中的順序排成一列，滿足要求.當(dāng)時，有 所以由，與式（根據(jù)定理2.2的推論）中存在哈密頓回路，所有的人按在回路中的順序站成一圈滿足要求. 此應(yīng)用中主要根據(jù)哈密頓通路與回路解決實際中的交流問題，使我們更深刻的了解圖論知識在日常生活中的作用.例3 教師如何分配課時問題某高中一年級有5個班，由4位老師為他們講課，周二每位老師為每個班上課的課時如表3.1所示，問此年級周二至少要安排多少節(jié)課？需要多少個教室？ 表3.1 1班 2班 3班 4班 5班 1 0 1 0 0 1 0 1 1 0 0 1 1 1 1 0 1 0 1 2 解 做二部圖，其中表示所有4為教師.，分別表示每個班級.，在與之間連條邊，每一條邊代