利用圖論知識(shí)解決實(shí)際問(wèn)題.docVIP

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