1

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

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

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

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

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

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

4

1 回答 1

2

这是个有趣的问题。据我所知，在有向图的上下文中，“连接”没有标准化的含义。有向图中连通性的两个一般概念是

  • 强连通性，对于任何一对节点 u 和 v，都有一条从 u 到 v 的路径和一条从 v 到 u 的路径，并且
  • 弱连通性，忽略箭头上的方向性形成的无向图是连通的。

您的“刚连接”有向图版本与这些定义略有不同，但它与强连接有关。任何有向图都可以将其节点划分为强连接组件（SCC），即可以相互连接的节点组。这些强连通分量形成一个 DAG，其中每个强连通分量都是一个节点，如果第一个 SCC 中的一个节点与第二个 SCC 中的一个节点有一条边，则从一个 SCC 到另一个 SCC 有一条边。

然后可以像这样确定您对“刚刚连接”的图形的定义：

  • “刚刚连接”：SCC 的 DAG 有一个可以到达所有其他节点的源节点。

请注意，“刚刚连接”意味着弱连接，但不是相反。

事实证明，在这种情况下，如果您有一个图，其中每个节点的入度恰好等于其出度，那么如果该图“刚刚连接”，那么它就有一个欧拉回路。如果您的图表是“刚连接的”，那么它是弱连接的。然后，我们将声称任何入度等于出度的弱连接图也必须是强连接的。要查看这一点，请在 SCC 的 DAG 中选择没有传入边的任何 SCC。进入此 SCC 中任何节点的任何边都必须来自该 SCC 内。因此，如果我们遍历 SCC 中的每个节点并将离开该节点的边数相加，则该总数将与 SCC 中每个节点的传入边数相匹配。但是，由于节点的入度之和等于节点的出度之和，因此可以' 然后 t 是在这个 SCC 内开始并以另一个结束的任何边，因为所有边都被考虑在内。因此，这个 SCC 没有边缘离开它。

我们刚刚展示了任何源 SCC 必须与任何其他 SCC 没有边。并且由于某个源 SCC 中的某个节点可以到达每个节点，这意味着图中没有其他 SCC，因此该图只有一个 SCC，因此是强连接的。

于 2020-04-21T17:19:40.067 回答