數(shù)學建模中的圖論方法第1頁，課件共39頁，創(chuàng)作于2023年2月數(shù)學建模中的圖論方法1.引言2.圖論的基礎知識4.圖論的幾個實用算法5.其他問題3.綜合例題第2頁，課件共39頁，創(chuàng)作于2023年2月數(shù)學建模中的圖論方法----引言1.引言圖論是離散數(shù)學的重要組成部分，它對于自然科學、工程技術、經(jīng)濟管理和社會現(xiàn)象等諸多問題，能夠提供有力的數(shù)學模型加以解決，特別在國內外大學生數(shù)學建模競賽當中，有不少問題可以應用圖論模型解決。我們在此有針對性地把圖論的骨干概念和結論以及相關的有效算法做一簡要介紹，愿聽者增強圖論建模的意識和能力。第3頁，課件共39頁，創(chuàng)作于2023年2月數(shù)學建模中的圖論方法----引言圖論起源于18世紀。第一篇圖論論文是瑞士數(shù)學家歐拉于1736年發(fā)表的“哥尼斯堡的七座橋”。在哥尼斯堡有七座橋將普萊格爾河中的兩個島及島與河岸連結起來（如圖）。問題是：要從這四塊陸地中的任何一塊開始通過每一座橋正好一次，再回到起點。問題轉化為：從任一點出發(fā)一筆畫出七條線再回到起點。第4頁，課件共39頁，創(chuàng)作于2023年2月數(shù)學建模中的圖論方法----引言

注：圖論中的“圖”并不是通常意義下的幾何圖形或物體的形狀圖，而是以一種抽象的形式來表達一些確定的事物及其關系的一個數(shù)學系統(tǒng)。歐拉考察了一般一筆畫的結構特點，給出了一筆畫的一個判定法則：這個圖是連通的，且每個點都與偶數(shù)線相關聯(lián)，將這個判定法則應用于七橋問題，得到了“不可能走通”的結果，不但徹底解決了這個問題，而且開創(chuàng)了圖論研究的先河。第5頁，課件共39頁，創(chuàng)作于2023年2月數(shù)學建模中的圖論方法----圖論的基礎知識2.圖的基礎知識圖G是由非空結點集以及邊集所組成，記作。它的結點數(shù)稱為階。根據(jù)邊有無方向，圖分為有向圖和無向圖。有向圖的邊去掉方向后所得的圖稱為原有向圖的基礎圖(或底圖)。沒有自環(huán)或多重邊的圖稱簡單圖。有些實際問題抽象出來的圖，邊上往往帶有信息，在邊上附加一些數(shù)字來刻劃此邊，稱權，此時該圖稱加權圖。無向圖中與結點v相關聯(lián)的邊數(shù)稱為v的度數(shù)，記，有向圖中以v為起點或終點的邊數(shù)分別稱為v的出度和入度，記。握手定理：（1）無向圖中所有結點的度數(shù)之和等于邊數(shù)的兩倍。（2）有向圖中所有結點的出度(入度)之和等于邊數(shù)。推論：任何圖的奇結點必為偶數(shù)個。例如，一群人中，有奇數(shù)個朋友的人必為偶數(shù)個。第6頁，課件共39頁，創(chuàng)作于2023年2月數(shù)學建模中的圖論方法----圖論的基礎知識如果簡單無向圖的任兩個結點均鄰接，稱之為完全圖，n階完全圖記為，它的每個結點的度數(shù)等于,邊數(shù)等于。一個邊的序列(或點的序列)稱路徑，封閉的路徑稱回路。邊不重復的路徑稱簡單路徑，點不重復的路徑稱基本路徑。路徑所含邊的條數(shù)稱為路徑的長度。如果存在從結點u到v的路徑，則稱從u到v可達。如果u到v可達，則從u到v的路徑中長度最短的路徑稱為短程線（或測地線），它的長度稱為從u到v的距離,記為；如果u到v不可達，則記。如果無向圖G的任兩個結點都可達，則稱G為連通圖。第7頁，課件共39頁，創(chuàng)作于2023年2月數(shù)學建模中的圖論方法----圖論的基礎知識設n階圖的結點集，則n階方陣稱為G的鄰接矩陣，其中

表示以為起點、

為終點的邊的數(shù)目。

