前不久在改高演期末考卷，發現一題有趣的題目，給定一個有向圖，請用minimum path cover為何？之前都沒有學過類似的概念，於是我上往查了些資料，才知道如何解決這一題！
很感激已經有人在網路上寫了這一方面的知識，而且又是我校系的學長，我與有榮焉，於此也在自己的部落格整理自己的想法。
首先當然要瞭解問題的本質「覆蓋(cover)」：是使用一種元件，壓到、甚至是蓋住圖上全部的點（邊）。例如拿一些點，壓到所有邊，叫做 Vertex Cover ；例如拿一些邊，壓到所有點，叫做 Edge Cover 。可以拿路徑來蓋、拿環來蓋、拿 Clique 來蓋、拿 Cut 來蓋，想的到的都可以拿來蓋，款式可說是相當多。有趣的是，以點為主體的問題們，都是 NP 問題；以邊為主體的問題們，都是 P 問題。這就跟 Hamilton Circuit 與 Euler Circuit 的關係一樣奇妙。
而在此，我想瞭解Path Cover，先來瞭解其定義：Path Cover其實就是Vertex-disjoint Path Cover：一張圖上選出數條路徑，這些路徑的點都不重複，並且涵蓋圖上所有點。路徑長度可以為零，也就是退化成一點。可以想做是一張圖抽取出許多條Hamilton Path。一個路徑集合，這些路徑們會包含圖上所有點，但是這些路徑們之間沒有共同的點。
又可細分為以下三種類型：
- Minimum Path Cover (NP-hard)
一張圖上路徑最少條的Vertex-disjoint Path Cover。 - Minimum Path Cover in DAG (P)
當給定的圖是有向無環圖DAG，得化作Maximum Cardinality Bipartite Matching解決。 - Minimum Weight Path Cover (NP-hard)
一張圖上權重總和最小的Path Cover。
而期末考題上的類型就是Minimum Path Cover in DAG (P)，因為有向無環，所以可以用Maximum Cardinality Bipartite Matching來解，舉個例子較好理解：
嘗試建造一張特別的二分圖：若DAG有一條i點到j點的邊，那麼二分圖就有一條Xi點到Yj點的邊。
現在，二分圖的一種Maximum Cardinality Bipartite Matching就會對應到DAG的一種Minimum Path Cover。反之亦同。
在二分圖的集合當中，未匹配點會是路徑尾端點，已匹配點不會是路徑尾端點。當匹配數越大，尾端點就會越少，表示路徑數也會越少。
於是乎，關鍵就在於從Bipartite Graph找到越多匹配數，使得路徑數越少！
話說此題呼應最前面所述，以邊為主體的問題是為P問題。
參考：WiKi – Path cover、演算法筆記 – Cover。
逍遙文工作室 
隨意留個言吧：）～