Problem Detail: Flow networks are often constructed when one is interested in measuring how resilient a graph is. The idea goes as follows: two vertices are designated as source $(s)$ and sink $(t)$ respectively, to each edge $e$ of the graph a capacity $c_e$ is assigned (which can be defined as a function vertex properties of the endpoints of an edge), and in analogy to flow of water through pipes for example, a net flow is assumed to take place from the source towards the sink. That is the net flow out of the source, is equal to the net flow entering the sink: $$ sum_{uin O(s)} f(s,u)-sum_{uin I(s)}f(u,s)=sum_{uin I(t)} f(u,t)-sum_{uin O(t)}f(t,u) $$ where $O(s)$ denotes the set of vertices, that $s$ is incident on, and $I(s)$ denotes the set of vertices that are incident to $s.$ Now often, one is interested in computing the maximum possible flow in the graph, which leads to using Menger’s theorem, which relates maximum number of distinct paths (between $s$ and $t$) to the minimal cut-set, or in a general setting, it relates the maximum flow to minimum cut capacity (summing the capacities of the minimum cut, that disconnects source from sink). There are many algorithms that allow computing the maximum flow rather efficiently, for a given digraph. But my questions are (sadly) rather basic, but are solely related to computing maximum flow:
- Assuming the capacities of all the edges are known, why the computation of maximum flow does not(?) depend on the net outward flow from the source, and instead it is only a function of the capacities? or am I wrong?
- How are then the individual flows $f$, through each edge $e$ (where $f_ele c_e $), calculated when we are estimating the maximum flow? Do we set all flows equal to respective capacities (i.e. $f_e=c_e$)? Or is the individual flow, a function of the minimum capacity ($text{min}(c_e)$ for all edges $e$) of the graph?
- Of course it is possible that I’m completely wrong here, in which case, the question becomes: how is the flow decided for each edge (knowing at least that $0le f_e le c_e$ for all edges), when we are interested in estimating the maximum flow through the graph?
Asked By : user929304
Answered By : Denis Pankratov
I think all your questions are answered by examining the actual algorithm to compute the max flow. With regards to your Q1: in the max flow problem your input is a graph and capacities on edges, your output is the max flow. Thus, max flow is a function of the graph and capacities. The basic algorithm for computing max flow is as follows. Your capacities are $c: E rightarrow mathbb{R}$. We shall incrementally compute the flow $f: E rightarrow mathbb{R}$. Let $f^i$ be the flow in iteration $i$. To begin with set $f^0 = 0$. In iteration $i$ construct the residual capacities $c^i(e) = c(e) – f^i(e)$ – this is how much capacity is left on edge $e$ given that we are already sending $f^i(e)$ flow through it. Find an augmenting path from $s$ to $t$, i.e., any path $p$ from $s$ to $t$ such that all edges on that path have positive residual capacity. How much flow can you push on this path? Clearly it’s the minimum capacity along an edge of that path $f_{add} = min_{e in p} c^i(e)$. Update your flow by pushing $f_{add}$ flow along path $p$. This process naturally stops when your residual graph does not have an augmenting path from $s$ to $t$. It’s a fact that at that point the flow you constructed is, indeed, the maximum flow. This fact requires a proof. This is a meta-algorithm (called Ford-Fulkerson), because I have not specified how to choose augmenting paths. Certain choices are better than others. Using BFS (in which case, this max flow algorithm has a name of Edmonds-Karp) to choose the augmenting path results in a polynomial time algorithm, but it again requires proof.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/57576 Ask a Question Download Related Notes/Documents
