【正文】 x2, … , xn安排 n項工作 y1, y2, … , yn. n個工作人員中每個人能勝任一項或幾項工作 , 但并 不是所有工作人員都能從事任何一項工作 . 比如 x1能做 y1, y2工作 , x2能做 y2, y3, y4工作等 . 這樣便提出一個問題 , 對所有的工作人員能不能都分配一件他所能勝任的工作？ 二部圖的匹配及其應(yīng)用 河南城建學(xué)院 我們構(gòu)造一個二部圖 G = ( X, Y, E ), 這里 X = {x1, x2, … , xn},Y = { y1, y2, … , yn}, 并且當(dāng)且僅當(dāng)工作人員 xi勝任工作 yj時 , xi與 yj才相鄰 . 于是 , 問題轉(zhuǎn)化為求二部圖的一個完美匹配 . 因?yàn)? |X|=|Y|, 所以完美匹配即為最大匹配 . 二部圖的匹配及其應(yīng)用 河南城建學(xué)院 1x 2x 3x 4x 5x1y 2y 3y 4y 5y例 18：求下圖完美匹配 Hungarian算法： ? ? 時終止。 ? 所謂 k正則圖，即每頂點(diǎn)皆度 k的圖。 河南城建學(xué)院 2. 問題求解： 顯然可以看出 ,上圖是一個連通無向圖，記為Ｇ＝｛Ｖ，Ｅ｝ . 任取 vi ∈ V(i=1,2, ……,10) ，考察 vi與Ｖ中其他頂點(diǎn)間的最短路（也稱為距離）：Ｐ ＊ （ vi， v１ ），Ｐ ＊ （ vi，v2）， …… ，Ｐ ＊ （ vi， v１０ ），把這 10個距離中最大的數(shù)稱為頂 vi的最大服務(wù)距離，記為 L(vi). 求出上圖中各點(diǎn)間的距離，如下表所示，這樣就可以把每個頂點(diǎn) vi對應(yīng)的最大服務(wù)距離 L(vi)求出來 . 最短路徑問題實(shí)例： 醫(yī)院選址問題 河南城建學(xué)院 最短路徑問題實(shí)例 ： 醫(yī)院選址問題 1 2 3 4 5 6 7 8 9 10 1 0 5 3 6 5 10 10 9 12 13 2 5 0 2 3 4 9 6 8 8 9 3 3 2 0 3 2 7 7 6 9 10 4 6 3 3 0 5 7 5 6 7 8 5 5 4 2 5 0 5 5 4 7 8 6 10 9 7 7 5 0 2 1 4 5 7 10 6 7 5 5 2 0 1 2 3 8 9 8 6 6 4 1 1 0 3 4 9 12 8 9 7 7 4 2 3 0 5 10 13 9 10 8 8 5 3 4 5 0 河南城建學(xué)院 最短路徑問題實(shí)例 ： 醫(yī)院選址問題 注：上表中的１，２，３，４，５，６，７，８，９，１０分別代表 v1， v２ ， v３ ， v４ ， v５ ， v６ ， v７ ， v８ ， v９ ， v１０ v1到各頂點(diǎn)的距離就是上表中的第一行各數(shù)，它們中最大的是 13，所以 L(v1)=13，其它各點(diǎn)的最大服務(wù)距離分別為 : L(v2)=9， L(v3)=10， L(v4)=8， L(v5)=8 ， L(v6)=10 ， L(v7)=10， L(v8)=9 ， L(v9)=12， L(v10)=13。 }sp ss sp sr rpL L d L d? ? ?河南城建學(xué)院 例 求圖中頂點(diǎn) v0與 v5的最短路徑 . 解 :可以將計算過程用一張表表示出來 (見下頁表 ) 算法示例 河南城建學(xué)院 由上表可知 ,v5與 v3相鄰 ,v3與 v4相鄰 ,v4與 v2相鄰 ,v2與 v1相鄰 ,v1與 v0相鄰 .這 樣從 v5往前追蹤 ,得 v0到 v5的最短路徑為： Γ=v0v1v2v4v3v5. W(Γ)=9. 河南城建學(xué)院 Dijkstra算法的標(biāo)號法舉例 2 10 7 3 6 4 5 2 10 7 3 6 4 5 2 2 10 7 3 6 4 5 2 10 7 3 6 4 5 10 ? 2 ? ? 9 5 2 2 5 5 9 9 9 9 0 0 0 0 河南城建學(xué)院 最短路徑問題實(shí)例：醫(yī)院選址問題 ： 新建居民小區(qū)的醫(yī)院 ， 對該區(qū)每一戶居民都很重要 。 若有 ，則對 p點(diǎn)標(biāo)號； （４）重復(fù)第三步，一直到 t點(diǎn)得到標(biāo)號為止?，F(xiàn)要求從點(diǎn)到某一點(diǎn) t的最 短路。 設(shè) G為賦權(quán)有向圖或無向圖， G邊上的權(quán)均非負(fù)。 求最短路的方法： (1) 求從一點(diǎn)到其余各點(diǎn)間的 Dijkstra算法 。如選址、管道鋪設(shè) 時的選線、設(shè)備更新、投資等都可以歸給為求最短路的 問題。 2 3 4 5 6 7 4 v3 v1 v2 v4 v5 v6 1 5 河南城建學(xué)院 2 3 4 5 6 7 4 v3 v1 v2 v4 v5 v6 1 5 2 3 4 5 6 4 v3 v1 v2 v4 v5 v6 1 5 2 3 4 5 6 4 v3 v1 v2 v4 v5 v6 1 5 2 3 4 5 4 v3 v1 v2 v4 v5 v6 1 5 河南城建學(xué)院 2 3 4 5 4 v3 v1 v2 v4 v5 v6 1 5 2 3 4 4 v3 v1 v2 v4 v5 v6 1 5 2 3 4 4 v3 v1 v2 v4 v5 v6 1 5 2 3 4 v3 v1 v2 v4 v5 v6 1 5 河南城建學(xué)院 最小生成樹實(shí)例 :有線電視網(wǎng)最優(yōu)布線問題 單位： 100米 : 衛(wèi)星加密電視的開播 ,受到大 家歡迎 ,要想收看加密電視必 須建一套有線電視網(wǎng)．我們 考慮這樣一個具體問題：設(shè) 某市六個個區(qū)之的相互距離 如下表所示，試確定表數(shù)據(jù) 形成的網(wǎng)絡(luò)中，如何布線能 布線最?。? 1 2 3 4 5 6 1 0 13 51 77 68 50 2 13 0 60 70 67 59 3 51 60 0 57 3 62 4 77 70 57 0 20 55 5 68 67 36 20 0 34 6 50 59 2 55 34 0 河南城建學(xué)院 最小生成樹實(shí)例 :有線電視網(wǎng)最優(yōu)布線問題 ２ .問題求解 : 最優(yōu)布線問題，就是要求任何兩地都有鏈相連，而使總線路最短，這個問題在圖論中也稱為最小樹題．作下圖，其中頂點(diǎn) v1 ， v２ ， v３ ， v４ ， v５ ， v６ 分別表示兩區(qū)之間的距離． V1 V6 V3 V5 V4 V2 60 70 20 13 67 59 77 57 55 68 51 2 34 36 50 河南城建學(xué)院 最小生成樹實(shí)例 :有線電視網(wǎng)最優(yōu)布線問題 對于上圖，我們要找使布線最省的網(wǎng)絡(luò)模型．圖論中的破圈法可以解 決這個問題，具體過程如下：在圈 v1v２ v３ v1中，去掉最長邊 v２ v３ ＝ 60，同 樣去掉圈 v1v３ v６ v1， v２ v４ v５ v２ ， v３ v４ v５ v３ ， v3 v5v６ v3， v4v5 v6 v4， v1v3v4v1， v1v6v2v1， v2v5v6v2中最長的邊 v1v３ ＝ 51， v2v4＝ 70， v3v4＝ 57， v3v5＝ 36,v4v6＝ 55， v1v4＝ 77， v1v5＝ 68， v2v6＝ 59， v2v5＝ 67，最后構(gòu) 成的圖（如下）就是最省的 布線圖 ． 13 2 50 34 20 v2 v3 v1 v6 v4 v6 V1 V6 V3 V5 V4 V2 60 70 20 13 67 59 77 57 55 68 51 2 34 36 50 河南城建學(xué)院 167。3e任取一條邊 會與已選邊構(gòu)成圈 ,故停止 ,得 中選取在中選取 ,7e 中選取 . 但 與 都 }, 86 ee 84,ee 4e 8e},{ 876432 eeeeee},{ 87642 eeeee,{ 42 ee在河南城建學(xué)院 B 破圈法 任取一個圈，從圈中去掉一條權(quán)最大的邊（如果有兩條或兩條以上的邊都是權(quán)最大的邊，則任意去掉其中一條）。 7 最小生成樹及其應(yīng)用 ? 定義 無向圖 G=（ V,E）的生成子圖 T是樹 ,則稱 T是 G的一棵生成樹（ 支撐樹 ） (不唯一） . ? 任何連通無向圖 G至少有一棵生成樹 . ? 賦權(quán)簡單連通無向圖 G=(V,E,W)的子圖 H的權(quán)定義為 H 的所有邊的權(quán)和 .G中權(quán)最小的生成樹稱為 最小生成樹 (對普通簡單連通圖不考慮最小生成樹 ). ? 最小生成樹有很強(qiáng)的應(yīng)用背景 ,例如 :設(shè)計聯(lián)系若干城市的最短線路通信網(wǎng) 。所以希望有一個方法以獲得相當(dāng)好（但不一定最優(yōu)）的解。稱這種圈為最優(yōu)圈。如何為他設(shè)計一條最短的旅行路線（從駐地出發(fā)，經(jīng)過每個城市恰好一次，最后返回駐地）？這個問題稱為旅行商問題。 河南城建學(xué)院 ? 多郵遞員問題： ? 郵局有 k(k≥2)位投遞員，同時投遞信件，全城街道都要投遞，完成任務(wù)返回郵局，如何分配投遞路線，使得完成投遞任務(wù)的時間最早？我們把這一問題記成 kPP。 ? 上述中國郵遞員問題的數(shù)學(xué)模型是：在一個賦權(quán)連通圖上求一個含所有邊的回路，且使此回路的權(quán)最小。 ? 3. 當(dāng)?shù)?2步不能再執(zhí)行時，算法停止。 ? 2. 假設(shè)跡 Wi=v0e1v1…eivi 已經(jīng)選定，那么按下述方法從 E{e1, … ,ei}中選取邊 ei+1： 河南城建學(xué)院 ? （ i） ei+1和 vi相關(guān)聯(lián)； ? （ ii）除非沒有別的邊可選擇，否則 ei+1不是Gi=G {e1, … ,ei}的割邊 (cut edge)。 河南城建學(xué)院 ? Euler回路的 Fleury算法 ? 1921年， Fleury給出下面的求 Euler回路的算法。 河南城建學(xué)院 ? 定義 包含 G的每個頂點(diǎn)的軌叫做 Hamilton(哈密頓 )軌 ；閉的 Hamilton軌叫做 Hamilton圈或 H圈