【正文】 ,映射 l:V(G)?R,滿足對 G的每條邊 e={x,y},均 有 l(x)+l(y)??(x,y),其中 ?(x,y)表示邊 {x,y}的 權(quán) ,則稱 l為 G的可行頂標(biāo) .令 El={{x,y}?{x,y}?E(G), l(x)+l(y)=?(x,y),Gl為以 El為邊集的 G的生成子圖 , 則稱 Gl為 l等子圖 . 說明 :可行頂標(biāo)總 是存在的 ,例如 : ? ?????? ?? ?? ?212,0)(),(m axVyylVyxxlVy?定理 l是 G的可行頂標(biāo) .若 l等子圖 Gl有完美匹配 M,則 M是 G的最優(yōu)匹配 . 基于定理 1的在一個加權(quán)二分圖 (Km,n,?)中求最優(yōu)匹配的有效算法 ?Kuhnmunkres算法 : (1)從任意可行頂標(biāo) (如平凡標(biāo)號 )l開始 ,確定 l等子圖 Gl,并且在 Gl中選取匹配 M飽和 V1,則 M是完美匹配 ,也即 M是最優(yōu)匹配 ,算法終止 ,否則轉(zhuǎn)入 (2)步 . (2)匈牙利算法終止于 S?V1,T ?V2且使 NGl(S)=T,計算 ,確定新的可行頂標(biāo) l’,并以 l’替代 l,以 Gl’替代 Gl轉(zhuǎn)入 (1)步 . la令2m in{ ( ) ( ) ( , ) | , }la l x l y x y x S y V T?? ? ? ? ? ? 則由 39。 (2)若 M飽和 V1則結(jié)束 .否則轉(zhuǎn) (3)。 i j ≤ 6} ,弧( , )V Vi j表第 i 年初購進一臺設(shè)備一直使用到第 j 年初的決策，其權(quán) W( , )V Vi j表由這一決策在第 i 年初到第 j 年初的總費用，如W ( , )V V1 4=1 1 +5 +6 +8 =30 . （ 3 ）問題轉(zhuǎn)化為求 V 1 到 V 6 的最短路問題，求得兩條最短路為V V V1 4 6– – ， V V V1 3 6– – ，權(quán)為 53 ，與圖 G1( V , E) 的解相同． 返回 （ 2 ） 計算在各點iv設(shè)立服務(wù)設(shè)施的最大服務(wù)距離)( ivS． }{max)(1 ijjidvS???? 1 , 2 , ,i ?? 選址問題 中心問題 例 2 某城 市要建立一個消防站，為該市所屬的七個區(qū)服務(wù)，如圖所示．問應(yīng)設(shè)在 哪 個區(qū)，才能使它至最遠區(qū)的路徑最短． （ 1 ）用 F l o y d 算法求出距離矩陣 D = ?? ?)( ijd ． （ 3 ）求出頂點 kv ，使 )}({m i n)( 1 iik vSvS ???? . 則 kv 就是要求的建立消防站的地點．此點稱為圖的 中心點 ． TO MATLAB (road3(floyd)) 0 7 5 3 97 0 2 4 65 2 0 2 43 4 2 0 69 6 4 6 0D??????????????????????????????????DS(v1)=10, S(v2)=7, S(v3)=6, S(v4)=10, S(v5)=7, S(v6)=7, S(v7)= S(v3)=6,故應(yīng)將消防站設(shè)在 v3處 . 返回 選址問題 重心問題 例 3 某礦區(qū)有 7 個礦點，如圖所示．已知各礦點每天的產(chǎn)礦量為 )(jvq（標(biāo)在圖的各頂點上）．現(xiàn)要從這 7 個礦點選一個來建造礦廠．問應(yīng)選在 哪個礦點，才能使各礦點所產(chǎn)的礦運到選礦廠所在地的總運力（千噸公里 ）最?。? （ 1 ）求距離陣 D = ?? ?)( ijd ． （ 2 ） 計算各頂點作為選礦廠的總運力 )(ivm ijj ji dvqvm ?? ? ? )()( 1? 1 , 2 , ,i ?? （ 3 ） 求 kv 使 )}({m i n)(1 iik vmvm ????，則 kv 就是選礦廠應(yīng)選的 礦點．此點稱為圖 G 的 重心 或 中位點 ． 返回 匹配 匹配問題是運籌學(xué)的重要問題之一 ,也是圖論研究的重點內(nèi)容 ,它提供了解決“人員分配問題”和“最優(yōu)分配問題”一種新的思想 . 定義 G=V,E是無環(huán)圖 ,M?E(G),M??,若 M中任意兩條邊都不相鄰 ,則稱 M是圖 G的一個匹配 .若對圖 G的任何匹配 M’ ,均有 ?M’? ?M?,則稱M是圖 G的最大匹配 ,記作 ?’ (G). 定義 M是圖 G的匹配 ,G中與 M中的邊關(guān)聯(lián)的頂點 稱為 M飽和點 .若圖 G的頂點都是 M飽和 ,則 稱為 G的完美匹配 . 說明 :(1)完美匹配是最大匹配 ,反之未然 。 ? 18世紀(jì)東普魯士哥尼斯堡被普列戈爾河分為四塊 ,它們通過七座橋相互連接 ,如下圖 .當(dāng)時該城的市民熱衷于這樣一個游戲 :“一個散步者怎樣才能從某塊陸地出發(fā)，經(jīng)每座橋一次且僅一次回到出發(fā)點？” S N A B 七橋問題的分析 ? 七橋問題看起來不難，很多人都想試一試，但沒有人找到答案 .后來有人寫信告訴了當(dāng)時的著名數(shù)學(xué)家歐拉 .千百人的失敗使歐拉猜想 ,也許那樣的走法根本不可能 .1876年 ,他證明了自己的猜想 . ? Euler把南北兩岸和四個島抽象成四個點 ,將連接這些陸地的橋用連接相應(yīng)兩點的一條線來表示 ,就得到如下一個簡圖 : S N A B 歐拉的結(jié)論 ? 歐拉指出 :一個線圖中存在通過每邊一次僅一次回到出發(fā)點的路線的充要條件是 : ? 1)圖是連通的 ,即任意兩點可由圖中的一些邊連接起來 。 (2)匹配的定義與邊的方向無關(guān) ,故匹配是針對無向圖而言 . (3)圖 G的邊不交匹配的最小數(shù)目即為 G的邊色數(shù) . 定義 3.(可增廣路 ):設(shè) M是圖 G的匹配 ,P是 G的一條路 ,且在 P中 ,M的邊和 E(G)M的邊交替出現(xiàn) ,則稱 P是 G的一條交錯路 .若 M交錯路 P的兩個端點為 M非飽和點 ,則稱 P為 M可增廣路 . 例 G的一條交錯路和一條可增廣路 . 6 2 3 4 1 5 8 7 匹配的幾個性質(zhì)定理 定理 M1和 M2是圖 G的兩個不同匹配 ,由 M1?M2導(dǎo)出的 G 的邊導(dǎo)出子圖記作 H,則 H的任意連通分支是下列情況之 一 :(1)邊在 M1和 M2中交錯出現(xiàn)的偶圈 . (2)邊在 M1和 M2中交錯出現(xiàn)的路 . 證明 :記 H= M1?M2,因為 H是邊導(dǎo)出子圖 ,所以 ?(H)≥ 于 M1和 M2是圖 G的兩個不同匹配 ,所以 H的任意頂點 x至多 與一條 M1的邊關(guān)聯(lián) ,同時也至多與一條 M2的邊關(guān)聯(lián) ,所以 Deg(x)≤2,所以 ? ≤2,故 H的每個連通分支或者是一條路 或者是一個圈 .據(jù)匹配的定義 ,H的任意兩條鄰接邊一定分 別屬于不同的匹配 M1和 M2,從而每條路或者圈的邊交錯 地屬于 M1和 M2且每個圈是偶圈 . 定理 G的最大匹配 ,當(dāng)且僅當(dāng) G中不存在 M可增廣路 . 證明 :(?)假設(shè)存在 M可增廣路 P,則 M’=M?P是 G的一個新的匹配 ,且 |M’|＝ |M|＋ 1|M|,矛盾 . (?)若 M不是 G的最大匹配 ,則存在匹配 M’,使得 |M’||M|,作H=M’?M,由定理 1,H的任意邊導(dǎo)出子圖 Q是下列兩種情況之一 :(1)交錯偶圈 :Q中每個結(jié)點度數(shù)為 2.(2)交錯路 .Q中除端點外 ,其余結(jié)點度數(shù)均為 2. 因為 |M’||M|,故 |E(H)?M’||E(H)?M|,因而 H中必有一條起始于 M’且終止于 M’的連通分支 P,故 P是 M可增廣路 ,矛盾 ,所以命題正確 . 定義 :NG(S):設(shè) S是圖 G的任意頂點子集 ,G中與 S的頂點鄰接的所有頂點的集合 ,稱為 S的鄰集 ,記做 NG(S). 定理 3(Hall定理 ,1935)設(shè) G是有二部劃分 (V1,V2)的二分圖 , 則 G含有飽和 V1的每個頂點的匹配 M的 充要條件 是 ,對?S?V1,有 ?N(S)???S?. 證明 :(?)對 ?S?V1,匹配 M將 S中的每個頂點與 N(S)中的頂 點配對 ,所以 ?N(S)???S?. (?)當(dāng) 對 ?S?V1,有 ?N(S)???S?時 .可按下述方法作出飽和 V1的匹配 M. 先作一初始匹配 M1,若已經(jīng)飽和 V1,定理得證 .否則 ,V1中至少有一非飽和點 x1,檢查以 x1為起點 ,終點在 V2中的交錯路 .考慮下面兩種情形 : (1)不存在任何一條交錯路可以到達 V2的非飽和點 .此時從 X1開始的一切交錯路的終點還是在 V1中 .故存在 A?V1,使得 ?N(A)??A?,矛盾 . (2)存在一條以 x1為起點 ,終點為 V2的非飽和點的交錯路 P,顯然 P是可增廣路 ,作新匹配 M2=M1?P,則M2飽和 x1,且 ?M2??M1?,因此 ,重復(fù)該過程就可以找到飽和 V1的全部頂點的匹配 M. 推論 1 具 有二部