第8講 最短路問題

圖論圖論起源于18世紀(jì)對(duì)哥尼斯堡七橋問題的研究，哥尼斯堡是18世紀(jì)屬于東普魯士的一座城市，它位于普列格爾河畔，河中有兩個(gè)島A,B,把市區(qū)分成了四塊陸地A,B,C,D。該城的市民熱衷于一個(gè)游戲，從四塊陸地的某一處出發(fā)通過每座橋恰好一次，再回到出發(fā)地。圖論的基本概念一、圖的概念1、圖的定義2、頂點(diǎn)的次數(shù)

3、子圖二、圖的矩陣表示1、關(guān)聯(lián)矩陣2、鄰接矩陣定義有序三元組G=(V,E,)稱為一個(gè)圖.圖的定義定義定義頂點(diǎn)的次數(shù)例在一次聚會(huì)中，認(rèn)識(shí)奇數(shù)個(gè)人的人數(shù)一定是偶數(shù)。偶點(diǎn)與奇點(diǎn)：如果某個(gè)頂點(diǎn)相連的邊的條數(shù)為偶數(shù)，則稱這個(gè)頂點(diǎn)為偶點(diǎn)，否則稱為奇點(diǎn)。子圖關(guān)聯(lián)矩陣注：假設(shè)圖為簡(jiǎn)單圖鄰接矩陣注：假設(shè)圖為簡(jiǎn)單圖七橋問題變?yōu)椋簭膱D中任一點(diǎn)出發(fā)，找出一條通過每條邊有且只有一次，最后回到出發(fā)點(diǎn)的回路。通常稱這樣的回路為歐拉回路。直觀來看：對(duì)于某個(gè)頂點(diǎn)，有一個(gè)進(jìn)來的邊就有一個(gè)出去的邊，同樣，有一條出去的邊，必然有一條進(jìn)來的邊。對(duì)于七橋問題，該圖四個(gè)頂點(diǎn)都是奇點(diǎn)，問題無解?？紤]問題有解的條件？人，狼、羊、菜問題有一農(nóng)夫帶著一只狼、一頭羊和一蘿白菜想從A岸撐船到B岸，現(xiàn)在有一條船，而船只能容納農(nóng)夫和另外一樣，人不在的情況下，狼會(huì)吃羊，羊吃白菜，怎樣才能把這幾樣?xùn)|西運(yùn)到對(duì)岸。問題轉(zhuǎn)化為求一條從頂點(diǎn)(1,1,1,1)到頂點(diǎn)(0,0,0,0)的路。若要求擺渡次數(shù)最少，可以對(duì)各邊賦權(quán)值為1，轉(zhuǎn)化為求最短路。消防設(shè)施的安置有一個(gè)小區(qū)，有七條街道，街道一共有五個(gè)交叉路口，如圖，現(xiàn)在要在某些路口安置消防設(shè)施，要求每條街道至少有一個(gè)路口設(shè)置有消防設(shè)施，則在哪些路口安置設(shè)施最為節(jié)?。窟@個(gè)問題是覆蓋問題，覆蓋的定義如下，若圖G的每條邊至少有一個(gè)端點(diǎn)在頂點(diǎn)集V的一個(gè)子集K中，則K稱為G的覆蓋。含頂點(diǎn)最少的覆蓋為最小覆蓋?？梢杂藐P(guān)聯(lián)矩陣求得。得到最小覆蓋（B,C,D）,(A,C,E),(B,D,E)化學(xué)制品的存放某實(shí)驗(yàn)室現(xiàn)有化學(xué)制品7種，其中部分是不相容的，應(yīng)該相互隔離在不同的房間里，以免發(fā)生危險(xiǎn)。這7中化學(xué)制品的相容性如下，則至少準(zhǔn)備多少間獨(dú)立的房間才能保證安全？ABCDEFGA不不B不不不C不不不D不不E不F不G問題轉(zhuǎn)化為圖上相鄰的兩個(gè)頂點(diǎn)代表的化學(xué)制品必不能放在同一個(gè)房間。設(shè)想用紅，藍(lán)，黃色等標(biāo)記，則相當(dāng)于所有相鄰的頂點(diǎn)的顏色不能相同，如何用最少的顏色將頂點(diǎn)染色。頂點(diǎn)染色問題就是在頂點(diǎn)集中找出不包含相鄰頂點(diǎn)的子集，并要求這種子集內(nèi)頂點(diǎn)數(shù)目盡量多。稱不包含相鄰頂點(diǎn)的子集S為獨(dú)立集，若S中添加任何一個(gè)頂點(diǎn)都會(huì)使其不再是獨(dú)立子集，則稱S為極大獨(dú)立集。步驟：1.求出各頂點(diǎn)的相鄰的點(diǎn)，并用邏輯表達(dá)式表示出來，如A＋BD得到B+ACEG，C+ACEF，D+ACEG，E+BCDF，F(xiàn)+CEG，G+BDF（2）將各邏輯表達(dá)式合并得：（A＋BD）（B+ACEG）（C+ACEF）（D+ACEG）（E+BCDF）（F+CEG）（G+BDF）（3）得到所有極大獨(dú)立集（B,D,F）（A,F）（A,C,G）（A,E,G）取一個(gè)最大獨(dú)立集，染第一種顏色。直到著色結(jié)束。最短路問題及其算法一、基本概念二、固定起點(diǎn)的最短路三、每對(duì)頂點(diǎn)之間的最短路基本概念固定起點(diǎn)的最短路最短路是一條路徑，且最短路的任一段也是最短路．算法步驟：u1u2u3u4u5u6u7u8每對(duì)頂點(diǎn)之間的最短路1、求距離矩陣的方法2、求路徑矩陣的方法3、查找最短路路徑的方法（一）算法的基本思想（三）算法步驟算法的基本思想算法原理——求距離矩陣的方法算法原理——求路徑矩陣的方法在建立距離矩陣的同時(shí)可建立路徑矩陣R．即當(dāng)vk被插入任何兩點(diǎn)間的最短路徑時(shí)，被記錄在R(k)中，依次求時(shí)求得，可由來查找任何點(diǎn)對(duì)之間最短路的路徑．算法步驟v1v29v4v2v574223一、可化為最短路問題的多階段決策問題二、選址問題1、中心問題2、重心問題可化為最短路問題的多階段決策問題

