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