DAG的最小路徑覆蓋和二分圖的最大匹配 DAG的最小路徑覆蓋是指找最小數(shù)目的互相不相交的有向路徑,滿足DAG的所有頂點(diǎn)都被覆蓋.

首先給出公式:DAG的最小路徑覆蓋數(shù)=DAG圖中的節(jié)點(diǎn)數(shù)-相應(yīng)二分圖中的最大匹配數(shù).

那么對應(yīng)一個DAG,如何構(gòu)造相應(yīng)的二分圖?對于DAG中的一個頂點(diǎn)p,二分圖中有兩個頂點(diǎn)p和p',對應(yīng)DAG中的一條有向邊p->q,二分圖中有p-q'的一條無向邊.二分圖中p屬于S集合,p'屬于T集合. 下面我們來解釋上面公式為什么成立,思路參考baihacker神牛:

上圖中,對應(yīng)左邊的DAG建立構(gòu)造右邊的二分圖,可以找到二分圖的一個最大匹配M:1-3',3-4',那么M中的這兩條匹配邊怎樣對應(yīng)DAG中的路徑的邊? 使二分圖中一條邊對應(yīng)DAG中的一條有向邊,1-3'對應(yīng)DAG圖中的有向邊1->3,這樣DAG中1就會有一個后繼頂點(diǎn)(3會是1的唯一后繼,因?yàn)槎謭D中一個頂點(diǎn)至多關(guān)聯(lián)一條邊!),所以1不會成為DAG中一條路徑中的結(jié)尾頂點(diǎn),同樣,3-4'對應(yīng)DAG中3->4,3也不會成為結(jié)尾頂點(diǎn),那么原圖中總共4個頂點(diǎn),減去2個有后繼的頂點(diǎn),就剩下沒有后繼的頂點(diǎn),即DAG路徑的結(jié)尾頂點(diǎn),而每個結(jié)尾頂點(diǎn)正好對應(yīng)DAG中的一條路徑,二分圖中尋找最大匹配M,就是找到了對應(yīng)DAG中的非路徑結(jié)尾頂點(diǎn)的最大數(shù)目,那么DAG中頂點(diǎn)數(shù)-|M|就是DAG中結(jié)尾頂點(diǎn)的最小數(shù)目,即DAG的最小路徑覆蓋數(shù). posted on 2011-05-12 01:33?Jackiesteed 閱讀(...) 評論(...) 編輯 收藏

轉(zhuǎn)載于:https://www.cnblogs.com/jackiesteed/articles/2043934.html

總結(jié)

以上是生活随笔為你收集整理的DAG的最小路径覆盖和二分图的最大匹配的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。