algorithm - 一个有趣的图形任务

Question

有一棵有n个顶点的树。我们被要求计算多重集 S 的最小大小，例如树中的每条边 (u,v) 至少满足以下条件之一:

• u ∈ S
• v∈S
• S中至少有两个顶点，每个顶点都与u或v相邻。

由于 S 是一个多重集，一个顶点可能多次出现在 S 中。

我的直觉如下。首先，我们考虑以下事实:在最优解中，每个顶点至多在 S 中两次。所以我们可以后序遍历树，计算顶点不在最优S、一次在一次和两次在三种情况下的结果。

不幸的是，我无法链接子问题之间的关系，我不确定这个想法是否正确。

欢迎提供提示或引用。非常感谢。

Answer 1

像这样表示树(未经测试的 Haskell)。

> data Tree a = Node a
>             | Cons (Tree a) (Tree a)

树

  1
 /|\
2 3 4
  |
  5

是

(Cons (Node 2)
      (Cons (Cons (Node 5) (Node 3))
            (Cons (Node 4) (Node 1)))) :: Tree Int .

这是一个自下而上的验证函数。

> type ZeroOneOrTwo = Int
> data Result = Failure
>             | Success { numDist0Provided :: ZeroOneOrTwo
>                       , numDist1Provided :: ZeroOneOrTwo
>                       , numDist1Required :: ZeroOneOrTwo
>                       }
>
> plus, minus :: ZeroOneOrTwo -> ZeroOneOrTwo -> ZeroOneOrTwo
> x `plus` y = min 2 (x + y)
> x `minus` y = max 0 (x - y)
>
> evaluate :: Tree ZeroOneOrTwo -> Bool
> evaluate t = case evaluate' t of
>   Failure -> False
>   s -> 0 == numDist1Required s
>
> evaluate' :: Tree ZeroOneOrTwo -> Result
> evaluate' (Node x) = Success { numDist0Provided = x
>                              , numDist1Provided = 0
>                              , numDist1Required = 0
>                              }
> evaluate' (Cons t1 t2) = case (evaluate' t1, evaluate' t2) of
>   (Failure, _) -> Failure
>   (_, Failure) -> Failure
>   (s1, s2) ->
>     if numDist0Provided s2 < numDist1Required s1 then Failure
>       else Success { numDist0Provided = numDist0Provided s2
>                    , numDist1Provided = numDist1Provided s2 `plus` numDist0Provided s1
>                    , numDist1Required = max (numDist1Required s2 `minus` numDist0Provided s1)
>                                           (if 0 < numDist0Provided s1 || 0 < numDist0Provided s2 then 0
>                                              else 2 `minus` (numDist1Provided s1 `plus` numDist1Provided s2))
>                    }

我将把相应的线性时间 DP 作为练习。