2

没有限制，您只能穿过每条边一次或每个顶点。

是否存在图的某些属性对于这样的路径的存在是必要和充分的（例如欧拉路径存在的节点度数），或者证明存在或不存在的某些已知算法（也许从起点找到通过所有边的最小路径）？

我考虑了几种可能性，其中最强的是将强连接的组件折叠成单个超节点，然后检查结果图是否只是一个覆盖所有边的“链表”式图（这很简单，只需从起始节点/超级节点总是从当前节点谈论一条边，计算出边（以及任何内部边，如果它是超级节点）被访问，当你到达叶节点时查看是否所有边都被计算在内）。在这个解决方案中，重要的是保留所有原始边，即使它们变得多余（例如，如果在将连接的组件 A、B、C 折叠到超节点 S 后，从 F 到 A、F 到 B、F 到 C 的边必须即使它们在简化图中指向同一个超节点 S，也都是守恒的）。抱歉，如果表达不正确，

有没有更简单的方法？或者一些更好的算法来处理循环/连接的组件？因为当图是非循环的时，它似乎很容易解决。

4

1 回答 1

2

如果图是强连接的，那么您可以从每个其他节点到达每个节点。由于您可以在此路径中重用边缘，因此您必须可以使用每条边缘。采取一些优势，e。e通向一个节点v，您随后可以从该节点到达每个其他顶点，因此可以到达所有其他边。从这些，你可以回到v。根据需要重复。

因此，要回答这个问题，图是否有一些属性可以保证这样一条路径的存在……如果图是强连接的，我会说是的。（请注意，尽管这样的路径不需要这样做 - 例如，在没有分支的单个单向路径的情况下）。但这似乎是唯一的边缘情况（我能想到的）。

强连接性测试可以通过蛮力检查所有方法轻松完成。我相信您也可以为此调整最大流量、最小切割算法。

于 2013-03-20T04:05:22.670 回答