消除图形中的循环流

Question

我有一个沿边缘流量的有向图,我想通过删除所有循环流来简化它.这可以通过在任何给定循环中找到沿每个边缘的最小流量并且将循环中每个边缘的流量减少该最小体积来完成,从而删除具有零流量的边缘.当所有循环流都被移除后,图形将是非循环的.

例如,如果我有顶点A,B和C,其中从A→B,2从B→C和3从C→A的1流动的图表然后我可以从A→B,1从没有流重写这个B→C和2→C→A.图中的边数从3减少到2,结果图是非循环的.

哪种算法(如果有的话)可以解决这个问题？

Answer 1

您可能会发现使用流分解定理很有用（请参阅max-flow 讨论的第 6.2 节），该定理表示任何流都可以分解为一组流路径和流循环。此外，图中最多可以有m个总流路和循环。这意味着消除流动循环的一种简单算法是找到图中的所有流动路径，然后删除图中所有剩余的流动，因为它必须对应于流动循环。

要查找流路径或循环，您可以从源节点使用简单的深度优先搜索。从源节点开始，按照您想要的方式继续跟踪边缘，直到您到达终端节点或访问您之前访问过的节点。如果您到达终端节点，那么您所采取的路径就是简单的流路径。如果您两次遇到某个节点，则您刚刚找到了一个流动循环（由您刚刚找到的循环形成）。如果您随后从图中删除流动路径/循环并重复，您最终将检测到所有流动路径和循环。当没有任何流程承载边缘离开源代码时，您就知道您已经完成了。如果每次找到一条流路径时，都记录其所有边上的总流量，则可以通过重复此操作直到没有剩余流路径、清除网络中的流，然后添加回流路径来消除循环流。

由于每个 DFS 花费的时间为 O(m + n)，并且最多有 O(m) 条流路径，因此该步骤的总运行时间为 O(m ² + mn)，这是图大小的多项式。

希望这可以帮助！

Answer 2

您是否考虑过生成最小生成树？你可以使用Dijkstra 算法来实现这一点。如果您想首先确定图是否是循环图，您可以使用拓扑排序来确定。