[高等教育]圖論方法建模(編輯修改稿)
2025-02-15 18:39 本頁面
【文章內(nèi)容簡介】 需要制定一個分工方案，使得人盡其才，讓公司獲得的總效益最大。 ? 數(shù)學(xué)模型： G是加權(quán)完全二分圖，求總權(quán)值最大的完備匹配。 四、 匹配問題 2022/2/16 KM算法 ? 窮舉的效率－ n！，我們需要更加優(yōu)秀的算法。 ? 定理：設(shè) M是一個帶權(quán)完全二分圖 G的一個完 備匹配，給每個頂點一個可行頂標 (第 i個 x頂點的 可行標用 lx[i]表示，第 j個 y頂點的可行標用 ly[j]表 示 )，如果對所有的邊 (i,j) in G,都有 lx[i]+ly[j]=w[i,j] 成立 (w[i,j]表示邊的權(quán) )，且對所有的邊 (i,j) in M,都有 lx[i]+ly[j]=w[i,j]成立，則 M是圖 G的一個最佳匹配。 四、 匹配問題 2022/2/16 KM算法 ? 對于任意的 G和 M，可行頂標都是存在的： ? l(x) = maxw(x,y) ? l(y) = 0 ? 欲求完全二分圖的最佳匹配，只要用匈牙利算法求其相等子圖的完備匹配；問題是當標號之后的 Gl無完備匹配時怎么辦？ 1957年， Kuhn和 Munkras給出了一個解決該問題的有效算法，用逐次修改可行頂標 l(v)的辦法使對應(yīng)的相等子圖之最大匹配逐次增廣，最后出現(xiàn)完備匹配。 四、 匹配問題 2022/2/16 四、 匹配問題 例 2 考慮完全的 2部圖，其中 ， 。邊上的權(quán)如下矩陣。 },{ 521 xxxX ??},{ 521 yyyY ???????????????????3312100110014422202214553W0)()(3)(,1)(,4)(,2)(,5)(5154321????????ylylxlxlxlxlxl?2022/2/16 ? 修改方法如下： ? 先將一個未被匹配的頂點 u(u in {x})做一次增廣 路，記下哪些結(jié)點被訪問那些結(jié)點沒有被訪問。求 出 d=min{lx[i]+ly[j]w[i,j]}其中 i結(jié)點被訪問， j結(jié)點沒 有被訪問。然后調(diào)整 lx和 ly：對于訪問過的 x頂點， 將它的可行標減去 d，對于所有訪問過的 y頂點，將 它的可行標增加 d。修改后的頂標仍是可行頂標，原 來的匹配 M仍然存在，相等子圖中至少出現(xiàn)了一條 不屬于 M的邊，所以造成 M的逐漸增廣。 四、 匹配問題 2022/2/16 KM算法步驟 ? Kuhn－ Munkras算法流程： ? (1)初始化可行頂標的值 ? (2)用匈牙利算法尋找完備匹配 ? (3)若未找到完備匹配則修改可行頂標的值 ? (4)重復(fù) (2)(3)直到找到相等子圖的完備匹配為止 四、 匹配問題 2022/2/16 四、 匹配問題 調(diào)用 m函數(shù)文件 。 命令形式： [M,MaxZjpp]=km(A,n) 功能： A是輸入二部圖的權(quán)矩陣， n是匹配點。 M— 輸出匹配矩陣 。 MaxZjpp— 輸出最優(yōu)匹配的總長度。 A=[3 5 5 4 1。2 2 0 2 2。2 4 4 1 0。0 1 1 0 0。1 2 1 3 3]。 [M,MaxZjpp]=km(A,5) 2022/2/16 五、 旅行商問題 定義 經(jīng)過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 圖。 定義 包含G的每個頂點的軌叫做 Ha m il t o n ( 哈密頓 ) 軌；閉的 Ha mi l t o n 軌叫做 H a m il t o n 圈或 H 圈；含 Ha m il t o n 圈的圖叫做 Ha mi l t o n 圖。 Euler圖和 Hamilton圖 2022/2/16 五、 旅行商問題 定理 （ i ）G是 E ul e r 圖的充分必要條件是G連通且每頂點皆偶次。 （ ii ）G是 E ul e r 圖的充分必要條件是G連通且?diiCG1??，iC是圈，)()()( jiCECE ji ????。 （ i ii ）G中有 E ul e
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1