Just My Life & My Work

路徑覆蓋 (Path Cover)

前不久在改高演期末考卷,發現一題有趣的題目,給定一個有向圖,請用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。一個路徑集合,這些路徑們會包含圖上所有點,但是這些路徑們之間沒有共同的點。

又可細分為以下三種類型:

  1. Minimum Path Cover (NP-hard)
    一張圖上路徑最少條的Vertex-disjoint Path Cover。
  2. Minimum Path Cover in DAG (P)
    當給定的圖是有向無環圖DAG,得化作Maximum Cardinality Bipartite Matching解決。
  3. 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

隨意留個言吧:)~

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com 標誌

您的留言將使用 WordPress.com 帳號。 登出 /  變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 /  變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 /  變更 )

連結到 %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

標籤雲

%d 位部落客按了讚: