假設(shè)G經(jīng)過匈牙利算法后找到一個最大匹配M，則可知G中再也找不到一條增廣路徑。
標(biāo)記右邊未匹配邊的頂點，并從右邊未匹配邊的頂點出發(fā)，按照邊：未匹配->匹配->未匹配...，的原則標(biāo)記途中經(jīng)過的頂點，則最后一條經(jīng)過的邊必定為匹配邊。重復(fù)上述過程，直到右邊不再含有未匹配邊的點。
記得到的左邊已標(biāo)記的點和右邊未標(biāo)記的點為S， 以下證明S即為所求的最小頂點集。
1。| S | == M
顯然，左邊標(biāo)記的點全都為匹配邊的頂點，右邊未標(biāo)記的點也為匹配邊的頂點。因此，我們得到的點與匹配邊一一對應(yīng)。
2。S能覆蓋G中所有的邊。
上途S中點所得到的邊有以下幾種情況：
（1）左右均標(biāo)記；
（2）左右均無標(biāo)記；
（3）左邊標(biāo)記，右邊未標(biāo)記；
若存在一條邊e不屬于S所覆蓋的邊集，則e 左邊未標(biāo)記右邊標(biāo)記。
如果e不屬于匹配邊，那么左端點就可以通過這條邊到達(dá)（從而得到標(biāo)記）；如果e屬于匹配邊，那么右端點不可能是一條路徑的起點，于是它的標(biāo)記只能是從這條邊的左端點過來的左端點就應(yīng)該有標(biāo)記。
3。S是最小的覆蓋。
因為要覆蓋這M條匹配邊至少就需要M個點。
轉(zhuǎn)自:http://yejingx.ycool.com/post.2801156.html#
在一個ＰＸＰ的有向圖中，路徑覆蓋就是在圖中找一些路經(jīng)，使之覆蓋了圖中的所有頂點，且任何一個頂點有且只有一條路徑與之關(guān)聯(lián)；（如果把這些路徑中的每條路徑從它的起始點走到它的終點，那么恰好可以經(jīng)過圖中的每個頂點一次且僅一次）；如果不考慮圖中存在回路，那么每每條路徑就是一個弱連通子集．
由上面可以得出：
１.一個單獨的頂點是一條路徑；
２．如果存在一路徑p1,p2,......pk，其中p1 為起點，pk為終點，那么在覆蓋圖中，頂點p1,p2,......pk不再與其它的頂點之間存在有向邊．
最小路徑覆蓋就是找出最小的路徑條數(shù)，使之成為Ｐ的一個路徑覆蓋．
路徑覆蓋與二分圖匹配的關(guān)系：
最小路徑覆蓋＝｜Ｐ｜－最大匹配數(shù)；
其中最大匹配數(shù)的求法是把Ｐ中的每個頂點pi分成兩個頂點pi'與pi''，如果在p中存在一條pi到pj的邊，那么在二分圖Ｐ＇中就有一條連接pi'與pj''的無向邊；這里pi' 就是p中pi的出邊，pj''就是p中pj 的一條入邊；
對于公式：最小路徑覆蓋＝｜Ｐ｜－最大匹配數(shù)；可以這么來理解；
如果匹配數(shù)為零，那么Ｐ中不存在有向邊，于是顯然有：
最小路徑覆蓋＝｜Ｐ｜－最大匹配數(shù)＝｜Ｐ｜－０＝｜Ｐ｜；即Ｐ的最小路徑覆蓋數(shù)為｜Ｐ｜；
Ｐ＇中不在于匹配邊時，路徑覆蓋數(shù)為｜Ｐ｜；
如果在Ｐ＇中增加一條匹配邊pi'－－＞pj''，那么在圖P的路徑覆蓋中就存在一條由pi連接pj的邊，也就是說pi與pj 在一條路徑上，于是路徑覆蓋數(shù)就可以減少一個；
如此繼續(xù)增加匹配邊，每增加一條，路徑覆蓋數(shù)就減少一條；直到匹配邊不能繼續(xù)增加時，路徑覆蓋數(shù)也不能再減少了，此時就有了前面的公式；但是這里只 是說話了每條匹配邊對應(yīng)于路徑覆蓋中的一條路徑上的一條連接兩個點之間的有向邊；下面來說明一個路徑覆蓋中的每條連接兩個頂點之間的有向邊對應(yīng)于一條匹配 邊；
與前面類似，對于路徑覆蓋中的每條連接兩個頂點之間的每條有向邊pi--->pj，我們可以在匹配圖中對應(yīng)做一條連接pi'與pj''的邊， 顯然這樣做出來圖的是一個匹配圖（這一點用反證法很容易證明，如果得到的圖不是一個匹配圖，那么這個圖中必定存在這樣兩條邊 pi'---pj'' 及 pi' ----pk''，（j!=k），那么在路徑覆蓋圖中就存在了兩條邊pi-->pj, pi--->pk ，那邊從pi出發(fā)的路徑就不止一條了，這與路徑覆蓋圖是矛盾的；還有另外一種情況就是存在pi'---pj'',pk'---pj''，這種情況也類似可證）；
至此，就說明了匹配邊與路徑覆蓋圖中連接兩頂點之間邊的一一對應(yīng)關(guān)系，那么也就說明了前面的公式成立！
轉(zhuǎn)自:http://hi.baidu.com/cjhh314/blog/item/ded8d31f15d7510c304e1591.html