我有一个沿边缘的流量的有向图，我想通过删除所有循环流来简化它。这可以通过在任何给定循环中找到沿每条边的最小流量并将循环中每条边的流量减少该最小量来完成，删除流量为零的边。当所有循环流都被移除后，该图将是非循环的。
例如，如果我有一个带有顶点 A、B 和 C 的图，其中 1 来自 A→B，2 来自 B→C，3 来自 C→A，那么我可以在没有来自 A→B 的流量的情况下重写它，1 B→C 和 C→A 中的 2。图中的边数从 3 减少到 2，结果图是非循环的。
如果有的话，哪种算法可以解决这个问题？
问问题
4066 次
4 回答
3
您可能会发现使用流分解定理很有用（参见关于 max-flow的讨论的第 6.2 节），它表示任何流都可以分解为一组流路径和流循环。此外，图中最多可以有 m 个总流路和循环。这意味着消除流循环的一种简单算法是找到图中的所有流路径，然后删除图中所有剩余的流，因为它必须对应于流循环。
要查找流动路径或循环，您可以从源节点使用简单的深度优先搜索。从源节点开始，随心所欲地跟随边，直到您到达终端节点或访问您之前访问过的节点。如果你点击终端节点，那么你所走的路径就是一条简单的流动路径。如果您两次遇到某个节点，则您刚刚找到了一个流循环（由您刚刚找到的循环形成）。如果然后从图中删除流路/循环并重复，您最终将检测到所有流路和循环。当源代码没有承载流的边缘时，您就知道您已经完成了。如果每次找到一条流路时都记录其所有边缘的总流量，则可以通过重复此操作来消除循环流，直到没有流路为止，
由于每个 DFS 需要时间 O(m + n) 并且最多有 O(m) 条流路，因此这一步的总运行时间为 O(m 2 + mn)，这是图大小的多项式。
希望这可以帮助！
于 2011-08-31T20:49:47.350 回答
2
您可以计算V给定流的值，然后为给定的网络和流值解决最小成本流问题V，将成本分配1给每条边。
那么结果流不应该包含任何循环，因为那将是非最优的（就成本而言）。
于 2011-03-25T14:53:19.967 回答
1
您可以使用拓扑排序 http://en.wikipedia.org/wiki/Topological_sorting
在有向图中查找循环时效果很好
于 2011-03-20T19:26:45.530 回答
0
您是否考虑过生成最小生成树？你可以使用Dijkstra 的算法。如果您想首先确定一个图是否是循环的，您可以使用拓扑排序来确定它。
于 2011-03-20T19:18:38.967 回答