圖論的發(fā)展及其在現(xiàn)實(shí)生活中的幾個(gè)應(yīng)用

《圖論的發(fā)展及其在現(xiàn)實(shí)生活中的幾個(gè)應(yīng)用》由會(huì)員分享，可在線閱讀，更多相關(guān)《圖論的發(fā)展及其在現(xiàn)實(shí)生活中的幾個(gè)應(yīng)用（20頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

菏澤學(xué)院本科生畢業(yè)設(shè)計(jì)（論文） 圖論的發(fā)展及其在生活中的應(yīng)用 數(shù)學(xué)與應(yīng)用數(shù)學(xué) 張佳麗 指導(dǎo)教師 劉秀麗 摘要 主要介紹了圖論的起源與發(fā)展及其生活中的若干應(yīng)用，如：渡河問題、旅游推銷員問題、最小生成樹問題、四色問題、安排問題、中國郵遞員問題。同時(shí)也涉及到了幾種在圖論中應(yīng)用比較廣泛的方法，如：最鄰近法、求最小生成樹的方法、求最優(yōu)路線的方法等。 關(guān)鍵詞 圖論 生活 問題 應(yīng)用 Graph Theory Development and the Application in Life Mathematics and applied mathematics Zhang Jiali Tutor Liu Xiuli Abstract This paper mainly introduces the origin and development of graph theory and its several applications in our life, such as: crossing river problem, traveling salesman problem, minimum spanning tree problem, four color problem，arrangement problem，Chinese postman problem．It also researches several methods that are more widely applied in graph theory, for example: the method of most neighboring, the method of solving the minimum spanning tree，the method of the best route，and so on． Key words graph theory life problem application 引言 圖論是一門古老的學(xué)科，是數(shù)學(xué)中有廣泛應(yīng)用的一個(gè)分支，與其他的數(shù)學(xué)分支，如群論、矩陣論、概率論、拓?fù)鋵W(xué)、數(shù)分析等有著密切的聯(lián)系．圖論中以圖為研究對象，圖形中我們用點(diǎn)表示對象，兩點(diǎn)之間的連線表示對象之間的某種特定的關(guān)系．事實(shí)上，任何一個(gè)包含了二元關(guān)系的系統(tǒng)都可以用圖論來模擬．而且,圖論能把紛雜的信息變的有序、直觀、清晰．由于我們感興趣的是兩對象之間是否有某種特定關(guān)系，所以圖形中兩點(diǎn)間連接與否尤為重要，而圖形的位置、大小、形狀及連接線的曲直長短則無關(guān)緊要． 圖論在自然科學(xué)、社會(huì)科學(xué)等各個(gè)領(lǐng)域都有廣泛的應(yīng)用．隨著科學(xué)的發(fā)展，以及生產(chǎn)管理、軍事、交通運(yùn)輸?shù)确矫嫣岢隽舜罅繉?shí)際的需要，圖論的理論及其應(yīng)用研究得到飛速發(fā)展。從20世紀(jì)50年代以后，由于計(jì)算機(jī)的迅速發(fā)展，有力地推動(dòng)了圖論的發(fā)展，加速了圖論向各個(gè)學(xué)科的滲透，尤其是網(wǎng)絡(luò)理論的建立，圖論與線性規(guī)劃、動(dòng)態(tài)規(guī)劃等優(yōu)化理論和方法互相滲透。同時(shí)，計(jì)算機(jī)的發(fā)展使圖論成為數(shù)學(xué)領(lǐng)域中發(fā)展最快的分支之一． 1 圖論的起源與發(fā)展 1．1 圖論的起源[1] 1736年是圖論的歷史元年．這一年，歐拉（L?Euler）研究了哥尼斯堡（Knigsberg）七橋問題，并發(fā)表了關(guān)于圖論的首篇文章．歐拉也因此被稱為圖論之父．哥尼斯堡城瀕臨藍(lán)色的波羅的海，城中有一條普萊格爾（Pregel）河，河的兩條支流在這里匯合，然后橫穿全城，流入大海．河水把城市分成4塊，于是，人們建造了7座各具特色的橋，把哥尼斯堡城連成一體，如圖一所示． 早在18世紀(jì)，這些形態(tài)各異的小橋吸引了眾多的游客，他們在陶醉于美麗風(fēng)光的同時(shí)，不知不覺間，腳下的橋觸發(fā)了人們的靈感，一個(gè)有趣的問題在居民中傳開． 圖一 圖二 誰能夠從兩岸A，B， C，D四個(gè)陸地中的任一個(gè)地方出發(fā)一次走遍所有的7座橋，而且每座橋都無重復(fù)的只通過一次？這個(gè)問題看起來似乎不難，誰都樂意用這個(gè)問題來測試一下自己的智力．但是，誰也沒有找到一條這樣的路線．這個(gè)問題極大的刺激了人們的好奇心，許多人都熱衷于解決這個(gè)問題，然而始終沒有人能夠成功．“七橋問題” 難住了哥尼斯堡城的所有居民．哥尼斯堡城也因“七橋問題” 而出了名．這就是數(shù)學(xué)史上著名的七橋問題． 問題看來并不復(fù)雜，但就是誰也解決不了，也說不出所以然來．1736年，當(dāng)時(shí)著名的數(shù)學(xué)家歐拉仔細(xì)研究了這個(gè)問題，他將上述四塊陸地與七座橋間的關(guān)系用一個(gè)抽象圖形來描述(見圖二)，其中A、B、C、D四個(gè)陸地分別用四個(gè)點(diǎn)來表示，而陸地之間有橋相連者則用連接兩個(gè)點(diǎn)的連線來表示，這樣，上述的哥尼斯堡七橋問題就變成了由點(diǎn)和邊所組成的如下問題： 試求從圖中的任一點(diǎn)出發(fā)，不重復(fù)的通過每條邊一次，最后返回到該點(diǎn)，這樣的路線是否存在？這樣問題就變得簡潔明了了，同時(shí)問題也變得更一般、更深刻了．這樣，七橋問題就轉(zhuǎn)變?yōu)閳D論中的一筆畫問題．即能不能不重復(fù)的一筆畫出圖二中的這個(gè)圖形． 原先人們是要求找出一條不重復(fù)的路線，歐拉想，既然成千上萬的人都失敗了，那么這樣的路線也許根本就不存在．于是，歐拉就想：這樣不重復(fù)的路線究竟存不存在？由于改變了一下提問的角度，歐拉抓住了問題的實(shí)質(zhì)．最后，歐拉認(rèn)真考慮了一筆畫圖形的結(jié)構(gòu)特征． 歐拉發(fā)現(xiàn)，凡是能用一筆畫成的圖形，都有這樣一個(gè)特點(diǎn)：每當(dāng)畫一條線進(jìn)入中間的一個(gè)點(diǎn)時(shí)，還必須畫一條線離開這個(gè)點(diǎn)．否則，這個(gè)圖形就不可能用一筆畫出．也就是說，單獨(dú)考察圖中的任何一點(diǎn)（起點(diǎn)和終點(diǎn)除外），這個(gè)點(diǎn)都應(yīng)該與偶數(shù)條線相連；如果起點(diǎn)與終點(diǎn)重合，那么，連這個(gè)點(diǎn)也應(yīng)該與偶數(shù)條線相連． 在七橋問題的幾何圖中，A、B、D三點(diǎn)分別與3條線相連，C點(diǎn)與5條線相連．連線數(shù)都是奇數(shù)條．因此，歐拉斷定：一筆畫出這個(gè)圖形是不可能的．也就是說，不重復(fù)地通過7座橋的路線是根本不存在的！天才的歐拉只用了一步就證明了這個(gè)難題，從這里我們也可以看到圖論的強(qiáng)大威力. 歐拉對七橋問題的研究，是拓?fù)鋵W(xué)研究的先聲． 1750年，歐拉又發(fā)現(xiàn)了一個(gè)有趣的的現(xiàn)象．歐拉因此得到了后人以他的名字命名的“多面體歐拉公式”．正4面體有4個(gè)頂點(diǎn)、6條棱，它的面數(shù)加頂點(diǎn)數(shù)減去棱數(shù)等于2；正6面體有8個(gè)頂點(diǎn)、12條棱，它的面數(shù)加頂點(diǎn)數(shù)減去棱數(shù)也等于2．接著，歐拉又考察了正12面體、正24面體，發(fā)現(xiàn)都有相同的結(jié)論．于是繼續(xù)深入研究這個(gè)問題，終于發(fā)現(xiàn)了一個(gè)著名的定理： (面數(shù)) ＋ (頂點(diǎn)數(shù)) －(棱數(shù)) ＝2 這個(gè)公式證明了多面體只有正四面體、正六面體、正八面體、正十二面體、正二十面體五種．這個(gè)定理成為拓?fù)鋵W(xué)的第一個(gè)定理，這個(gè)公式被認(rèn)為開啟了數(shù)學(xué)史上新的一頁，促成了拓?fù)鋵W(xué)的發(fā)展． 1．2 圖論的發(fā)展 圖論的產(chǎn)生和發(fā)展經(jīng)歷了二百多年的歷史，大體上可以分為三個(gè)階段： 第一階段是從1736年到19世紀(jì)中葉．當(dāng)時(shí)的圖論問題是盛行的迷宮問題和游戲問題．最具代表性的工作是著名數(shù)學(xué)家歐拉于1736年解決的哥尼斯堡七橋問題(見1．1)． 第二階段是從19世紀(jì)中葉到1936年．圖論主要研究一些游戲問題:迷宮問題、博弈問題、棋盤上馬的行走路線問題等，[2]隨著對這些問題的深入研究，圖論又產(chǎn)生了新的一系列問題，例如：連通性、嵌入問題、染色問題、矩陣表示以及網(wǎng)絡(luò)流等．連通性是圖論研究的基本問題之一，歐拉路、中國郵路問題、哈密頓問題、樹與圖的支撐樹、匹配問題都是連通性的典型問題；地圖著色問題即是對無論多么復(fù)雜的地圖，只需用四種顏色就足夠?qū)⑾噜彽膮^(qū)域分開．平面圖的染色問題是與四色問題緊密相聯(lián)的．于是產(chǎn)生了著色問題即給定一個(gè)圖，如果要求把所有頂點(diǎn)涂上顏色，使得相鄰頂點(diǎn)具有不同的顏色，問最少需要幾種不同的顏色?這個(gè)問題叫做圖的點(diǎn)著色問題．如果對給定圖的全部邊都涂上顏色，使相鄰的邊有不同的顏色，問至少需要幾種顏色?這個(gè)問題叫做邊的著色問題，邊的著色問題可以轉(zhuǎn)化為點(diǎn)著色問題．由這些問題人們逐漸豐富并發(fā)展了圖論學(xué)科知識．同時(shí)出現(xiàn)了以圖為工具去解決其他領(lǐng)域中一些問題的成果．1847年德國的克?；舴?qū)涞母拍詈屠碚搼?yīng)用于工程技術(shù)的電網(wǎng)路方程組的研究．1936年匈牙利的數(shù)學(xué)家哥尼格寫出了第一本圖論專著《有限圖與無限圖的理論》．標(biāo)志著圖論成為了一門獨(dú)立學(xué)科． 第三階段是1936年以后.由于生產(chǎn)管理、軍事、交通運(yùn)輸、計(jì)算機(jī)和通訊網(wǎng)路等方面大量實(shí)際問題的出現(xiàn)，大大促進(jìn)了圖論的發(fā)展．特別是電子計(jì)算機(jī)的大量應(yīng)用，使大規(guī)模問題的求解成為可能．實(shí)際問題如電網(wǎng)絡(luò)、交通網(wǎng)絡(luò)、電路設(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu)以及社會(huì)科學(xué)中的問題所涉及到的圖形都很復(fù)雜的，需要計(jì)算機(jī)的幫助才有可能進(jìn)行分析和解決．目前，圖論在物理、化學(xué)、運(yùn)籌學(xué)、計(jì)算機(jī)科學(xué)、電子學(xué)、信息論、控制論、網(wǎng)絡(luò)理論、社會(huì)科學(xué)及經(jīng)濟(jì)管理等幾乎所有學(xué)科領(lǐng)域中都有應(yīng)用． 2 圖論在生活中幾種應(yīng)用 2．1 渡河問題 2．1．1 基本理論 定義2.1[3] 有向圖：一個(gè)有向圖是一個(gè)有序的二元組，記作，其中 （1）稱為頂點(diǎn)集，其元素稱為頂點(diǎn)或結(jié)點(diǎn)． （2）為邊集，它是笛卡爾積的多重子集，其元素稱為有向邊，簡稱邊． 2．1．2 應(yīng)用舉例 例[4] （渡河問題） 一個(gè)擺渡人要把一只狼，一只羊和一捆菜運(yùn)過河去，由于船很小，每次擺渡人至多只能帶一樣?xùn)|西．另外，如果人不在旁時(shí)，狼就要吃羊，羊就要吃菜．問這個(gè)人怎樣才能安全的將它們運(yùn)過河去？ 解 用表示擺渡人，表示狼，表示羊，表示菜 若用表示人和其他三樣?xùn)|西在河的原岸的狀態(tài)，這樣原岸全部可能出現(xiàn)的狀態(tài)為以下16種： 表示原岸什么也沒有，即人、狼、羊、菜都運(yùn)到河對岸了 根據(jù)題意，我們知道這16種情況中有6種是不允許的，它們是、、、、、，如表示人和菜在原岸而狼和羊在對岸，這當(dāng)然是不允許的．因此，允許出現(xiàn)的情況只有10種．以這10種狀態(tài)為結(jié)點(diǎn)，以擺渡前原岸的一種狀態(tài)與擺渡一次后出現(xiàn)在原岸的狀態(tài)所對應(yīng)的結(jié)點(diǎn)之間的連線為邊，作有向圖2.1： 圖2.1 上圖給出了兩種方案，方案為上圖中從到的不同的基本通路： ⑴ ⑵． 它們的長度均為7故擺渡人只需擺渡7次就能將它們?nèi)窟\(yùn)到對岸，并且羊和菜完好無損． 2．2 旅行推銷員問題 該問題是說：“給定個(gè)城市和它們之間的距離，問如何設(shè)計(jì)一條路線，使得一個(gè)推銷員從他所在的城市出發(fā)途經(jīng)其余個(gè)城市剛好一次，最后回到原駐地并使得行程最短[5]？” 2．2．1 基本理論 定義2.2[6] 給定圖（為無向圖或有向圖），設(shè)：（為實(shí)數(shù)集），對中任意的邊 ( 為有向圖時(shí)，)，設(shè)，稱實(shí)數(shù)為邊上的權(quán)，并將標(biāo)注在邊上，稱為帶權(quán)圖，此時(shí)常將帶權(quán)圖記作．設(shè)，稱為的權(quán)，記作，即=． 最鄰近法[7] (1)由任意選擇的結(jié)點(diǎn)開始，找與該點(diǎn)最近（即權(quán)最?。┑狞c(diǎn)，形成有一條邊的初始路徑． (2)設(shè)表示最新加到這條路上的結(jié)點(diǎn)，從不在路上的所有結(jié)點(diǎn)中選一個(gè)與最靠近的結(jié)點(diǎn)，把連接與這一結(jié)點(diǎn)的邊加到這條路上，重復(fù)這一步，直到中所有結(jié)點(diǎn)包含在路上． (3)將連接起始點(diǎn)與最后加入的結(jié)點(diǎn)之間的邊加到這條路上，就得到一個(gè)圈，即為問題的近似解． 2．2．2 應(yīng)用舉例 例[8] 某流動(dòng)售票員居住在城，為推銷貨物他要訪問、、城后返回城，若該四城間的距離如下圖2.2所示，找出完成該訪問的最短路線． 圖2.2 解 步驟如下圖①—④ ① ② ③ ④ 最短距離為：8+6+7+11=32． 2．3 最小生成樹 2．3．1 基本理論 定義2.3.1[9] 設(shè)，為兩個(gè)圖（同為無向圖或同為有向圖），若且，則稱是的子圖，為的母圖，記作．又若或，則稱為的真子圖，若，則稱為的生成子圖． 定義2.3.2[10] 不含圈的連通圖稱為樹． 定義2.3.3[11] 如果是的一個(gè)生成子圖而且又是一棵樹，則稱是圖的一棵生樹． 定義2.3.4[12] 設(shè)無向連通帶權(quán)圖，是的一棵生成樹，的各邊權(quán)之和稱為的權(quán)．的所有生成樹中，權(quán)最小的生成樹稱為的最小生成樹． ⑴破圈法[13] 在中任取一個(gè)圈，去掉其中一條邊，然后再取一個(gè)圈，再去掉這個(gè)圈中的一條邊，如此繼續(xù)下去，最后得到的連通圖的無圈的生成子圖就是的一棵生成樹． ⑵用破圈法求帶權(quán)的最小生成樹的方法 在賦權(quán)圖中任取一個(gè)圈，然后去掉這個(gè)圈中權(quán)最大的邊，如此繼續(xù)進(jìn)行直到中不再有圈時(shí)為止，這時(shí)剩下的邊組成的子圖就是最小樹．[14] 2．3．2 應(yīng)用舉例 旅游線路中的最短問題 對于旅客來說，要求在最短的時(shí)間內(nèi)用最少的錢來旅游最多的景點(diǎn)，考慮到無論采取哪種方案，在門票的花費(fèi)均相同且路費(fèi)在速度恒定的情況下可由路程的多少來求得，從而把問題轉(zhuǎn)化為求最短的旅游路線的問題．[15] 例[16] 公園的路徑系統(tǒng)圖如圖2.3，其中為入口，為出口，，，，，為五個(gè)景點(diǎn)，現(xiàn)求如何能使觀光旅游車從入口到出口所經(jīng)過的距離最短． 圖2.3 解 用破圈法求帶權(quán)的最小生成樹的方法求解，求解步驟如下圖①—⑥ ① ② ③ ④ ⑤ ⑥ 由圖可知，從如口到出口的最短路徑為 最短距離為：2+2+3+1+5=13． 2．4 四色問題 1852年10月23日英國數(shù)學(xué)家德?摩根寫給當(dāng)時(shí)還屬于英國的愛爾蘭數(shù)學(xué)家哈密爾頓的一封信中，他寫道：“我的一位學(xué)生今天請我解釋一個(gè)我過去不知道，現(xiàn)在仍不甚了了的事實(shí)．他說任意劃分一個(gè)地圖并給各部分著上顏色，使任何具有公共邊界的部分顏色不同，那么需要且僅需要四種顏色就夠了．”德?摩根提到的這位學(xué)生名叫弗雷德里克?格里斯．而據(jù)他后來撰文披露，該問題的真正發(fā)現(xiàn)者實(shí)際是他是的哥哥弗蘭西斯?格里斯．[17] 2.4.1 基本理論 定義2.4.1[18] 設(shè)為無向標(biāo)定圖，中的頂點(diǎn)與邊的交替序列 …稱為到的通路，其中，為的端點(diǎn)，=1,2, …， ，分別稱為的始點(diǎn)與終點(diǎn)，中邊的條數(shù)稱為它的長度，若 =，則稱通路為回路．若的所有邊各異，則稱為簡單通路，又若=，則稱為簡單回路．若的所有頂點(diǎn)（除 與可能相同外）各異，所有邊也各異，則稱為初級通路或路徑，此時(shí)又若=，則稱為初級回路或圈，將長度為奇數(shù)的圈稱為奇圈，長度為偶數(shù)的圈稱為偶圈． 定義2.4.2[19] 對無環(huán)圖的每個(gè)頂點(diǎn)涂上一種顏色，使相鄰的頂點(diǎn)涂不同的顏色，稱為對圖的一種著色．若能用種顏色給的頂點(diǎn)著色，就稱對進(jìn)行了著色，也稱是—可著色的．若是—可著色的，但不是—可著色的，就稱是色圖，并稱這樣的為的色數(shù)，記作． 定義2.4.3[20] 在（4）邊形內(nèi)放置一個(gè)頂點(diǎn)，使這個(gè)頂點(diǎn)與上的所有頂點(diǎn)均相鄰，所得階簡單圖稱為階輪圖．為奇數(shù)的輪圖稱為奇階輪圖，為偶數(shù)的輪圖稱為偶階輪圖． 定理2.4.1（四色定理）[21] 每個(gè)平面的色數(shù)至多是4． 定理2.4.2[19] 奇圈和奇階輪圖的色數(shù)均為3，而偶階輪圖的色數(shù)為4． 2．4．2 應(yīng)用舉例 例1[22] 在期末考試周期間，一所學(xué)院的8名選修數(shù)學(xué)的學(xué)生得到許可去參加大學(xué)生科研討論會(huì)．假設(shè)他們回來之后需要在星期一對所錯(cuò)過的考試進(jìn)行補(bǔ)考，星期一安排這些考試的可能時(shí)間段為： ⑴8:00——10:00 ⑵10:15——12:15 ⑶12:30——2:30 ⑷2:45——4:45 ⑸5:00——7:00 ⑹7:15——9:15 應(yīng)用圖論的相關(guān)知識，確定這8名學(xué)生完成考試的最早時(shí)間．要求：如果有某個(gè)學(xué)生必須要參加某兩門課的考試，那么，這兩門課程就不能安排在同一時(shí)間段內(nèi)．這8名學(xué)生以及他們選修的課程：高等微積分（）、微分方程（）、幾何學(xué)（）、圖論（）、線性規(guī)劃（）、近世代數(shù)（）、統(tǒng)計(jì)學(xué)（）、拓?fù)鋵W(xué)（），列表如下： ：，， ：，， ：，， ：，， ：，， ：，， ：，， ：，， 解 首先構(gòu)造圖2.4.1，其頂點(diǎn)為這8門課程，如果有某個(gè)學(xué)生同時(shí)考兩門課程則在這兩個(gè)頂點(diǎn)間連一條邊．1、2、3、4表示四種不同的顏色，如1表示用第一種顏色著色． 記最小的時(shí)間段數(shù)為，由于中含有奇圈，，，，，，由定理2知，需要3種顏色為該圖上的頂點(diǎn)著色．由于與該圖上的所有頂點(diǎn)都鄰接，所以需要用第四種顏色來為染色．因此≥4；又由定理1知≤4，因而＝4． 圖2.4.1 故在四個(gè)時(shí)間段內(nèi)可安排這8門課程的考試，安排方法為： 時(shí)間段1：統(tǒng)計(jì)學(xué)、幾何學(xué)、圖論 時(shí)間段2：高等微積分、拓?fù)鋵W(xué) 時(shí)間段3：微分方程、近世代數(shù) 時(shí)間段4：線性規(guī)劃 故可在安排時(shí)間段(1) 8:00—10:00 (2) 10:15—12:15 (3) 12:30—2：30 (4) 2:45—4:45 故完成考試的最短時(shí)間為4:45． 例2[22] 有8種化學(xué)藥品需要空運(yùn)飛越整個(gè)國家.運(yùn)費(fèi)根據(jù)運(yùn)送的容器數(shù)量來確定.運(yùn)送一個(gè)容器需要125元.某些藥品之間可以發(fā)生化學(xué)反應(yīng),所以把它們放在同一個(gè)容器中是很危險(xiǎn)的.這些化學(xué)藥品被標(biāo)記成,,,,,, ,.下面列出的是與某個(gè)給定藥品能夠發(fā)生反應(yīng)的其他藥品名稱: :,, : ,,, : ,, : ,,, : ,,,, : ,,, : ,,,, : ,,, 這些化學(xué)藥品應(yīng)該如何放置于那些容器中使得運(yùn)送這些化學(xué)藥品所需的費(fèi)用最少?最少是多少? 解 首先構(gòu)造圖2.4.2,其頂點(diǎn)為這8種化學(xué)藥品.如果某兩種藥品能發(fā)生化學(xué)反應(yīng)就在這兩個(gè)頂點(diǎn)間連一條邊.1，2，3，4表示四種不同的顏色，如1表示用第一種顏色著色． 記最小的容器數(shù)為，由于中含有奇圈,,,，,由定理2知，需要3種顏色為該圖上的頂點(diǎn)著色．由于與該圖上的所有頂點(diǎn)都鄰接，所以需要用第四種顏色來為染色．因此≥4；又由定理1知≤4，因而＝4． 圖2.4.2 故將這8種化學(xué)藥品放置在四個(gè)容器內(nèi),安排方法為： 第一個(gè)容器: , 第二個(gè)容器: , 第三個(gè)容器: , 第四個(gè)容器: , 最少費(fèi)用為4125＝500. 2．5 用邊染色解決安排問題 2.5.1 基本理論 定義2.5.1[23] 非空圖的一個(gè)邊染色是指給的邊分配顏色，每條邊分配一種顏色，使得鄰接的邊分配不同的顏色．對的邊染色所需的最少顏色數(shù)稱為是邊色數(shù)，記為．應(yīng)用種顏色的邊染色稱為是邊染色． 定義2.5.2[24] 設(shè)為一無向圖，，稱作為邊的端點(diǎn)次數(shù)之和為的度數(shù)，簡記為度，記作，在不發(fā)生混淆時(shí)，簡記為． 定理2.5.1[23] 對于任意非空圖， ＝或者． 定理2.5.2[23] 設(shè)是一個(gè)階為，邊數(shù)為的圖．若 則． 2.5.2 應(yīng)用舉例 例1[23] ()曾邀請3對夫婦到他的避暑別墅住一個(gè)星期,他們是 ()和 (), ()和 (), ()和 ()．由于這6位客人都喜歡網(wǎng)球運(yùn)動(dòng),所以他決定進(jìn)行一些網(wǎng)球比賽．6位客人中的每一位都要與其配偶之外的每位客人比賽．另外, 將分別與, , , 進(jìn)行一場比賽．若沒有人在同一天進(jìn)行兩場比賽,則要在最少天數(shù)完成比賽,該如何安排? 解 首先構(gòu)造圖2.5.1,其頂點(diǎn)為住在的避暑別墅的人,因此, 中的兩個(gè)頂點(diǎn)是鄰接的,如果這兩個(gè)頂點(diǎn)(人)需要進(jìn)行一場比賽．為了解答這個(gè)問題,我們需要確定的邊色數(shù)． 圖2.5.1 易見, ．根據(jù)定理2．5．1, 或者．此外, 的階為,邊數(shù)為．由于 由定理2．5．2,可知．圖列出了的一個(gè)6邊染色,從而也給出了一個(gè)具有最少天數(shù)(6)的時(shí)間安排表． 第一天: — — — 第二天: — — — 第三天: — — — 第四天: — — — 第五天: — — 第六天: — — 例2[25]　來自亞特蘭大、波士頓、芝加哥、丹佛、路易維爾、邁阿密以及納什維爾的7支壘球隊(duì)受邀請參加比賽，其中每只隊(duì)都被安排與一些其他隊(duì)比賽，如下： 亞特蘭大（）：波士頓，芝加哥，邁阿密，納什維爾 波士頓（）：亞特蘭大，芝加哥，納什維爾 芝加哥（）：亞特蘭大，波士頓，丹佛，路易維爾 丹佛()：芝加哥，路易維爾，邁阿密，納什維爾 路易維爾()：芝加哥，丹佛，邁阿密 邁阿密()：亞特蘭大，丹佛，路易維爾，納什維爾 納什維爾()：亞特蘭大，波士頓，丹佛，邁阿密 每支隊(duì)在同一天最多只能進(jìn)行一場比賽。建立一個(gè)具有最少天數(shù)的比賽時(shí)間表. 解 首先構(gòu)造圖2.5.2,其頂點(diǎn)為7支球隊(duì),因此, 中的兩個(gè)頂點(diǎn)是鄰接的,如果這兩個(gè)頂點(diǎn)需要進(jìn)行一場比賽．為了解答這個(gè)問題,我們需要確定的邊色數(shù)． 圖2.5.2 易見, ．根據(jù)定理2．5．1, 或者．此外, 的階為,邊數(shù)為．由于 由定理2．5．2,可知．圖列出了的一個(gè)5邊染色,從而也給出了一個(gè)具有最少天數(shù)(5)的時(shí)間安排表． 第一天：　亞特蘭大－波士頓　　納什維爾－邁阿密　　芝加哥－路易維爾 第二天：　波士頓－納什維爾　　亞特蘭大－芝加哥　　丹佛－路易維爾 第三天：　亞特蘭大－邁阿密　　芝加哥－波士頓　　　丹佛－納什維爾 第四天：　芝加哥－丹佛　　　　路易維爾－邁阿密　　亞特蘭大－納什維爾 第五天：　丹佛－邁阿密 2.6 中國郵遞員問題 中國郵遞員問題即為郵遞員路線問題．郵遞員從郵局出發(fā),經(jīng)過他所投遞范圍的每一條街道至少一次,完成郵件的投遞任務(wù)以后返回郵局．如何安排郵遞員的行走路線,以使總路程最短,這個(gè)問題是中國學(xué)者管梅谷1962年首先提出,并給出了一個(gè)解法,被國際上稱為中國郵遞員問題． 2.6.1 基本理論 定義2.6.1[26] 在圖上,從某個(gè)頂點(diǎn)出發(fā),對各條邊只通過一次,這樣的跡稱為跡．閉跡叫做環(huán)游．一個(gè)圖若包含環(huán)游,則這個(gè)圖稱為圖． 定義2.6.2[27] 將邊的兩個(gè)端點(diǎn)再用一條權(quán)同樣為的新邊連接，即得重復(fù)邊． 定理2.6.1 [27] 若是圖，則中任意用Fleury算法做出的跡都是上午環(huán)游． 定理2.6.2[27]　 設(shè)賦權(quán)圖經(jīng)添加重復(fù)邊集后得到賦權(quán)歐拉圖，重復(fù)邊集權(quán)值總和最小的充要條件是：每條邊最多重復(fù)一次，并且中任一個(gè)圈，其所含重復(fù)邊的權(quán)值之和都不大于所在圈中所有邊權(quán)值的二分之一． 算法[27] : (1) 任意選取一個(gè)頂點(diǎn),置； (2) 假設(shè)跡已經(jīng)選定，那么按下述方法從中選取邊： 1）和相關(guān)聯(lián)； 2）除非沒有別的邊可選擇，否則不是的割邊． (3)當(dāng)2）不能再執(zhí)行時(shí)，算法停止，得到中一條跡． 非圖求最優(yōu)環(huán)游的算法步驟[27] ： (1)開始．任給一個(gè)初始方案，使非賦權(quán)圖各頂點(diǎn)變?yōu)榕键c(diǎn)，得到一個(gè)初始賦權(quán)圖； (2)檢查．檢查各圈是否滿足圈中“重復(fù)邊總權(quán)值小于等于非重復(fù)邊總權(quán)值”的最優(yōu)解條件．若條件已滿足，則現(xiàn)行方案為最優(yōu)解，再由算法得到一條最優(yōu)環(huán)游，否則轉(zhuǎn)（3）； (3)調(diào)整．調(diào)整重復(fù)邊并保持圖仍為賦權(quán)圖．轉(zhuǎn)（2）． 2．6．2　應(yīng)用舉例 例[28] 設(shè)郵遞員所轄的投遞區(qū)如下圖2.6所示，其中邊旁的數(shù)字為街道長度，問從郵局出發(fā)，如何走遍全區(qū)各街最后回到郵局而又最短的路徑． 圖2.6 解 ，故此圖為非歐拉圖．添加重復(fù)邊使其變?yōu)闅W拉圖，如下圖2.6.1，　經(jīng)檢查所有圈皆符合定理2．6．2，故下圖為最優(yōu)方案． 圖2.6.1 按算法可得到一條最優(yōu)環(huán)游,這條最優(yōu)環(huán)游是: . 參考文獻(xiàn) [1]李冰．圖論的起源和發(fā)展[J]．大眾文藝，2010（9）：34． [2]黃會(huì)蕓．圖論思想在生活中的運(yùn)用[J]．赤峰學(xué)院學(xué)報(bào)（自然科學(xué)版），2009,25(12):23-24． [3]耿素云、屈婉玲．離散數(shù)學(xué)[M]．2版．北京：高等教育出版社，2004:267． [4]傅彥．離散數(shù)學(xué)基礎(chǔ)及應(yīng)用[M]．成都：電子科技大學(xué)出版社，2000：149—150． [5]程釗．圖論中若干著名問題的歷史標(biāo)記[J]．?dāng)?shù)學(xué)的實(shí)踐與認(rèn)識，2009，39（24）：75． [6]耿素云、屈婉玲．離散數(shù)學(xué)[M]．2版．北京：高等教育出版社，2004:302． [7]喬維聲、湯惟．離散數(shù)學(xué)[M]．西安：西安電子科技大學(xué)出版社，2005:157． [8]喬維聲、湯惟． 離散數(shù)學(xué)[M]．西安：西安電子科技大學(xué)出版社，2005:158． [9]耿素云、屈婉玲．離散數(shù)學(xué)[M]．2版．北京：高等教育出版社，2004:274． [10]王朝瑞．圖論[M]．3版．北京：北京理工大學(xué)出版社，2002:26． [11]王朝瑞．圖論[M]．3版．北京：北京理工大學(xué)出版社，2002:33． [12]耿素云、屈婉玲．離散數(shù)學(xué)[M]．2版．北京：高等教育出版社，2004:311． [13]王朝瑞．圖論[M]．3版．北京：北京理工大學(xué)出版社，2002:34． [14]王朝瑞．圖論[M]．3版．北京：北京理工大學(xué)出版社，2002:232． [15]方冬云．圖論在旅游路線選擇中的應(yīng)用[J]．長春工業(yè)大學(xué)學(xué)報(bào)（自然科學(xué)版），2009,30（5）：583． [16]劉海英．最短路徑問題在管理中的應(yīng)用[J]．福建廣播電視大學(xué)學(xué)報(bào),2010，4（29）：87． [17]程釗．圖論中若干著名問題的歷史標(biāo)記[J]．?dāng)?shù)學(xué)的實(shí)踐與認(rèn)識，2009，39（24）：78． [18]耿素云、屈婉玲．離散數(shù)學(xué)[M]．2版．北京：高等教育出版社，2004:276． [19]耿素云、屈婉玲．離散數(shù)學(xué)[M]．2版．北京：高等教育出版社，2004:333． [20耿素云、屈婉玲．離散數(shù)學(xué)[M]．2版．北京：高等教育出版社，2004:332． [21]Gary Chartrand、Ping Zhang．圖論導(dǎo)引[M]．范益政等，譯．北京：人民郵電出版社，2007：237． [22]Gary Chartrand、Ping Zhang．圖論導(dǎo)引[M]．范益政，朱明，龔世才等譯．北京：人民郵電出版社，2007：246－247． [23] Gary Chartrand、Ping Zhang．圖論導(dǎo)引[M]．范益政，朱明，龔世才等譯．北京：人民郵電出版社，2007：248—250． [24]耿素云、屈婉玲．離散數(shù)學(xué)[M]．2版．北京：高等教育出版社，2004:269． [25] Gary Chartrand、Ping Zhang．圖論導(dǎo)引[M]．范益政，朱明，龔世才等譯．北京：人民郵電出版社，2007：255. [26]劉纘武．應(yīng)用圖論[M]．長沙：國防科技大學(xué)出版社，2004：83． [27]劉纘武．應(yīng)用圖論[M]．長沙：國防科技大學(xué)出版社，2004：85—87． [28]劉纘武．應(yīng)用圖論[M]．長沙：國防科技大學(xué)出版社，2004：97． 致謝 在此論文撰寫過程中，要特別感謝我的導(dǎo)師劉秀麗老師的指導(dǎo)與督促。劉秀麗老師對該論文從選題，構(gòu)思到最后定稿的各個(gè)環(huán)節(jié)都給予細(xì)心指導(dǎo)和不懈的支持,使我得以最終完成畢業(yè)論文設(shè)計(jì)。 此外，本文最終得以順利完成，也是與數(shù)學(xué)系其他老師的幫助分不開的，雖然他們沒有直接參與我的論文指導(dǎo)，但在這個(gè)過程中卻給我提供了不少的意見，提出了一系列可行性的建議，在此向他們表示深深的感謝！ 最后再一次感謝所有在畢業(yè)設(shè)計(jì)中曾經(jīng)幫助過我的良師益友和同學(xué)，以及在設(shè)計(jì)中被我引用或參考的論著的作者。 19