最小顶点覆盖

最小顶点覆盖是一个经典的图形问题。比方说,在一个城市,我们有几条连接几个点的道路。让我们使用边和使用节点的点来表示道路。我们来看两个示例图:

https://i.stack.imgur.com/7n7bv.jpg

我们想在某些方面设置守望者。守望者可以保护连接到该点的所有道路。问题是,覆盖所有道路所需的最小守望人员是多少?如果我们在节点 ABHIJ 设置守望者,我们可以覆盖所有道路。

https://i.stack.imgur.com/ADM8O.jpg

这是我们的最佳解决方案。我们至少需要 5 名守望者才能守护整个城市。怎么判断这个?

首先,我们需要理解这是一个 *NP 难*问题,即问题没有多项式时间解决方案。但是如果图形是,那意味着如果它有 (n-1)个节点,其中 n 是边数,并且图中没有循环,我们可以使用动态编程来解决它。

https://i.stack.imgur.com/YvGHM.jpg

要构建 DP 解决方案,我们需要遵循两个策略:

  1. 如果节点中没有守望者,则连接到它的所有节点都必须有守望者,否则所有道路都不会被覆盖。如果 Uv 连接和 U 没有任何守望者,那么 v 必须有一个守望者。
  2. 如果节点中有守望者,则与其连接的不同节点可能有也可能没有守望者。这意味着没有必要有一个守望者,但它可能是有益的。如果 Uv 连接和 U 有守望,我们会检查,发现其上是对我们有利的:
    • v 。中设置守望者
    • 不在 v 中设置守望者。

让我们定义一个递归函数,其中 state 是我们当前的节点,是否有守望者。这里:

F(u,1) = Currently we're in 'u' node and there is a watchman in this node.
F(u,0) = Currently we're in 'u' node and there is no watchman in this node.

该函数将返回剩余节点中的守望者数量。

我们来看一个示例树:

https://i.stack.imgur.com/rka2p.jpg

我们可以很容易地说,如果我们不把守望者放在节点 A 上,我们就必须把守望者放在节点 BCD 上。我们可以推断:

F(A,0) = F(B,1) + F(C,1) + F(D,1) + 0

如果我们不将守望者放在节点 A 中,它会返回所需的守望人数。我们最后添加了 0 ,因为我们没有在当前节点中设置任何守望者。

现在 F(A,1) 意味着,我们在节点 A 中设置了守望者。为此,我们可以在所有连接的节点中设置看门人,也可以不设置。我们将为我们提供最少数量的守望者。

F(A,1) = min(F(B,0), F(B,1) + min(F(C,0), F(C,1)) + min(F(D,0), F(D,1)) + 1

我们通过设置而不是在每个节点上设置守望者并获取最佳值来检查。

我们必须要注意的一件事是,一旦我们进入子节点,我们将永远不会回顾父节点。从上面的例子中,我们去 BA,因此父[B] = A。因此,我们将不会再回到一个B

为了确定基本情况,我们可以注意到,如果从一个节点,我们不能去任何其他新节点,如果我们当前节点中有一个守望者,我们将返回 1,如果我们当前没有守望者,则返回 0 节点。

最好有一个树的邻接列表。让列表用 edge 表示。我们将有一个数组 dp [n] [2] ,其中 n 表示存储计算值的节点数,并用 -1 初始化它。我们还将有一个 parent [n] 数组来表示节点之间的父子关系。我们的伪代码看起来像:

Procedure f(u, isGuarded):
if edge[u].size is equal to 0                    //node doesn't have any new edge
    Return isGuarded
else if dp[u][isGuarded] is not equal to -1      //already calculated
    Return dp[u][isGuarded]
end if
sum := 0
for i from i to edge[u].size
    v := edge[u][i]
    if v is not equal to parent[u]               //not a parent
        parent[v] := u
        if isGuarded equals to 0                 //not guarded, must set a watchman
            sum := sum + f(v,1)
        else                                     //guarded, check both
            sum := sum + min(f(v,1), f(v,0)
        end if
    end if
end for
dp[u][isGuarded] := sum + isGuarded
Return dp[u][isGuarded]

如果我们将节点 A 表示为 root,我们将通过:min(f(A,1), f(A,0)) 调用该函数。这意味着我们还将检查在根节点中设置 watchman 是否最佳。这是我们的 DP 解决方案。使用最大匹配算法或 max-flow 也可以解决此问题。