最大權閉合子圖

一、最大權閉合子圖算法

最大權閉合子圖指的是在一個有向加權圖中，選取一個子圖，使得子圖中每個點都有至少一個後繼節點在該子圖中，並且選取的子圖的所有點的權重和最大。

最大權閉合子圖算法可以使用線性規劃、貪心算法、網絡流等多種方法求解，這裡介紹一種基於二分圖匹配的貪心算法。

假設原圖為 $G=(V,E),w:V\rightarrow R$ 是每個點的權重，閉合約束 $\delta(s):S\rightarrow{0,1}$，表示該子圖不能包含集合 $S$ 中的點。則最大權閉合子圖可以表示為以下線性規劃問題：

Maximize $\sum_{v\in V}{w(v)x(v)} $

Subject to $\sum_{v\in \delta(S)}x(v) \geq 1 $ for all $S\subseteq V$ and $\delta(S) \neq \emptyset $

$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$ $ x(v) \in \{0,1\} $ for all $v\in V$

其中 $x(v)$ 表示點 $v$ 是否被選中。

觀察上面的線性規劃問題，發現如果能找到一個最大匹配 $M$ ，滿足匹配的邊 $(u,v) \in M$，則說明 $u$ 要被選中，$v$ 不選中。

因此，我們可以將原圖變成一個二分圖 $G_{bipartite}=(L,R,E^\prime)$，其中 $L=\{v\in V \mid \delta(v) \neq \emptyset\}$，$R=\{s\}\cup\{v\in V \mid \delta(v) = \emptyset\}$，$E^\prime=\{(u,v)\mid u,v\in V,(u,v)\in E \}$。

我們對二分圖 $G_{bipartite}$ 進行最大匹配 $M$，則選中的點集為 $S=\{v \in L \mid (s,v) \notin M \lor (v,s) \in M \}$。$S$ 就是最大權閉合子圖的點集。

代碼示例：

“`python
def find_max_weight_closed_subgraph(G, w):
L = [v for v in G if any([u not in G[v] for u in G])]
R = [‘s’] + [v for v in G if v not in L]
G_bipartite = {u:{v for v in G[u] if v in R} for u in L}
M = max_weight_matching(G_bipartite, w)
S = set([v for v in L if ‘s’ in M[v]] + [v for v in L if ‘s’ not in M[v]])
return S
“`

二、最大權閉合子圖算法題

問題描述：給定一張有向加權圖，求解最大權閉合子圖。

給定一張有向加權圖 $G=(V,E,w)$，其中 $w:V\rightarrow R$ 是點的權重，為每個點指定一個閉合集合 $\delta(v)$，表示該點不能被選中的條件。請你設計一個算法，從 $G$ 中選取一個子圖，滿足以下條件：

1. 選中的子圖需要包含有向閉合子圖 $\delta(v)$ 中的所有點。
2. 子圖中每個點都至少有一個後繼節點在子圖中。
3. 子圖的權重和最大。

輸入格式：

第一行包含兩個整數 $n$ 和 $m$，表示圖中點數和邊數。

接下來 $m$ 行每行三個整數 $u, v, c$，表示一條從 $u$ 指向 $v$，邊權為 $c$ 的邊。

接下來一行包含 $n$ 個整數，其中第 $i$ 個整數表示點 $v_i$ 所對應的閉合集合 $\delta(v_i)$ 的大小 $k$，接下來的 $k$ 個整數 $d_{i,1}\cdots d_{i,k}$ 表示閉合集合 $\delta(v_i)$ 中的點。

輸出格式：

一行一個整數，表示最大權閉合子圖的權重和。

輸入樣例1：

4 5
1 2 2
1 3 3
2 3 1
2 4 4
3 4 1
2 1
0
1 3
0

輸出樣例1：

5

代碼示例：

“`python
n, m = map(int, input().split())

# 構建圖
G = {i:{} for i in range(1, n+1)}
w = {}
for i in range(m):
u, v, c = map(int, input().split())
G[u][v] = c

# 讀取閉合集合
closed_sets = []
for i in range(n):
closed_set = set(map(int, input().split()[1:]))
closed_sets.append(closed_set)

# 尋找最大權閉合子圖
S = find_max_weight_closed_subgraph(G, w)

# 計算權重和
res = 0
for v in S:
res += w[v]

print(res)
“`

三、最大權閉合圖

最大權閉合子圖算法可以擴展到最大權閉合圖問題，最大權閉合圖問題指定起始節點 $s$，求取一個子圖，使得子圖中每個點都有至少一個後繼節點在該子圖中，同時選取的子圖的所有點的權重和最大，路徑必須以 $s$ 為起始節點。

最大權閉合圖問題可以通過引入超級源點 $s$，並把 $s$ 指向所有出度為 $0$ 的節點建立的虛擬節點轉化為最大權閉合子圖問題來解決。

代碼示例：

“`python
def find_max_weight_closure(G, w, s):
supersource = ‘s’
G[supersource] = {u for u in G if not G[u]}
for u in G:
if not G[u]:
G[u].add(supersource)
G[supersource][u] = w[u]

S = find_max_weight_closed_subgraph(G, w)

if supersource in S:
S.remove(supersource)
return S
“`

四、最小路徑覆蓋

最大權閉合圖算法還可以應用於最小路徑覆蓋問題。最小路徑覆蓋問題指定起始節點 $s$，在 DAG 中選取一個最小的節點集合 $C$，使得該 DAG 中所有從 $s$ 到某個節點 $v$ 的路徑上至少包含一個 $C$ 中的節點。

最小路徑覆蓋問題可以通過引入超級源點 $s$，並把 $s$ 指向所有入度為 $0$ 的節點建立的虛擬節點轉化為最大權閉合子圖問題來解決。最小路徑覆蓋數量就是 DAG 中節點數減去選中的節點數。

代碼示例：

“`python
def min_path_cover(G, s):
supersink = ‘t’
G[supersink] = {}
for u in G:
if u == s:
continue
G[supersink][u] = 1

S = find_max_weight_closure(G, {u:0 for u in G}, supersink)

return len(G) – len(S)
“`