logo标签列表

从图中消除循环流

algorithmgraphcycle
5
我有一个带有边缘流量的有向图，我想通过消除所有循环流来简化它。这可以通过在任何给定周期内找到每个边缘上的最小流量并将周期内每个边缘的流量减少该最小值来完成，从而删除流量为零的边缘。当所有循环流都被移除后，图将是无环的。
例如，如果我有一个具有顶点A、B和C的图，其中从A→B流出1，从B→C流出2，从C→A流出3，则我可以用没有从A→B流出的流，从B→C流出1和从C→A流出2来重写它。图中的边数已经从3减少到2，并且生成的图是无环的。
哪种算法（如果有）可以解决这个问题？
3
你刚刚不是已经描述了那个算法吗？ - Lasse V. Karlsen
@Lasse：你是指我的例子吗？我可以直观地通过铅笔和纸研究给定的图形来了解需要做什么，但我无法将我的直觉方法形式化以自动化该过程。 - J D
4个回答
5
您可能会发现使用流分解定理（参见最大流讨论的§6.2），对于任何流，都可以被分解为一组流路径和流循环。此外，在图中最多只有m个总流路径和循环。这意味着消除流循环的一个简单算法是找到图中的所有流路径，然后删除剩余的所有流，因为它必须对应于流循环。
要找到流路径或循环，您可以从源节点开始使用简单的深度优先搜索。从源节点开始，按照自己的方式继续跟随边缘，直到您到达终端节点或访问过以前访问过的节点。如果到达终端节点，则您所采取的路径是一个简单的流路径。如果遇到某个节点两次，则刚刚找到了一个流循环（由您刚刚找到的循环形成）。然后，如果从图中删除流路径/循环并重复，您将最终检测到所有流路径和循环。当没有携带流的边离开源代码时，您知道完成了。如果每次找到流路径时记录其所有边上的总流量，您可以通过重复此过程直到没有流路径，清除网络中的流量，然后再添加回流路径来消除循环流。
因为每个DFS需要时间O（m + n），而在图中最多有O（m）个流路径，所以该步骤的总运行时间为O（m² + mn），这是图的大小的多项式。
希望这可以帮助您！
2
拓扑排序仅适用于无环图。如果图中存在环，根据定义它就无法进行拓扑排序。 - templatetypedef
感谢这个，你可以检测循环。 - Berial
啊，我的错...我误读了你的帖子。我试图取消我的踩但是没有编辑过帖子我无法这样做；你能否进行一些小的更改以便我可以点赞这个回答？ - templatetypedef
1
使用拓扑排序能否找到最小的循环呢？例如，如果给定a->b->c，同时也有b->d->c，如何分别找到这两个循环呢？或者在任一情况下，这种方法都是错误的吗？ - Lasse V. Karlsen
2
你可以计算给定的流量值V，然后针对给定的网络和流量值V解决最小费用流问题，将每条边的成本设为1。最终得到的流应不包含任何循环，因为这样会导致非最优（与成本有关）。
循环取消显然是解决最小费用流问题的一种已知技术。然而，谷歌上关于这个主题的信息很少。有什么想法吗？ - J D
稍等，最小费用流有微妙的不同。我想通过取消循环来减少总流量，但是最小费用流在保持流量的同时最小化成本。实际上，所有成本相等的最小流量根本不会产生任何作用。 - J D
0
1
我不认为最小生成树（甚至是一般的生成树）在这里有用，因为这是一个有向图，目标是找到环。 - templatetypedef
1
Dijkstra算法不是用于寻找最小生成树，而是用于寻找最短路径，但我对其背后的逻辑有些困惑。 - Micromega
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接