Closure

Closure

「閉包」。導出子圖,沒有聯外邊。可能有許多個。

Minimum Closure / Maximum Closure

「最小閉包」。點數最少的閉包,即是空圖,缺乏討論意義。

「最大閉包」。點數最多的閉包,即是原圖,缺乏討論意義。

無向圖的情況下,閉包是連通分量,缺乏討論意義。

有向圖的情況下,收縮強連通分量,得到DAG,容易找閉包。

Maximum Weight Closure

「最大權閉包」。一張圖上,點有權重、邊無權重,點的權重總和最大的閉包。只有唯一一個。

無向圖演算法:權重最大的連通分量。

有向圖演算法:重新打造一張網路流量圖,求最小源匯割。我不知道為什麼這樣做,真是不好意思。

新增源點、匯點。源點連向所有正點,容量是正點權重;所有負點連向匯點,容量是負點權重變號;原圖的邊,容量是無限大。

最小源匯割不會包含容量無限大的邊。也就是說,源點側到匯點側,沒有容量無限大的邊、沒有原圖的邊。源點側沒有連外邊。源點側是閉包。源點側去掉源點即是最大權閉包。

PKU 2987 3155

Transitive Closure

Transitive Closure

一張圖的「遞移閉包」也是一張圖,用來記錄由一點能不能走到另一點的關係,如果能走到,則兩點之間以邊相連。

兩種演算法:

一、每個點分別做為起點,各做一次Graph Traversal。時間複雜度為O(VE)。

二、使用Dynamic Programming。時間複雜度為O(V³),空間複雜度為O(V²)。

tc(i, j, k) = tc(i, k, k-1) && tc(k, j, k-1) || tc(i, j, k-1)
              ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^    ^^^^^^^^^^^^^
              經過第k點                         沒有經過第k點

tc(i, j, k):由i點能不能走到j點。中繼點只能是第0點到第k點。

UVa 280 12017

Transitive Reduction

Transitive Reduction(Equivalent Graph)

「遞移縮減」。子圖,維持所有點對的連通關係,Transitive Closure保持不變。

Minimum Transitive Reduction(Minimum Equivalent Graph)

保留盡量少的邊、刪除盡量多的邊,讓Transitive Closure保持不變。

無向圖:生成森林,可能有許多種。時間複雜度O(V+E)。

有向圖:NP-hard。

有向無環圖:只有唯一一種。計算所有點對的最長路徑長度,保留長度是1的點對的邊。V次單源最長路徑,時間複雜度O(VE)。