一個圖的鄰接矩陣完整地刻劃了圖中各結點間的鄰接關系。，如圖1，它們的鄰接矩陣分別為：v1v2v3v4第8頁，課件共39頁，創(chuàng)作于2023年2月數(shù)學建模中的圖論方法----圖論的基礎知識，連通無回路圖稱為樹。每個連通分支都是樹的無向圖稱為森林．在結點數(shù)確定的情況下，樹是連通圖中邊數(shù)最少的圖，也是無回路圖中邊數(shù)最多的圖．每個連通圖G至少有一個生成子圖是一棵樹，稱之為G的生成樹。顯然每個連通圖都有生成樹，而一般來說生成樹不唯一(而邊數(shù)是確定的)。如果G是一個加權連通圖，我們希望找一棵權之和最小的生成樹，稱為最小生成樹。定理：若樹的結點數(shù)為n，邊數(shù)為m，則m=n-1。第9頁，課件共39頁，創(chuàng)作于2023年2月數(shù)學建模中的圖論方法----圖論的基礎知識例設有6個城市，它們之間有輸油管道連通，其布置圖如圖(a)所示．戰(zhàn)爭期間，為了保衛(wèi)油管不被破壞，需派部隊看守，看守一段油管需一連士兵．為保證各城市間輸油暢通，最少需派幾連士兵？他們應駐于那些油管處？解：此問題即為尋找圖(a)的生成樹問題．由圖知，結點數(shù)為6，故其生成樹的邊數(shù)為5，即最少需派5連士兵看守．其看守地段可見圖(b)、(c)、(d)所畫之線段．第10頁，課件共39頁，創(chuàng)作于2023年2月數(shù)學建模中的圖論方法----圖論的基礎知識

如果圖G中具有一條經(jīng)過所有邊的簡單回路,稱歐拉回路,含歐拉回路的圖稱為歐拉圖；如果圖G中具有一條經(jīng)過所有邊的簡單(非回路)路徑,稱歐拉路。定理:(1)連通無向圖G是歐拉圖的充要條件是G的每個結點均為偶結點; (2)連通無向圖G含有歐拉路的充要條件是G恰有兩個奇結點,且歐拉路必始于一個奇結點而終止于另一個奇結點.第11頁，課件共39頁，創(chuàng)作于2023年2月數(shù)學建模中的圖論方法----圖論的基礎知識圖1的所有結點均為偶結點，故為歐拉圖，一條歐拉回路為：。圖2有2個奇結點，故不是歐拉圖，但有歐拉路：。（1）（2）第12頁，課件共39頁，創(chuàng)作于2023年2月數(shù)學建模中的圖論方法----圖論的基礎知識如左圖是某街道圖形。灑水車從A點出發(fā)執(zhí)行灑水任務。試問是否存在一條灑水路線，使灑水車通過所有街道且不重復而最后回到車庫B？（螞蟻比賽問題）如右圖所示，甲、乙兩只螞蟻分別位于結點處，并設圖中的邊長度相等。甲、乙進行比賽：從它們所在的結點出發(fā)，走過圖中的所有邊最后到達結點處。如果他們的速度相同，問誰先到達目的地？第13頁，課件共39頁，創(chuàng)作于2023年2月數(shù)學建模中的圖論方法----圖論的基礎知識哈密爾頓回路，起源于一個名叫“周游世界”的游戲，它是由英國數(shù)學家哈密爾頓（Hamilton）于1859年提出的。他用一個正十二面體的20個頂點代表20個大城市（圖(a)），這個正十二面體同構于一個平面圖（圖(b)）。要求沿著正十二面體的棱，從一個城市出發(fā)，經(jīng)過每個城市恰好一次，然后回到出發(fā)點。這個游戲曾風靡一時，它有若干個解。圖(b)給出了一個解。（a）（b）第14頁，課件共39頁，創(chuàng)作于2023年2月數(shù)學建模中的圖論方法----圖論的基礎知識如果圖G中具有一條經(jīng)過所有結點的基本回路（稱哈密爾頓回路），則稱為哈密爾頓圖。雖然哈密爾頓圖判定問題與歐拉圖判定問題同樣有意義，但遺憾的是至今為止還沒有找到一個判別它的充分必要條件，這是圖論中尚未解決的主要問題之一。第15頁，課件共39頁，創(chuàng)作于2023年2月數(shù)學建模中的圖論方法----圖論的基礎知識設無向圖，如果存在的一個分劃，使得G的每一條邊的兩個端點分屬

和

