最大权闭合子图

发布时间：2023-05-19

一、最大权闭合子图算法

最大权闭合子图指的是在一个有向加权图中，选取一个子图，使得子图中每个点都有至少一个后继节点在该子图中，并且选取的子图的所有点的权重和最大。 最大权闭合子图算法可以使用线性规划、贪心算法、网络流等多种方法求解，这里介绍一种基于二分图匹配的贪心算法。 假设原图为 $G=(V,E),w:V\rightarrow R$ 是每个点的权重，闭合约束 $\delta(s):S\rightarrow{0,1}$，表示该子图不能包含集合 $S$ 中的点。则最大权闭合子图可以表示为以下线性规划问题： $$ \text{Maximize } \sum_{v\in V}{w(v)x(v)} $$ $$ \text{Subject to } \sum_{v\in \delta(S)}x(v) \geq 1 \text{ for all } S\subseteq V \text{ and } \delta(S) \neq \emptyset $$ $$ x(v) \in {0,1} \text{ 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$ 就是最大权闭合子图的点集。

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

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$ 的节点建立的虚拟节点转化为最大权闭合子图问题来解决。

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 中节点数减去选中的节点数。

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)
推荐文章