如何确定有向图是否有一条从某个节点开始消耗所有边的路径？
没有任何限制，你必须跨越每条边，只有一次，或每一个顶点。
图中是否有这样一条路径存在的必要条件和充分性(如欧拉路径存在的节点度)，还是证明有或没有这样一条路径的已知算法(也许从起始路径的所有边求出最小路径)？
我已经考虑了几种可能性，其中最强的是将强连接的组件折叠成单个超级节点，然后检查生成的图是否只是覆盖所有边缘的“链接列表”-like图(这很简单，只是从起始节点/超级节点走过来，总是从当前节点中说出一条边，计算访问时的传出边缘(以及任何内部边缘，如果它是超级节点)，当您到达叶节点时，查看是否所有边都被计数)。在这种解决方案中，保存所有原始边是很重要的，即使它们变得多余(例如，在将连通的分量A、B、C折叠成超节点S之后，从F到A、F到B、F到C的边必须被保存，即使它们指向简化图中相同的超级节点S)。对不起，如果没有正确表达，我将尝试实现此解决方案，而我等待答案。
有更简单的方法吗？还是更好的处理循环/连通部件的算法？因为当图是无圈的，它看起来很容易解决。
回答 1
Stack Overflow用户
发布于 2013-03-20 04:05:22
如果图是强连通的，那么您可以从每个其他节点到达每个节点。由于允许在此路径中重用边缘，因此必须可以使用每个边缘。取一些边，e导致一个节点v，从它你可以得到每一个其他的顶点，因此，得到每一个其他的边。从这些，你可以回到v.重复根据需要。
因此，为了回答这个问题，图的某些性质保证了这样一条路径的存在。如果图是强连通的，我会说是的。(注意，这样的路径并不需要--例如，在没有分支的单向路径的情况下)。但这似乎是唯一的边缘情况(我可以想到)。
对强连通性的测试可以通过蛮力、检查-所有方法来完成.你也可以适应最大流，最小切割算法，我相信。
https://stackoverflow.com/questions/15514990
复制相似问题
腾讯云开发者
