创建具有欧拉通路的图的证明算法？

Question

3

我想知道是否存在一种经过验证的算法，可以在给定一组节点的情况下创建一个具有欧拉回路的图。我在谷歌上搜索了它，但只找到了弗洛伊德算法，它只能判断一个图中是否存在欧拉回路。你知道是否存在这样的算法吗？谢谢:)

- GniruT

4

创造的图应具备哪些属性？根据您所述，将所有节点连接为单一路径将满足存在欧拉通路的条件。 - kajacx

有一个算法，可以给定一个带权图，在保证结果图为欧拉图的前提下，将总权重最小的边加倍。这是您要找的吗？ - Ivaylo Strandjev

@kajacx 没错，那是一种可能性。但是还有其他方法可以获得欧拉回路。你知道那些算法吗？ - GniruT

@IvayloStrandjev 我可能可以。这个算法叫什么？我在哪里可以找到Python、C或Java的实现？谢谢。 - GniruT

@GniruT 如果你能说出为什么你需要它，我或许可以更好地帮助你。你可以添加一条连接所有节点的路径，然后随机添加剩余的边。 - kajacx

显示剩余2条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user1952500 · Accepted Answer

“寻找给定节点集合的所有可能欧拉回路”问题与“在完全无向图中寻找所有欧拉回路”问题相同。这是一个开放性问题，有一些近似解法可用。

关于研究的一些细节，请参见此处和此处。