有向图中的欧拉电路
Euler Circuit in a Directed Graph
如何判断有向图是否欧拉？
1) 所有非零度的顶点都属于一个强连通分量。
2) 每个顶点的入度等于出度。资料来源：geeksforgeeks
问题：
在给定的两个条件中，第一个是否严格？我的意思是为什么图真的有必要 "strongly" 连通图？如果图只是连接呢？
我了解到条件1可以用弱连通图代替。同样，如果图只是连接而不是弱连接怎么办？
很高兴看到一些示例。
P.S：考虑条件2在上面的讨论中总是满足的。 "just connected"，我的意思是图中存在一个顶点，所有其他顶点都可以从该顶点到达。
这是一个有趣的问题。据我所知，"connected" 在有向图的上下文中没有标准化的含义。有向图中连通性的两个一般概念是
- 强连通性，其中对于任何一对节点 u 和 v 都有一条从 u 到 v 的路径和一条从 v 到 u 的路径，并且
- 弱连通性，忽略箭头方向性形成的无向图是连通的
您的有向图版本 "just connected" 与这些定义略有不同，但它与强连通性有关。任何有向图都可以将其节点划分为 strongly connected components (SCC)，一组节点都可以相互访问。这些强连通分量形成一个 DAG，其中每个强连通分量都是一个节点，并且如果第一个 SCC 中的一个节点具有到第二个 SCC 中的节点的边，则存在从一个 SCC 到另一个 SCC 的边。
您对图表的定义 "just connected" 可以这样固定：
- "just connected"：SCC的DAG有一个源节点可以到达所有其他节点。
请注意 "just connected" 表示弱连接，但反之则不然。
事实证明，在这种情况下，如果您有一个图，其中每个节点的入度恰好等于其出度，那么如果图是 "just connected," 则它有一个欧拉回路。如果你的图是 "just connected," 那么它是弱连接的。然后，我们将声明任何入度等于出度的弱连通图也必须是强连通的。要查看此内容，请在 SCC 的 DAG 中选择任何没有传入边的 SCC。进入此 SCC 中任何节点的任何边都必须来自该 SCC 内。因此，如果我们遍历 SCC 中的每个节点并将离开该节点的边数相加，则该总数将与进入 SCC 中每个节点的边数相匹配。但是，由于节点的入度之和等于节点的出度之和，因此不会有任何边从该 SCC 开始并以另一个结束，因为所有边都被考虑在内。因此，这个SCC没有边离开它。
我们刚刚展示了任何源 SCC 都必须没有与任何其他 SCC 的边。并且由于某个源SCC中有某个节点可以到达每个节点，这意味着图中没有其他SCC，因此该图只有一个SCC，因此是强连接的。
如何判断有向图是否欧拉？
1) 所有非零度的顶点都属于一个强连通分量。
2) 每个顶点的入度等于出度。资料来源：geeksforgeeks
问题： 在给定的两个条件中，第一个是否严格？我的意思是为什么图真的有必要 "strongly" 连通图？如果图只是连接呢？
我了解到条件1可以用弱连通图代替。同样，如果图只是连接而不是弱连接怎么办？ 很高兴看到一些示例。
P.S：考虑条件2在上面的讨论中总是满足的。 "just connected"，我的意思是图中存在一个顶点，所有其他顶点都可以从该顶点到达。
这是一个有趣的问题。据我所知，"connected" 在有向图的上下文中没有标准化的含义。有向图中连通性的两个一般概念是
- 强连通性，其中对于任何一对节点 u 和 v 都有一条从 u 到 v 的路径和一条从 v 到 u 的路径，并且
- 弱连通性，忽略箭头方向性形成的无向图是连通的
您的有向图版本 "just connected" 与这些定义略有不同，但它与强连通性有关。任何有向图都可以将其节点划分为 strongly connected components (SCC)，一组节点都可以相互访问。这些强连通分量形成一个 DAG，其中每个强连通分量都是一个节点，并且如果第一个 SCC 中的一个节点具有到第二个 SCC 中的节点的边，则存在从一个 SCC 到另一个 SCC 的边。
您对图表的定义 "just connected" 可以这样固定：
- "just connected"：SCC的DAG有一个源节点可以到达所有其他节点。
请注意 "just connected" 表示弱连接，但反之则不然。
事实证明，在这种情况下，如果您有一个图，其中每个节点的入度恰好等于其出度，那么如果图是 "just connected," 则它有一个欧拉回路。如果你的图是 "just connected," 那么它是弱连接的。然后，我们将声明任何入度等于出度的弱连通图也必须是强连通的。要查看此内容，请在 SCC 的 DAG 中选择任何没有传入边的 SCC。进入此 SCC 中任何节点的任何边都必须来自该 SCC 内。因此，如果我们遍历 SCC 中的每个节点并将离开该节点的边数相加，则该总数将与进入 SCC 中每个节点的边数相匹配。但是，由于节点的入度之和等于节点的出度之和，因此不会有任何边从该 SCC 开始并以另一个结束，因为所有边都被考虑在内。因此，这个SCC没有边离开它。
我们刚刚展示了任何源 SCC 都必须没有与任何其他 SCC 的边。并且由于某个源SCC中有某个节点可以到达每个节点，这意味着图中没有其他SCC，因此该图只有一个SCC，因此是强连接的。