庫恩一曼克爾斯算法(Kuhn - Munkres algorithm)一種求解最優分派問題的方法。
基本介紹
- 中文名：庫恩一曼克爾斯算法
- 外文名：Kuhn - Munkres algorithm
- 所屬學科：數學
定義
若頂點集X U Y上的實值函式L適合下述條件:對所有的二EX以及yEY，均有L(二)+ L(y)二二，婦，則把這個函式定義為該二部圖的一個可行頂點標號(實數(Lv)稱為頂點v的標號).不管邊的權是什麼，總存在可行點標號.如下述定義的函式L就是這樣的可行點標號:
庫恩一曼克爾斯算法
令E,={xyEE}l(二)十L(y) -二(二，y＞)，具有邊集E，的G的生成子圖稱為對應於可行點標號L的相等子圖，用G，表示.庫恩一曼克爾斯算法建立在如下定理的基礎上:設l是G的可行頂點標號，若以包含完美對集M`，則M‘是G的最優對集.
