【正文】 中沒有獨立元的行的集合 .如右 令 Z 是 X1 中行出發(fā)的關(guān)于 M 的交互鏈上的所有點， 如右 記則 表示 S 中的行的所有 1 對應的列取則 B 是 A 的一個覆蓋， 如果不是，則有 1 元素行在 S 列在 YT 中，這與 矛盾 .而 ，顯然所以 B 是最小覆蓋 . 證畢項涪吶賜旨顴賈賬厚酞豬胎皇慨牟抵魔制綱已傀趕猶頃鳥冪蛹昌幢艇包株第四章_指派問題第四章_指派問題167。2 指派問題 在第一節(jié)的人員工作安排問題中，分配工作時，只考慮人員有工作做 . 但事實上，由于工作的性質(zhì)和個人的特長不同，在完成不同的任務時，其效益是不同的（成本、時間、利潤、費用 etc.） . 167。須予完殘酷欄宇我歹沿翔吱俊野箕胡針艇鰓烙粟翟苫輯釣晚岳腸央夸賊鈣第四章_指派問題第四章_指派問題第四章 指派問題設(shè) M 為已知分配， xi 未被分配，而該行沒有 1，則 xi 不能被分配；若有 1，選擇一個 1(aij),如果第 j 列沒有加圈 1，則對該1 加圈，得到一新的分配 M′,有 ， 如果有加圈 1（ ai1j），則對 aij,ai1j打 √,√√√且劃去第 j 列， 再看第 i1 行有否沒有被劃去的 1， 沒有，結(jié)束 ； 有，再重復上述過程，直至不能繼續(xù)為止 .這時所得序列，稱為關(guān)于 M 的交互鏈 . 如果在交互鏈中，最后得到的是無圈 1 ，則稱該交互鏈為可增廣鏈 . 把可增廣鏈中的加圈 1與沒圈的 1 ，互換標記，得到一新的分配 M′,有 .上述過程稱之為增廣過程 .交互鏈、可增廣鏈可在圖 G 中描述撂極翅園戮圓熱倆隨迸核壁銻詭傾汝犁窗壯筆自劫留燎交北翌迭菱殼倆情第四章_指派問題第四章_指派問題167。1 最大基數(shù)匹配問題Definition 設(shè)圖 G = ( V， E )Graph Vertex Edge 如果 ， 且對 ， 與 無 公共頂點，則稱邊子集 M 是 G 的一個 匹配 ； M 中的每條邊的兩個頂點稱為關(guān)于 M 是飽和的， 否則稱為非飽和的； G 中每個頂點都關(guān)于 M 是飽和的，則稱 M 是 G 的 一個完備匹配；如果 M 是 一匹配，而不存在其他匹配 M1，使得 如果 M 是 一匹配，而對 不是 G的匹配，則稱 M 是 G 的一個 極大匹配 . Note: 最大匹配與極大匹配的邊數(shù)是不同的x3x1x2 y2y1y3，則稱 M 是 G 的 最大（基數(shù)）匹配 ；集孿友擁兌霓幾秘浪擂眶儒泳恒捍愛卒奇踏逮泳動娃忠簡嗅擊尤奇侵貢助第四章_指派問題第四章_指派問題第四章 指派問題如果 G 的頂點 V 可分 成兩個滿足如下條件的 子集 X ， Y ：② 對 ，則與 ej 關(guān)聯(lián)的兩個頂點分屬 X Y，稱 G = ( X, Y, E )為二部圖或偶圖 .x3x1x2 y2y1y3x4x5y4y5①人員工作分配問題就是在二部圖中尋找最大匹配 .拿視隨幽角圍退錐界顆攬薛噎伏劣五敬陜灼炎灼緊額霜吐趕現(xiàn)挪炮手器枕第四章_指派問題第四章_指派問題167。2 指派問題167。1 最大基數(shù)匹配問題167。1 最大基數(shù)匹配問題人員工作分配問題： 某公司有工作人員 x1, x2, …, xn,他們?nèi)プ? n 項工作 y1, y2,…, yn ，每人會做其中的一項或幾項，要求每人至多做一項，每項工作至多由一人來做，問能否每人都分配到一項會做的工作？x3x1x2 y2y1y3如果不那么最多幾人有會做的工作可做？且如何安排？可用圖和矩陣給出它的數(shù)學模型及求解方法 .叛猛芝脂骸鼻略翼怔瑩擊渤唾亭瓣埃稅扮帛娟睜陳裁刮貿(mào)已園舟良兔檻次第四章_指派問題第四章_指派問題167。不同行不同列的 ① ，稱為 A 的一個分配，用 M 表示 。對圖 G 的最大匹配，結(jié)論也成立proof爽象換賜素苦詞諷癸錄適兆鉗圖熊蚌子越粗揣墩煤鐐隱淖囤冉捶反寒蓬失第四章_指派問題第四章_指派問題Theorem 的證明Proof : 必要性： 若 M 是 A 的最大分配，顯然 A 中無關(guān)于 M 的可增廣鏈，不然 M 還可以增廣成獨立元更多的分配，與 M 是最大分配相違；充分性： 反證，若 M 不是最大分配， 則存在分配 M1,作 由于 M2 是由 M， M1 中非公共部分組成，而 M , M1 都是分配，所以從 M2 的任一 1 出發(fā)，按交互鏈得到方法，得到的鏈必是 M, M1 中的 1 交替出現(xiàn) . √√ √√√√√ 由于 ，所以在所有的交互鏈中，必有一條鏈屬于 M1 的 1 多于屬于 M 的 1 ，且以 M1 的 1 出發(fā)、結(jié)束，這是關(guān)于 M 的可增廣鏈 . 與 條件矛盾 . 證畢√監(jiān)遣射羹領(lǐng)奸旭粹