从图中消除循环流
我有一个有向图，其边缘有流量，我想通过删除所有循环流来简化它。这可以通过找到任何给定循环中沿每条边的流量的最小值并将循环中每条边的流量减少该最小流量、删除流量为零的边来完成。当所有循环流被删除后，该图将是非循环的。
例如，如果我有一个包含顶点 A、B 和 C 的图，其流量为 1 从 A→B、2 从 B→C 和 3 从 C→A，那么我可以重写此图，而没有从 A→B 的流量，1 从B→C 和 2 从 C→A。图中的边数从 3 条减少到 2 条，并且生成的图是非循环的。
哪种算法（如果有）可以解决这个问题？
I have a directed graph with flow volumes along edges and I would like to simplify it by removing all cyclic flows. This can be done by finding the minimum of the flow volumes along each edge in any given cycle and reducing the flows of every edge in the cycle by that minimum volume, deleting edges with zero flow. When all cyclic flows have been removed the graph will be acyclic.
For example, if I have a graph with vertices A, B and C with flows of 1 from A→B, 2 from B→C and 3 from C→A then I can rewrite this with no flow from A→B, 1 from B→C and 2 from C→A. The number of edges in the graph has reduced from 3 to 2 and the resulting graph is acyclic.
Which algorithm(s), if any, solve this problem?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
您可能会发现使用流分解定理很有用（请参阅max-flow 的讨论），它说任何流都可以分解为一组流路径和流循环。此外，图中最多可以有m个总流路和循环。这意味着消除流动循环的一种简单算法是找到图中的所有流动路径，然后删除图中所有剩余的流动，因为它必须对应于流动循环。
要查找流路径或循环，您可以从源节点使用简单的深度优先搜索。从源节点开始，按照您想要的方式继续跟踪边缘，直到您到达终端节点或访问您之前访问过的节点。如果您到达终端节点，那么您所采取的路径就是简单的流路径。如果您两次遇到某个节点，则您刚刚找到了一个流动循环（由您刚刚找到的循环形成）。如果您随后从图中删除流动路径/循环并重复，您最终将检测到所有流动路径和循环。当没有任何流程承载边缘离开源代码时，您就知道您已经完成了。如果每次找到一条流路径时，都记录其所有边上的总流量，则可以通过重复此操作直到没有剩余流路径、清除网络中的流，然后添加回流路径来消除循环流。
由于每个 DFS 花费的时间为 O(m + n)，并且最多有 O(m) 条流路，因此该步骤的总运行时间为 O(m2 + mn)，这是一个多项式图表的大小。
希望这有帮助！
You may find it useful to use the flow decomposition theorem (see §6.2 of this discussion of max-flow), which says that any flow can be broken down into a set of flow paths and flow cycles. Moreover, there can be at most m total flow paths and cycles in the graph. This means that one simple algorithm for eliminating flow cycles would be to find all of the flow paths in the graph, then remove all remaining flow in the graph since it must correspond to flow cycles.
To find a flow path or cycle, you can use a simple depth-first search from the source node. Starting at the source node, keep following edges however you'd like until either you hit the terminal node or you visit a node you've previously visited. If you hit the terminal node, then the path you've taken is a simple flow path. If you encounter some node twice, you've just found a flow cycle (formed by the loop that you just found). If you then remove the flow path/cycle from the graph and repeat, you will end up detecting all flow paths and cycles. You know that you're done when there are no flow-carrying edges leaving the source code. If each time that you find a flow path you record the total flow across all of its edges, you can eliminate cyclic flow by repeating this until no flow paths remain, clearing the flow in the network, then adding back in the flow paths.
Since each DFS takes time O(m + n) and there are at most O(m) flow paths, the total runtime of this step is O(m2 + mn), which is a polynomial in the size of the graph.
Hope this helps!
您可以使用拓扑排序
http://en.wikipedia.org/wiki/Topological_sorting
在查找时效果非常好有向图中的循环
You could use topological sorting
http://en.wikipedia.org/wiki/Topological_sorting
It works great when it comes to finding a cycles in directed graphs
您可以计算给定流的值
V，然后针对给定网络和流值V求解最小成本流问题，分配成本1到每个边缘。那么生成的流不应包含任何循环，因为这将是非最佳的（相对于成本）。
You can compute the value
Vof a flow given and then solve a min-cost flow problem for the network given and flow valueV, assigning cost1to each edge.Then a resulting flow should not contain any cycles, since that would be non-optimal (with respect to cost).
您是否考虑过生成一个最小生成树？您可以使用 Dijkstra 算法 来实现这一点。如果您想首先确定图是否是循环图，您可以使用拓扑排序来确定。
Have you thought about producing a minimum spanning tree? you could use Dijkstra's algorithm for that. If you want to first find out if a graph is cyclic you can determine that by using topological sorting.