有向图中的最大流量 [英] Maximum Flow in Directed Graph

问题描述

我正在阅读最大流量问题。
说你找到的第一条路径是s，u，v，t，并且你推动10个流量通过它。现在，您可以在残差图中找到路径s，v，u，t（即使vu边缘不存在于原始图形中），并按5流量通过它。所以发生的事情是，从u到v的5个单位现在被重定向到t，而从u到v的5个单位现在来自s。

如果您有无向图，则可以用有向边AB和有向边BA替换边AB，其边具有与原始无向边相同的容量。你不能在两个方向上都流动，因为你通过取消较小的方法来获得相同的解决方案。来回发送流量没有任何好处。

I am reading about the Maximum Flow Problem Here. I could not understand the initiation behind the Residual Graph. Why we are considering a back edge while calculating the flow.

Can anyone help me in understanding the concept of Residual Graph.

How the Algorithm changes in Undirected Graph

解决方案

The residual graph is what is left of the network after you remove the flow you've already passed through. Say you have an edge AB with capacity 10 and the current flow moves 7 units through AB then in the residual graph you should have an edge AB with capacity 3 (what is left) and an edge BA with capacity 7 (this appears because you can get flow back by removing it from the previous solution; That is because if you find a way from source to B and from A to the sink then you can redirect the previous solution to not use the edge AB, or use less of it).

To make it more clear see this image . Say the first path you find is s, u, v, t and you push 10 flow through it. Now you can find in the residual graph the path s,v,u,t (even if the vu edge doesn't exist in the original graph) and push 5 flow through it. So what happened is that 5 units of flow that were going from u to v are now redirected to go to t, and the 5 units that were coming from u to v are now coming from s.

If you have an undirected graph you can replace an edge AB with a directed edge AB and a directed edge BA with the same capacity as the original undirected edge. You can't have flow going in both directions because you get the same solution by cancelling out the smaller one. There's nothing to gain by sending the flow back and forth.

这篇关于有向图中的最大流量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！