找到访问无向、未加权图中每个节点的最短路线
Finding the shortest route to visit every node in an undirected, unweighted graph
寻找访问无向、未加权图中每个节点的最短路线是 NP-Hard 问题吗？
我找不到关于这个问题的明确答案。我知道找到访问加权图的每个节点的最短路线是一个 NP-Hard 问题（旅行推销员）。但是未加权的图表呢？
假设有一个算法 A 来找到连接无向、未加权图中所有节点的最短路径 G = (V, E) 多项式时间。我们将证明我们可以使用 A 在多项式时间内求解 Hamiltonian path problem ，使用以下步骤：
- 用A得到连接所有节点的最短路径pV
- 统计p包含的节点数；设 k 为节点数
- 令n = |V|； G 包含一个 Hamiltonian path 当且仅当 k = n（见下文证明)
但是，由于汉密尔顿路径问题是 NP-Complete 这样的算法 A 不存在，除非 P = NP。所以你描述的问题一定是NP-Hard。
证明 k = n ⇔ G 包含哈密顿路径
注意 n ≤ k，因为 p 包含 V 中的每个节点。
⇒：假设k = n。由于 p 连接 all 个节点，因此不能多次访问任何节点。因此 G 包含哈密顿路径，即 p.
⇐：假设G包含哈密顿路径。假设 k ≠ n，即 k > n.
A 将不会返回满足我们要求的最短路径，因为具有 n 个节点的哈密顿路径存在。因此，它必须认为 k = n.
∎
寻找访问无向、未加权图中每个节点的最短路线是 NP-Hard 问题吗？
我找不到关于这个问题的明确答案。我知道找到访问加权图的每个节点的最短路线是一个 NP-Hard 问题（旅行推销员）。但是未加权的图表呢？
假设有一个算法 A 来找到连接无向、未加权图中所有节点的最短路径 G = (V, E) 多项式时间。我们将证明我们可以使用 A 在多项式时间内求解 Hamiltonian path problem ，使用以下步骤：
- 用A得到连接所有节点的最短路径pV
- 统计p包含的节点数；设 k 为节点数
- 令n = |V|； G 包含一个 Hamiltonian path 当且仅当 k = n（见下文证明)
但是，由于汉密尔顿路径问题是 NP-Complete 这样的算法 A 不存在，除非 P = NP。所以你描述的问题一定是NP-Hard。
证明 k = n ⇔ G 包含哈密顿路径
注意 n ≤ k，因为 p 包含 V 中的每个节点。
⇒：假设k = n。由于 p 连接 all 个节点，因此不能多次访问任何节点。因此 G 包含哈密顿路径，即 p.
⇐：假设G包含哈密顿路径。假设 k ≠ n，即 k > n.
A 将不会返回满足我们要求的最短路径，因为具有 n 个节点的哈密顿路径存在。因此，它必须认为 k = n.
∎