，則稱G為二部圖(或偶圖)。

和

稱為互補結點子集，此時可將G記為。設是二部圖，若，且M中任何兩條邊均不相鄰，則稱M是G的一個匹配；具有最大邊數(shù)的匹配稱為最大匹配；若最大匹配M滿足，則稱M是G的一個完備匹配，此時若，則稱M為V1到V2的一個完備匹配；若，則稱M是G的一個完美匹配．第16頁，課件共39頁，創(chuàng)作于2023年2月數(shù)學建模中的圖論方法----綜合例題例1證明任意六個人的集會上，總會有三人互相認識或者不認識．證明這是1947年匈牙利數(shù)學競賽出的一道試題，因為它很有趣且很重要，后來曾收錄到《美國數(shù)學月刊》及其它數(shù)學刊物上。這類問題可以轉化為圖論中的完全圖染色問題．把參加集會的人看作結點，作一個完全圖，如果兩個人認識，則兩結點間的連線涂上紅色，否則涂上藍色．問題轉化為：無論怎樣涂色，總可以找到紅或藍．3.綜合例題第17頁，課件共39頁，創(chuàng)作于2023年2月數(shù)學建模中的圖論方法----綜合例題例1證明任意六個人的集會上，總會有三人互相認識或者不認識．證明設六個結點為。從引出的邊有五條，而顏色只有紅藍兩種，由抽屜原理，至少有三條邊同色，不失一般性，假定有三條邊為紅色。（1）如果結點之間至少有一條紅邊，比如是紅邊，則得到紅色的三角形；（2）如果結點之間的邊全是藍色的，則得到藍色的三角形。關于問題中的結點數(shù)，對任何，命題都成立．但當時，命題便不成立了。這說明：不同的六個點是保證用兩色涂染其邊，存在同色三角形的最少點數(shù)。第18頁，課件共39頁，創(chuàng)作于2023年2月數(shù)學建模中的圖論方法----綜合例題例2

出席某次國際學術會議的有六個成員a,b,c,d,e,f，其中：a會講漢語、法語和日語；b會講德語、日語和俄語；c會講英語和法語；d會講漢語和西班牙語；e會講英語和德語；f會講俄語和西班牙語．如將此六人分成兩組，是否會發(fā)生同一組內的任意兩人不能互相直接交談的情況？abdfec圖18解用結點表示成員，兩成員間如有共同語言，則用邊相連，可得下圖．由于圖中的回路長度均為偶數(shù)，故此圖為二部圖．設，，當六位代表如此分組時，則同一組內的任意兩個人都不能直接交談．第19頁，課件共39頁，創(chuàng)作于2023年2月數(shù)學建模中的圖論方法----綜合例題例3

某中學有3個課外小組：英語組(A)、物理組(B)和生物組(C)，有5名學生a,b,c,d,e，(1)已知a,b為A組成員，a,c,d為B組成員，c,d,e為C組成員；(2)已知a為A組成員，b,c,d為B組成員，b,c,d,e為C組成員；(3)已知a為A組成員，a又為B組成員，b,c,d,e為C組成員．問在以上三種情況下，能否各選出3名不兼職的組長？解：根據(jù)三種已知情況，分別畫出二部圖，如圖所示．記，第20頁，課件共39頁，創(chuàng)作于2023年2月數(shù)學建模中的圖論方法----圖論中的幾個實用算法4.圖論中的幾個實用算法1．加權圖中的最短路徑的Dijkstra算法最短路徑問題：給定連接若干城市的鐵路網(wǎng)，尋找從指定城市到各城市去的最短路線。數(shù)學模型：設是一個加權圖，邊的權記為，路徑P的長度定義為路徑中邊的權之和，記為。兩結點u和v之間的距離定義為

問題：在加權的簡單連通無向圖G(V,E,W)中，求一結點a(源點)到其它結點x的距離——稱單源問題。Dijkstra算法的基本思想是：若是從

到

的最短路徑，則也必然是從

到的最短路徑。第21頁，課件共39頁，創(chuàng)作于2023年2月數(shù)學建模中的圖論方法----圖論中的幾個實用算法2．求最小生成樹的Kruskal算法數(shù)學模型：在一個連通加權圖上求權最小的連通生成子圖，顯然，即求權最小的生成樹，稱最小生成樹。筑路選線問題：欲修筑連接n個城市的鐵路，已知i城與j城之間的鐵路造價為

