最小路徑覆蓋

一個PXP的有向圖中，路徑覆蓋就是在圖中找一些路徑，使之覆蓋了圖中的所有頂點，且任何一個頂點有且只有一條路徑與之關聯；（如果把這些路徑中的每條路徑從它的起始點走到它的終點，那麼恰好可以經過圖中的每個頂點一次且僅一次）；如果不考慮圖中存在迴路，那麼每條路徑就是一個弱連通子集．

由上面可以得出：

1.一個單獨的頂點是一條路徑；

2．如果存在一路徑p1,p2,......pk，其中p1 為起點，pk為終點，那麼在覆蓋圖中，頂點p1,p2,......pk不再與其它的頂點之間存在有向邊．

對於一個路徑覆蓋，有如下性質：

1、每個頂點屬於且只屬於一個路徑。

2、路徑上除終點外，從每個頂點出發只有一條邊指向路徑上的另一頂點。

路徑覆蓋與二分圖匹配的關係（必須是有向無環圖）：

最小路徑覆蓋=|P|－最大匹配數

其中最大匹配數的求法是把P中的每個頂點pi分成兩個頂點pi'與pi''，如果在p中存在一條pi到pj的邊，那麼在二分圖P'中就有一條連接pi'與pj''的無向邊；這裏pi' 就是p中pi的出邊，pj''就是p中pj 的一條入邊；

對於公式：最小路徑覆蓋=|P|－最大匹配數；可以這麼來理解；

如果匹配數為零，那麼P中不存在有向邊，於是顯然有：

最小路徑覆蓋=|P|－最大匹配數=|P|－0=|P|；即P的最小路徑覆蓋數為|P|；

P'中不在於匹配邊時，路徑覆蓋數為|P|；

如果在P'中增加一條匹配邊pi'－－＞pj''，那麼在圖P的路徑覆蓋中就存在一條由pi連接pj的邊，也就是説pi與pj 在一條路徑上，於是路徑覆蓋數就可以減少一個；

如此繼續增加匹配邊，每增加一條，路徑覆蓋數就減少一條；直到匹配邊不能繼續增加時，路徑覆蓋數也不能再減少了，此時就有了前面的公式；但是這裏只 是説明了每條匹配邊對應於路徑覆蓋中的一條路徑上的一條連接兩個點之間的有向邊；下面來説明一個路徑覆蓋中的每條連接兩個頂點之間的有向邊對應於一條匹配 邊；

與前面類似，對於路徑覆蓋中的每條連接兩個頂點之間的每條有向邊pi---＞pj，我們可以在匹配圖中對應做一條連接pi'與pj''的邊， 顯然這樣做出來圖的是一個匹配圖（這一點用反證法很容易證明，如果得到的圖不是一個匹配圖，那麼這個圖中必定存在這樣兩條邊 pi'---pj'' 及 pi' ----pk''，（j!=k），那麼在路徑覆蓋圖中就存在了兩條邊pi--＞pj, pi---＞pk ，那邊從pi出發的路徑就不止一條了，這與路徑覆蓋圖是矛盾的；還有另外一種情況就是存在pi'---pj'',pk'---pj''，這種情況也類似可證）；

至此，就説明了匹配邊與路徑覆蓋圖中連接兩頂點之間邊的一一對應關係，那麼也就説明了前面的公式成立！