用生命标记的图形
Graph marking with lives
你得到了一个具有整数节点权重和边权重的无向图。
一个节点是"mark-able"，如果它的节点权重是非负的，并且标记一个节点将导致其所有邻居节点权重减少连接两者的边缘的边缘权重。
如果标记节点的节点权重低于 0，它会自动取消标记（并且它的邻居边权重的减少也被撤消）。
求解尽可能多的标记节点集。
可能更简单的问题：
- 限制边权重为正。
- 限制边的权重全部为1。
- 求解解集的大小而不是集本身。
这个问题可以在多项式时间内解决吗？最佳解决方案是什么？
实际上，这听起来像是 minimum vertex cover 问题的概括，已知该问题是 NP 完全问题。
确实，考虑一个图，其中顶点的权重为 0，边的权重为 1。
对于每条边，我们最多可以标记它的一个端点：否则，它们的权重都将变为负数。
这个 属性 也是倒退的，这意味着 "single marked endpoint" 属性 之后的任何一组标记也是一个解决方案。
这意味着我们要标记尽可能多的顶点集，以便每条边最多连接到一个标记的顶点。
反过来，这意味着我们想要找到尽可能小的一组 unmarked 顶点，以便每条边连接到至少一个 unmarked 顶点。
考虑到没有孤立的顶点，听起来 未标记 顶点是最小顶点覆盖。
你得到了一个具有整数节点权重和边权重的无向图。
一个节点是"mark-able"，如果它的节点权重是非负的，并且标记一个节点将导致其所有邻居节点权重减少连接两者的边缘的边缘权重。 如果标记节点的节点权重低于 0，它会自动取消标记（并且它的邻居边权重的减少也被撤消）。
求解尽可能多的标记节点集。
可能更简单的问题：
- 限制边权重为正。
- 限制边的权重全部为1。
- 求解解集的大小而不是集本身。
这个问题可以在多项式时间内解决吗？最佳解决方案是什么？
实际上，这听起来像是 minimum vertex cover 问题的概括，已知该问题是 NP 完全问题。
确实，考虑一个图，其中顶点的权重为 0，边的权重为 1。 对于每条边，我们最多可以标记它的一个端点：否则，它们的权重都将变为负数。 这个 属性 也是倒退的，这意味着 "single marked endpoint" 属性 之后的任何一组标记也是一个解决方案。 这意味着我们要标记尽可能多的顶点集，以便每条边最多连接到一个标记的顶点。 反过来，这意味着我们想要找到尽可能小的一组 unmarked 顶点，以便每条边连接到至少一个 unmarked 顶点。 考虑到没有孤立的顶点，听起来 未标记 顶点是最小顶点覆盖。