，設計一個線路圖，使總造價最低。Kruskal算法（避圈法）1956年設G為由n個頂點、m條邊構成的加權連通圖。先將G中所有的邊按權的大小次序進行排列，不妨設，??；ⅱ

若導出的子圖不含回路，則；ⅲ

若A中已有n-1條邊，則stop；否則，轉ⅱ。

第22頁，課件共39頁，創(chuàng)作于2023年2月數(shù)學建模中的圖論方法----圖論中的幾個實用算法例：求圖(a)中加權圖的最小生成樹．解：用Kruscal算法可以求得最小生成樹如圖(b)．第23頁，課件共39頁，創(chuàng)作于2023年2月數(shù)學建模中的圖論方法----圖論中的幾個實用算法3.中國郵路問題中國郵路問題：郵遞員傳送報紙和信件，都要從郵局出發(fā)，經(jīng)過他所管轄的每一條街道，最后回到郵局，要求最短的傳送路線．數(shù)學模型：在加權圖上找一條經(jīng)過所有邊至少一次的回路，使它的權數(shù)最小。

如果是歐拉圖,則所求回路必為歐拉回路。下面給出在歐拉圖上求取歐拉回路的Fleury算法。第24頁，課件共39頁，創(chuàng)作于2023年2月數(shù)學建模中的圖論方法----圖論中的幾個實用算法(1)Fleury算法(3)重復步驟(2),直至不能進行下去為止。(1)任取起始結點,令；(2)設路徑已選定,則從中選一邊,使得:(ⅰ)與相連(共端)；(ⅱ)除非已無選擇余地,不要選的橋(斷邊),即仍連通；第25頁，課件共39頁，創(chuàng)作于2023年2月數(shù)學建模中的圖論方法----圖論中的幾個實用算法(2)Edmonds-Johnson算法如果G不是歐拉圖，即存在奇結點，這時某些邊必被重復走過，我們稱這樣的邊為重復邊?？紤]到奇結點必為偶數(shù)個，我們可以把奇結點劃分成若干對，每對之間在G中有相應的最短路，將這些最短路的邊以原來的權作為重復邊疊加在原圖上形成一個多重圖G*，則G*是一個歐拉圖，可用Fleury算法求出歐拉回路。問題是當G的奇結點較多時，可能有很多的配對方法，應怎樣選擇配對，使相應的歐拉回路的權最小呢？1973年，Edmonds和Johnson給出下面的算法：第26頁，課件共39頁，創(chuàng)作于2023年2月數(shù)學建模中的圖論方法----圖論中的幾個實用算法(2)Edmonds-Johnson算法設G是連通加權圖,(1)求出G的奇結點集；(2)用Dijkstra算法求得V0中每對結點的距離；(3)構作加權完全圖:以為結點集,以為邊的權；(4)求中權之和最小的完備匹配M；(5)用Dijkstra算法求M中邊的端點之間在G中的最短路徑；(6)在(5)中求得的每條最短路徑上每條邊添加一條同權的新邊,即得所求之歐拉圖G*；(7)在G*上用Fleury算法求一條歐拉回路,即為問題的解。第27頁，課件共39頁，創(chuàng)作于2023年2月數(shù)學建模中的圖論方法----圖論中的幾個實用算法4.迷宮和DFS算法

迷宮問題：一座迷宮，游人事先未知其結構，如何搜索前進，保證萬無一失地通過每一通道再從入口退出？縱深搜索原則：任選一條未曾走過的通道就盡可能遠地走下去，直至無未曾走過的路可走時，沿未逆行過的最晚來路返回，發(fā)現(xiàn)有未走過的路，則沿它盡可能遠地走下去，依次運行至重返入口止。1973年，Hopcroft和Tarjan把上述縱深搜索原則編寫成DFS(DepthFirstSearch)算法.例如，在地圖是未知的情形下，雙車道單車掃雪車，按右側通行交通規(guī)則，依DFS算法的過程安排掃雪工作程序即可。第28頁，課件共39頁，創(chuàng)作于2023年2月數(shù)學建模中的圖論方法----圖論中的幾個實用算法5.TSP(貨郎擔問題)及“最鄰近算法”一個與哈密爾頓圖有密切關系的問題是所謂“貨郎擔”問題或“旅行商”問題(TravellingSalesmanProblem)：貨郎為了銷售物品，要去訪問若干個村、鎮(zhèn)，然后回到自己所住的地方。假設每個村鎮(zhèn)間都有路，那么他應該怎樣設計所走的路線，使得能對每個村鎮(zhèn)恰好訪問一次且走的路程最短？用圖論的話來講就是：在一個加權的完全無向圖中，如何尋找一條最短的哈密爾頓回路？迄今為止還沒有找到一個解決“貨郎擔”問題的有效算法（多項式算法）。一般來講，這個問題比哈密爾頓問題更加困難些。下面介紹一個近似解法—“最鄰近方法”（或稱“貪婪算法”），這是實際工作中經(jīng)常采用的方法：第29頁，課件共39頁，創(chuàng)作于2023年2月數(shù)學建模中的圖論方法----圖論中的幾個實用算法最鄰近算法ⅰ

