问题标签 [euler-path]

有人可以告诉我汉密尔顿路径和欧拉路径之间的区别。它们看起来很相似！

这周我做了这个作业：计算无向图中节点的等级，并测试其中是否存在欧拉路径。该功能应如下所示：

我对该函数的第一个想法gradliste是“合并”图形并生成如下列表： [a,b,b,c,b,g,c,d,d,e,e,f,f,g,g,h,c,f]然后我计算每个节点的数量。不幸的是，我坚持merge.

对于第二个函数testEulerweg，我认为我应该首先编写一个函数allconnected，如下所示：

然后我可以使用该gradliste功能检查是否没有或有2个具有奇数级数的节点。

任何人都可以帮我解决我的想法吗？我也乐于接受新想法:)

提前致谢

熊熊

我正在寻找一种算法来在图中找到欧拉路径。

几周前我看过一个不错的，但现在找不到了，我记得有标记边缘，有偶数/奇数连接的东西......

你知道一个类似的、简单直接的算法吗？

现在我正在学习Prolog。请帮我完成这项任务：如何获得在 Prolog 上创建欧拉路径的顶点列表？程序应该适用于任何图表。

我有这个程序，但它只适用于这个图表。

基于标准定义，欧拉路径是图中的一条路径，它只访问每条边一次。

现在，我试图在有向图中找到欧拉路径。我知道欧拉电路的算法。如果一个图有欧拉回路，它就有欧拉路径，这似乎是微不足道的。

[图片来源：geeksforgeeks.org]

因此对于上述具有欧拉回路的有向图也具有欧拉路径。

现在，如果我删除一个边缘，让我们说从 4 到 0 它不再是欧拉电路。

1. 如果从顶点 0 开始我的 DFS，我仍然有欧拉路径。
2. 如果从顶点 3 开始，我没有欧拉路径

那么，有向图是否必须在欧拉回路中才能成为欧拉路径？我想，欧拉路径应该比欧拉电路限制更少。

是否有任何有向图可以是欧拉路径但不是欧拉回路。

我正在做一个线游戏。我有一些点和一些线将它们连接起来。当玩家第一次触摸 1 点时，该点被标记为“已选择”。然后玩家触摸另一个点，如果有一条线连接它们，该线将消失，第二个点被标记为“已选择”。当所有线消失时，玩家获胜。我搜索发现游戏关卡必须包含欧拉路径才能完成。但是我怎样才能为我的游戏生成关卡呢？

以下是在欧拉图中找到欧拉路径的给定算法。但是，据说有一个顶点少于10个的反例。给定的欧拉图是无向的，每个顶点的度数都是偶数，它将在同一个顶点开始和结束。

在过去的 3 天里，我一直在尝试从 6 到 9 的顶点，但我真的想不出一个例子。任何帮助表示赞赏！谢谢你。

从这个问题- 哈密顿路径和欧拉路径之间的差异，每条哈密尔顿路径都不是欧拉路径。我怎样才能准确地覆盖每个顶点一次并穿过边缘两次？

如何在无向加权图中找到最小欧拉路径？（该路径必须包含给定的边）

边缘的权重是所有边缘的 2 个点的总和（例如：edge 4-9 weight=4+9=13）。

示例：有 6 个节点（N）和 5 条边（E）：

解决方案：我们必须向最小欧拉路径添加 2 条边：

在此示例中，第三个节点是孤立的，但这不是问题。目标：欧拉路径，包含所有起始边。在这个例子中，我们可以使用 2 个互补边 (1-2)(1-2) 来执行欧拉路径：5->5->1->2->4->2->1->6。所以我们访问了所有的起始边，互补边最少，我们只使用一次所有边。

什么是最好的算法来找到，什么时候1<N,E<100000，必须在 0.01 秒内运行？

如何检查有向图是否是欧拉图？

1）所有非零度的顶点都属于一个单一的强连通分量。

2) 每个顶点的入度等于出度。资料来源：geeksforgeeks

问题： 在给定的两个条件中，第一个是严格的吗？我的意思是为什么图真的有必要成为“强”连接图？如果图形刚刚连接怎么办？

我了解到条件 1 可以用弱连通图代替。同样，如果图只是连接而不是弱连接怎么办？ 很高兴看到一些例子。

PS：在上面的讨论中，考虑条件 2 总是得到满足。通过“刚刚连接”，我的意思是图中存在一个顶点，所有其他顶点都可以从该顶点到达。