本文證明如下：最小路徑覆蓋=|G|-二分圖的最大匹配。

參考鏈接：http://baike.baidu.com/view/2444809.htm

（1）什么是有向圖G的最小路徑覆蓋？首先，圖G必須是有向無環的。路徑覆蓋就是在圖G中找出一些路徑，每條路徑從起點走到終點并且標記中間經過的點。最后，每個點只被標記一次。選出的這些路徑組成路徑覆蓋。如果找出最少的路徑成為一個路徑覆蓋，則稱為最小路徑覆蓋。

在上圖中,以下兩個均是路徑覆蓋：

a、<1,2> <4,6> <3> <5>

b、<1,2,4,6> <3> <5>

但是<1,2,4,6> <3,2,4,6>則不是一個路徑覆蓋，因為2,4被標記兩次。在上面兩個覆蓋中b為最小覆蓋，|b|=3,而|a|=4。（注意一個單獨的節點也是一個路徑）

（2）由原圖G構造對應的二分圖S，將原圖G中的每個點i拆成兩個點i1和i2，i1和i2屬于S。i1組成二分圖的X集合，i2組成Y集合。若原圖G中有邊<i,j>，則在S中有邊<i1,j2>，則上面的圖可以得到如下二分圖：

（3）定理證明：如果匹配數為零，那么P中不存在有向邊，于是顯然有最小路徑覆蓋=|G|－最大匹配數=|G|。在匹配數為0的基礎上，即S中一條邊沒有，如果在S中增加一條匹配邊(i1,j2)，那么在圖G的路徑覆蓋中就存在一條由i連接j的邊，也就是說i與j 在一條路徑上，于是路徑覆蓋數就可以減少一個；如此繼續增加匹配邊，每增加一條，路徑覆蓋數就減少一條；直到匹配邊不能繼續增加時，路徑覆蓋數也不能再減少了；但是這里只 是說明了每條匹配邊對應于路徑覆蓋中的一條路徑上的一條連接兩個點之間的有向邊；下面來說明一個路徑覆蓋中的每條連接兩個頂點之間的有向邊對應于一條匹配 邊。與前面類似，對于路徑覆蓋中的每條連接兩個頂點之間的每條有向邊<i,j>，我們可以在匹配圖中對應作一條連接i1與j2的邊， 顯然這樣做出來二分圖中的邊均為匹配，即連接的X和Y中的兩個點之前都未匹配過，否則匹配過的那個點對應原圖時就被覆蓋兩次，與路徑覆蓋矛盾。這就說明匹配邊與路徑覆蓋圖中連接兩頂點之間邊的一一對應關系，那么也就說明了前面的公式成立，即S中每增加一條匹配邊，路徑覆蓋數減少1.

總結

以上是生活随笔為你收集整理的有向图最小路径覆盖的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。