[高等教育]圖論方法建模-文庫吧資料
2025-01-25 18:39本頁面
【正文】 t o n 圈 : 12112121vvvvvvvvvvvCnjjijjjiij?????????, 它是由C中刪 去邊1?ii vv和1?jj vv，添加邊jivv和11 ?? ji vv而得到的。修改的方法叫做改良圈算法。如何為他（她）設計一條最短的旅行路線（從駐地出發(fā)，經過每個城市恰好一次，最后返回駐地）？這一問題的研究歷史十分悠久，通常稱之為旅行商問題。 （ i ii ）G中有 E ul e r 跡的充要條件是G連通且至多有兩個奇次點。 Euler圖和 Hamilton圖 2022/2/16 五、 旅行商問題 定理 （ i ）G是 E ul e r 圖的充分必要條件是G連通且每頂點皆偶次。 [M,MaxZjpp]=km(A,5) 2022/2/16 五、 旅行商問題 定義 經過G的每條邊的跡叫做G的 E ul e r 跡；閉的 E ul e r跡叫做 E u l e r 回路或 E 回路；含 E u l e r 回路的圖叫做 E u l e r 圖。0 1 1 0 0。2 2 0 2 2。 MaxZjpp— 輸出最優(yōu)匹配的總長度。 命令形式： [M,MaxZjpp]=km(A,n) 功能： A是輸入二部圖的權矩陣， n是匹配點。修改后的頂標仍是可行頂標，原 來的匹配 M仍然存在，相等子圖中至少出現(xiàn)了一條 不屬于 M的邊，所以造成 M的逐漸增廣。求 出 d=min{lx[i]+ly[j]w[i,j]}其中 i結點被訪問， j結點沒 有被訪問。邊上的權如下矩陣。 四、 匹配問題 2022/2/16 KM算法 ? 對于任意的 G和 M，可行頂標都是存在的： ? l(x) = maxw(x,y) ? l(y) = 0 ? 欲求完全二分圖的最佳匹配，只要用匈牙利算法求其相等子圖的完備匹配；問題是當標號之后的 Gl無完備匹配時怎么辦？ 1957年， Kuhn和 Munkras給出了一個解決該問題的有效算法，用逐次修改可行頂標 l(v)的辦法使對應的相等子圖之最大匹配逐次增廣，最后出現(xiàn)完備匹配。 四、 匹配問題 2022/2/16 KM算法 ? 窮舉的效率－ n！，我們需要更加優(yōu)秀的算法。 ? 實際模型：某公司有職員 x1,x2,…,x n,他們去做工作 y1,y2,…,y n,每個職員做各項工作的效益未必一致，需要制定一個分工方案，使得人盡其才，讓公司獲得的總效益最大。0 1 1 0。 d=[0 1 0 0。 格式： [e,total]=pipei(d) 功能： d是二部圖矩陣 (01矩陣 )。},{,3321yBBuSSyuMMyPEMMPMyxMyBSNyBSNBxSxMXXMMG??????????? ? 四、 匹配問題 2022/2/16 例 1 求二部圖 G中的最大匹配。 四、 匹配問題 2022/2/16 ）轉（置中有一邊飽和點，故是由于轉置可擴路的到求一條從）；否則作：飽和點轉（為若擇一點則停止；否則，任意選）若（置非飽和點中尋找一個）在（）；否則轉（中的每一個頂點，結束飽和）若（中的一個初始匹配）任意?。ɑ静襟E：4},{},{,)6()2(),(,6)5(。 四、 匹配問題 2022/2/16 ? 結論： ? P的路徑長度必定為奇數，第一條邊和最后一條邊都不屬于 M。 ? M中任意一條邊的端點 v稱為（關于 M的）飽和 點， G中其他定點稱為非飽和點。 四、 匹配問題 2022/2/16 匈牙利算法 ? 求最大匹配的一種顯而易見的算法是：先找出 全部匹配，然后保留匹配數最多的。 ? 選擇這樣的邊數最大的子集稱為圖的 最大匹配問題 。則稱圖 G為二分圖。 ? 設 G=(V,{R})是一個無向圖。上述的工作分配問題就是要在圖 G中找 一個邊集 E的子集，使得集中任何兩條邊沒有公共端 點，最好的方案就是要使此邊集的邊數盡可能多，這 就是匹配問題。 怎樣分配才能盡量的工作有人做，更多的人有工作？ 圖的匹配 2022/2/16 這個問題可以用圖的語言描述。a5] [out,len]=kruskal(map) 2022/2/16 四、 匹配問題 例 指派問題 一家公司經理準備安排
教學課件相關推薦
鄂ICP備17016276號-1