選址問題--中心問題S(v1)=10,S(v2)=7,S(v3)=6,S(v4)=8.5,S(v5)=7,S(v6)=7,S(v7)=8.5S(v3)=6,故應(yīng)將消防站設(shè)在v3處。

選址問題--重心問題最優(yōu)匹配算法設(shè)有六個(gè)人和六項(xiàng)工作的最優(yōu)指派問題，其效益矩陣如下:問題是求一種工作分配，使每個(gè)工人完成一項(xiàng)任務(wù)，而且效益最大。工人1234561201516547217153312863912181630134128112719145-7102110326---61113設(shè)G(V,E)是一個(gè)二部圖，設(shè)M是E的一個(gè)子圖，如果M中的所有邊沒有公共的頂點(diǎn)，則稱M是二部圖G(V,E)的一個(gè)匹配。如果它關(guān)聯(lián)的邊是匹配M的一條邊，則稱頂點(diǎn)是飽和的。如果M的所有頂點(diǎn)都是飽和的，稱M為G的完美匹配。如何求一個(gè)具有最大權(quán)的完美匹配假定：圖G是加權(quán)二部圖，兩個(gè)頂點(diǎn)集合為V1,V2，并且V1,V2均有n個(gè)頂點(diǎn)。對(duì)于每個(gè)頂點(diǎn)對(duì)，邊存在。在介紹最優(yōu)匹配算法之前，先介紹概念－－可擴(kuò)充路定義設(shè)M是G的一個(gè)匹配，G的M交錯(cuò)路是指其邊在E-M和M中交錯(cuò)出現(xiàn)的路。M可擴(kuò)充路是指其起點(diǎn)和終點(diǎn)都是M非飽和的M交錯(cuò)路。藍(lán)線是匹配M的邊，黑線不屬于M，因此路徑是一條可擴(kuò)充路，去掉邊，得到另一個(gè)圖?？尚许旤c(diǎn)標(biāo)號(hào)定義設(shè)G是加權(quán)二部圖，其中W是加權(quán)矩陣，設(shè)L(v)是頂點(diǎn)v的標(biāo)號(hào)，對(duì)于所有的邊，有，則稱L是可行頂點(diǎn)標(biāo)號(hào)，記稱具有邊集的G的生成子圖為對(duì)應(yīng)可行頂點(diǎn)標(biāo)號(hào)L的相等子圖，記為G(L)。對(duì)于任何加權(quán)二部圖G，它的可行頂點(diǎn)標(biāo)號(hào)是存在的，只需令設(shè)S是圖G的頂點(diǎn)集，稱與S的頂點(diǎn)相鄰的所有頂點(diǎn)組成的集合為鄰集，記為工人1234561201516547217153312863912181630134128112719145-9971021