【正文】 劃分 (V1,V2)的二分圖 G有完美匹配 ? ?V1?=?V2?,且 對 ?S?V1(或 V2),有 ?N(S)???S?. 證明 :必要性 .若 二分圖 G有完美匹配 ,由定理 3有 ?V2=N(V1)???V1?,即 ?V2???V1?,同理 ?V1???V2?,因此?V1?=?V2?. 充分性 :因為 對 ?S?V1,有 ?N(S)???S?,由定理 1,G中存在飽和 V1的每個頂點匹配 M,又 G是二分圖 ,故匹配 M的每一邊的兩個端點分別屬于 V1和 V2,據(jù) ?V1?=?V2?即知 M飽和V2,所以 M為完美匹配 . 推論 2. 設(shè) G是 k(0)正則二分圖 ,則 G有完美匹配 . 證明 :因為 G是二部劃分 (V1,V2)的 k正則二分圖 ,故 k?V1?=E(G)=k?V2? 又 k?0,所以 ?V1?=?V2?.任取 S?V1,并用 E1和 E2分別表示 G中與 S和 N(S)中關(guān)聯(lián)的邊集 ,則 E1?E2,則 k?N(S)?=?E2???E1?=k?S?即 ?N(S)???S?,? S?V1, 由定理 3可知 ,G有飽和 V1的匹配 M,再據(jù) ?V1?=?V2?和推 論 1即知 M是完美匹配 . 推論 3. 設(shè) G是二部劃分 (V1,V2)的簡單二分圖 ,且 ?V1?=?V2?=n,若 ?(G)?n/2,則 G有完美匹配 . 證明 :?S?V1,(1)若 S中至少有兩個頂點 ,由 ?(G)?n/2可知 ?N(S)??n/2+n/2=n=?V1???S? (2)若 S中只有一個頂點 ,由 ?(G)?n/2可知 ?N(S)??n/2, 所以 ?N(S)??1??S?=1. 綜上 ,對 ?S?V1,均有 ?N(S)???S?,所以 G中有完美匹配 . 定理 4. G有完美匹配 ?O(GS)??S?,?S?V(G),其中 O(GS)是 GS的奇數(shù)階連通分支數(shù)目 .(不證 ) 例 n張紙牌 ,每張紙牌的正反兩面都寫上 1,2,…n 的某一個數(shù) .證明 :如果每個數(shù)字恰好出現(xiàn)兩次 ,則這些紙牌一定可以這樣攤開 ,使朝上的面中 1,2,…n 都出現(xiàn) . 證明 :作一個二分圖 G=V1,V2,E,其中V1={1,2,…,n},V 2={y1,y2,…,y n}表示這 n張紙牌 .i與 yi之間連接的邊數(shù) 等于 數(shù) i在紙牌 yj中出現(xiàn)的次數(shù) ,這樣得到的圖G是一個 2正則二分圖 ,因此圖 G中有完美匹配 ,設(shè)為 M={1yi1,2yi2,…,ny in} 則只要把紙牌 yi1中的 1朝上 ,yi2中的 2朝上 ,…,y in的 n朝上 , 這樣攤開 ,這樣攤開的紙牌就能使上面中 1,2,…,n 都出現(xiàn) . 例 6種不同顏色的紗布織成的雙色布 ,由該 廠所生產(chǎn)的雙色布中 ,每一種顏色至少和其他三種顏色搭 配 .證明 可以挑選出三種不同的雙色布 ,它們含有所有的 6 種顏色 . 證明 :構(gòu)造圖 G=V,E,其中 V={v1,v2,v3,v4,v5,v6}表示 6種顏 色 ,工廠生產(chǎn)出一種顏色 vi與 vj搭配而成的雙色布 ?邊 {vi,vj} ?E(G).由題意知 ,G為簡單圖 ,且每個結(jié)點的度數(shù)至少為 3,下證 G中含有一個完美匹配 . 今設(shè) {v1,v2}?E(G),由于 d(v3) ≥3,所以存在一個不同于 v1和 v2的頂點 vi(4≤i≤6),使 {v3,vi}?E(G),不妨設(shè) vi=4, 即 {v3,v4}?E(G). 如果邊 {v5,v6}?E(G),由于 d(v5)≥3,v1,v2,v3,v4中至少有 3個頂點與 v5相鄰 ,即 v5與邊 {v1,v2},{v3,v4}中的每一邊的某一個端點相鄰 ,不妨設(shè) {v1,v5}?E(G)和{v3,v5}?E(G). 對于頂點 v6,同樣與 v1,v2,v3,v4中至少 3個頂點相鄰 ,即在 v2和 v4中至少有一個頂點與 v6相鄰 .如果{v2,v6}?E(G),則邊 {v1,v5},{v3,v4},{v2,v6}是 G的一個完美匹配 。 (3)在 V1中找一非 M飽和點 x,置 S={x},T=?。 (5)若 y為 M飽和點轉(zhuǎn) (6),否則作求一條從 x到 y的 M可增廣路P,置 M=M?P,轉(zhuǎn) (2) (6)由于 y是 M飽和點 ,故 M中有一邊 {y,u},置 S=S?{u}, T=T?{y},轉(zhuǎn) (4). 例 1 如圖 G所示， V1={x1,x2,x3,x4,x5}，V2={y1,y2,y3,y4,y5}，試求圖 G的最大匹配。 G中由起點為 x的 M交錯路所能連接的頂點集所導(dǎo)出的 G的導(dǎo)出子圖 稱為根在 x的 M交錯子圖 . 定理 1. 設(shè) M是具有二部劃分 (V1,V2)的二分圖 G的匹配 , x?V1是非 M飽和點 ,H是 G中根在 x的 M交錯子圖的頂點 集 S=H?V1,T=H?V2,則 : (1)T?NG(S)。 由 v 4 向 v 1 追溯 ： 141 ?r 所以從 v 5 到 v 1 的最短路徑為： 1435 ??? .返回 最 短 路 的 應(yīng) 用 一、 可化為最短路問題的多階段決策問題 二、 選 址 問 題 1． 中心問題 2． 重心問題 返回 可化為最短路問題的多階段決策問題 例 1 設(shè)備更新問題：企業(yè)使用一臺設(shè)備，每年年初，企業(yè)領(lǐng)導(dǎo)就要確定是購置新的，還是繼續(xù)使用舊的 . 若購置新設(shè)備，就要支付一定的購置費(fèi)用；若繼續(xù)使用，則需支付一定的維修費(fèi)用 . 現(xiàn)要制定一個五年之內(nèi)的設(shè)備更新計劃，使得五年內(nèi)總的支付費(fèi)用最少 . 已知該種設(shè)備在每年年初的價格為： 第一年 第二年 第三年 第四年 第五年 11 11 12 12 13 使用不同時間設(shè)備所需維修費(fèi)為： 使用年限 0 － 1 1 － 2 2 － 3 3 － 4 4 － 5 維修費(fèi) 5 6 8 11 18 構(gòu)造加權(quán)有向圖 G 1( V , E ) （ 1 ）頂點集 V ＝ { Xib , i =1,2, 3,4, 5} ∪ { X ir k( ) , i =2,3, 4,5, 6。 k = 1,2 ,i 1} 若第 i 年初作了決策X i后，第 i+ 1 年初可以作決策X i ? 1，則頂點X i與 X i ? 1之間有弧 (X i,X i ? 1) ，其權(quán) W(X i,X i ? 1) 代表第 i 年初到第 i+ 1 年 初之間的費(fèi)用 . 例如，弧( , )( )X Xb r3 4 1代表第 三 年初買新設(shè)備，第四年初 決定用第三年買的用過一年的舊設(shè)備，其權(quán)則為第三年初的購置費(fèi)與 第 三、 第 四年間的維修費(fèi)之和， 即 為 12 ＋ 5 ＝ 17 . （ 3 ）問題轉(zhuǎn)化為頂點 Xb1到 Xrk6( )的最短路問題 . 五年的最優(yōu)購置費(fèi)為 k b rkd X X? 1 2 3 4 5 1 6, , , ,( )m in { ( , )} 其中 d( Xb1, Xrk6( )) 為頂點 Xb1到 Xrk6( )的最短路的權(quán) . 求得最短路的權(quán)為 53 ，而兩條最短路分別為 X X X X X Xb r r b r r1 2 1 3 2 4 5 1 6 2? ? ? ? ?( ) ( ) ( ) ( )。 (c) T=NG(S),且 ?T?=?S?1. 證明 :(1)?y?T,則 G中存在以 x和 y為端點的 M交錯路 u?Np(y),由于 G是二分圖且 y?T?V2,所以 u?H?V1=S, 即 y?NG(S),因而 T? NG(S),. (2)(a)?(b)設(shè) y是 H中異于 x的非 M飽和點 ,則 G中存在以 x和 y為端點的 M交錯路 P。 例 k5,5,其中 V1={x1,x2,x3,x4,x5}, V2={y1,y2,y3,y4,y5,},且 k5,5的權(quán)矩陣為 A,求 k5,5的最 優(yōu)匹配 . 3 5 5 4 12 2 0 2 22 4 4 1 00 1 1 0 01 2 1 3 3A?????????????????實驗作業(yè) 生產(chǎn)策略問題 ：現(xiàn)代化生產(chǎn)過程中，生產(chǎn)部門面臨的突出問題之一，便是如何選取合理的生產(chǎn)率 .生產(chǎn)率過高，導(dǎo)致產(chǎn)品大量積壓，使流動資金不能及時回籠；生產(chǎn)率過低，產(chǎn)品不能滿足市場需要，使生產(chǎn)部門失去獲利的機(jī)會 .可見，生產(chǎn)部門在生產(chǎn)過程中必須時刻注意市場需求的變化，以便適時調(diào)整生產(chǎn)率，獲取最大收益 . 某生產(chǎn)廠家年初要制定生產(chǎn)策略，已預(yù)知其產(chǎn)品在年初的需求量為 a=6萬單位，并以 b=1萬單位 /月速度遞增 .若生產(chǎn)產(chǎn)品過剩，則需付單位產(chǎn)品單位時間（月）的庫存保管費(fèi) C2=；若產(chǎn)品短缺，則單位產(chǎn)品單位時間的短期損失費(fèi) C3= .假定生產(chǎn)率每調(diào)整一次帶有固定的調(diào)整費(fèi)C1=1萬元，問：工廠應(yīng)如何制定當(dāng)年的生產(chǎn)策略，使工廠的總損失最?。? 返回