3

给定 G，一个有向图，是否存在一条经过 G 中所有顶点的路径（不一定是简单路径）？

我首先需要检查无环图和强连接图中发生的情况，然后使用强连接组件的图找到一般图的解决方案。

到目前为止，我已经发现对于一个强连通图来说总是有一条路径。对于无环图，如果源不止一个，则路径将永远不存在。此外，如果有一个 D out 大于 1 的顶点，则路径将永远不存在。

问题是，我不确定最后一个是正确的，如果它是错误的，我的算法是错误的。

4

1 回答 1

1

最后一个假设不成立，例如看一下图G = (V,E)，其中E = {(v_i,v_j) | i < j }图显然是一个 DAG。所以找到最大的强连通分量不会改变图形。另外-该图具有汉密尔顿路径，但是d_out(v_1) > 1[假设|V| > 3]。

但是 - 你在正确的轨道上。

高级伪代码中的算法：

  1. 在图中找到最大强连通分量 - 结果图是 DAG。
  2. 对结果图1使用拓扑排序。
  3. 检查有序排序是否创建了哈密顿路径
  4. 如果是 - 返回真，否则返回假

宣称：

当且仅当表示图的MSCC的DAG具有汉密尔顿路径时，存在具有所有顶点的路径

索赔证明：
<-
如果有一条汉密尔顿路径 - 那么这样的路径对于每个 MSCC 来说都是微不足道的 - 路径经过所有顶点，然后到达代表我们在汉密尔顿路径中选择的边的外边在 MSCC 图中。
->
如果存在这样的路径，就让它成为v0->v1->...vm。
让我们表示V_i其中的最大强连通分量v_i。
现在，对于原始图中的路径，MSCC 图2v0->v1->...->vm中也有一条路径：。 请注意，如果在上述路径中出现两次 [或更多] - 两次出现彼此相邻，否则找到的 MSCC 不是最大的，因为如果V_0->V_1->...->V_m
V_iV_i->V_k->...->V_i是可行的路径 - 那么 V_i 和 V_k 不是最大的，因为您可以将它们合并成一个更大的 SCC。
现在，对于每一次V_i崩溃，它的所有出现都合二为一，你就会得到一条路径——每一个V_i最多出现一次[我们只是说明了原因]，而且恰好是一个[因为每一个v_i都在原始路径上，我们没有完全删除 MSCC - 只是折叠它们]。
因此 - 生成的路径是 MSCC 图中的哈密顿路径。

建议算法的正确性证明：
由于我们在 MSCC 图中显示哈密顿路径存在当且仅当原始图中存在请求的路径 - 然后：
->
算法返回 true -> 算法在 DAG 中找到了哈密顿路径-> Dag 中有一条哈密顿路径 [脚注 1] -> 原始图中要求有一条路径。
<-
算法返回 false -> 算法在 DAG 中没有找到哈密顿路径 -> DAG 中没有哈密顿路径 [脚注 1] -> 原始路径中没有请求的路径。

量子点

1：在一个DAG中，如果存在hamiltonian路径，则存在唯一的拓扑排序，如果有hamiltonian路径——就是拓扑排序中顶点的顺序。因此，在 DAG 中 - 找到一条汉密尔顿路径很容易。
2：实际上，它有点修改，V_i->V_i不是MSCC上的真正边，图但现在让我们将它表示为一个。

于 2012-04-17T07:21:40.190 回答