1

给定图的任意两个顶点之间的 m 条最短路径。确定我们是否可以选择 k 条最短路径，使得它们的并集覆盖所有边。

我确信减少必须来自固定的掩护，但我没有办法将其减少到这个问题。请帮帮我

4

2 回答 2

2

提示：看下图。从 A 到 B 有很多不同的最短路径。你能用这样的图和一组路径对集合覆盖进行编码吗？（好吧，您可能需要稍微修改一下图表，但这是一般的想法）。

   o     o     o     o     o     o     o     o     o     o     o     o     o
  / \   / \   / \   / \   / \   / \   / \   / \   / \   / \   / \   / \   / \
A     o     o     o     o     o     o     o     o     o     o     o     o     B
  \ /   \ /   \ /   \ /   \ /   \ /   \ /   \ /   \ /   \ /   \ /   \ /   \ /
   o     o     o     o     o     o     o     o     o     o     o     o     o
于 2016-12-02T15:54:35.053 回答
1

更新并不知道套装封面也是 NP 完整的。不需要做任何事情来将原件放入确切的封面，所以我所做的 wlog 假设是不必要的。但我也意识到我证明的基本思想是错误的：它表明当前问题是另一个问题的特例，这使它更容易，而不是更难。mjqxxxx在https://math.stackexchange.com/q/2047262给出了完整且正确的答案。

让我们假设没有单个顶点属于超过 1 个路径（即路径对应于不同的顶点集）。

那么这个问题是一个精确覆盖问题（它是 NP 完全问题）扩展为找到所有精确覆盖而不是只找到任何一个（然后检查其中一个是否具有精确k元素 - 这种检查在一般情况下有点棘手）。https://en.wikipedia.org/wiki/Exact_cover https://en.wikipedia.org/wiki/Set_cover_problem

集合X包含图的所有顶点，集合S包含对应于给定路径集合的顶点集合。

于 2016-12-05T07:33:11.700 回答