選任意點作為始點，找出一個與始點最近的點，形成一條邊的初始路徑。然后用ⅱ逐點擴充這條路徑。ⅱ

設x表示最新加到這條路徑上的點，從不在路徑上的所有點中，選一個與x最鄰近的點，把連接x與此點的邊加到這條路徑中。重復這一步，直到G中所有頂點包含在路徑中。ⅲ

把始點和最后加入的頂點之間的邊放入，這樣就得到一個回路。第30頁，課件共39頁，創(chuàng)作于2023年2月數(shù)學建模中的圖論方法----圖論中的幾個實用算法例對加權完全無向圖K5如圖(a)，如果從v1出發(fā)，使用“最鄰近方法”得到的哈密爾頓回路如圖(b)，總距離為40；最小哈密爾頓回路的總距離為37（如圖(c)）。(a)(b)(c)第31頁，課件共39頁，創(chuàng)作于2023年2月數(shù)學建模中的圖論方法----圖論中的幾個實用算法6.匈牙利算法分工問題：工作人員去做n件作，每人適合做其中的一項或幾項，問能否每人都有一份適合的工作？如果不能，最多幾人可以有適合的工作？數(shù)學模型：G是二分圖,結點集劃分為,,,當且僅當適合做工作時,,求G中的最大匹配.解決這個問題可以用1965年Edmonds提出的匈牙利算法.第32頁，課件共39頁，創(chuàng)作于2023年2月數(shù)學建模中的圖論方法----圖論中的幾個實用算法最佳分工問題：在分工問題中，工作人員適合做的各項工作當中，效益未必一致，我們需要制定一個方案，使公司總效益最大。

數(shù)學模型：在分工問題的模型中，圖G的每邊加了權表示做工作的效益，求加權圖G上的權最大的完備匹配。解決這個問題可以用Kuhn-Munkras算法。

第33頁，課件共39頁，創(chuàng)作于2023年2月數(shù)學建模中的圖論方法----其他問題5.其他問題1.地圖著色問題把無環(huán)圖G的結點皆染上顏色，且使相鄰的結點顏色不同，又所用的顏色最少，稱這個顏色數(shù)為G的色數(shù)，記為。定理設G為無環(huán)圖，則，其中是G中結點的最大度數(shù)。1976年，Appel和Haken用計算機證明了下面的四色定理若G是平面圖，則。第34頁，課件共39頁，創(chuàng)作于2023年2月數(shù)學建模中的圖論方法----其他問題(1)考試日程問題:選修課考試安排時,要避免任何一位學生所選不同課程在同一天考,問最少幾天才能完成?數(shù)學模型:以每門課程為結點,僅當兩門課程被同一位學生選修時,在這兩個結點之間連上一條邊,構作一個圖G,求取即為所求。(2)存儲安全問題:某公司生產若干種化學制品,其中有些制品如果放在一起可能發(fā)生化學反應,引起危險.因此公司必須把倉庫分成相互隔離的若干區(qū).問至少要劃分多少小區(qū),才可安全存放?數(shù)學模型:以每種貨物為結點,僅當兩種貨物放在一起不夠安全時,在這兩個結點之間連上一條邊,如此得到的圖G的色數(shù)即為所求。第35頁，課件共39頁，創(chuàng)作于2023年2月數(shù)學建模中的圖論方法----其他問題(3)頻率分配問題:地面上有若干無線電發(fā)射臺,對每臺分配一個頻率供其使用,頻率用自然數(shù)從1起編號,稱為信道號碼,為排除同信道的干擾,要求使用同信道的發(fā)射臺相距必須大于指定的正數(shù)d,問至少要幾個信道?