Network flow Flashcards
Definition of a flow network
“we’ll say that a flow network is a directed graph G= (V, E) with the following features.
Associated with each edge e is a capacity, which is a nonnegative number
that we denote ce.
There is a single source node s ∈ V.
There is a single sink node t ∈ V.
Nodes other than s and t will be called internal nodes.
Assumptions:
no edge enters the source s and no edge leaves the sink t
there is at least one edge incident to each node;
that all capacities are integers
We say that an s-t flow is a function f that maps each edge e to a
nonnegative real number, f : E → R+; the value f(e) intuitively represents the
amount of flow carried by edge e.
Capacity and conservation”
Max flow vs min cut
“Given a flow network, find a flow of maximum possible value.
The maximum-flow algorithm that we develop here will be intertwined with a proof that the maximum-flow value equals the minimum capacity of any such division, called the minimum cut.
(7.13) In every flow network, the maximum value of an s-t flow is equal to the minimum capacity of an s-t cut.
“
Maximum-Flow Problem
“Given a flow network, find a flow of maximum possible value.
pushing flow: We can push forward on
edges with leftover capacity, and we can push backward on edges that are already carrying flow, to divert it in a different direction. We now define the residual graph, which provides a systematic way to search for forward-backward operations such as this.
The residual graph
“We define bottleneck(P, f) to be the minimum residual capacity of any edge on P, with respect to the flow f.
The result of augment(f, P) is a new flow f′ in G, obtained by increasing
and decreasing the flow values on edges of P. f′ is a flow in G.”
The Ford Fulkerson algorithm
“(7.5) Suppose, as above, that all capacities in the flow network G are integers.
Then the Ford-Fulkerson Algorithm can be implemented to run in O(mC) time.
To find an s-t path in Gf , we can use breadth-first search or depth-first search, which run in O(m + n) time; by our assumption that m ≥ n/2, O(m + n) is the same as O(m).
When C is large, this time bound is much better than the O(mC) bound
that applied to an arbitrary implementation of the Ford-Fulkerson Algorithm. (see book).
”
Bipartite Matching
A matching M in G is a subset of the edges M ⊆ E such that each node appears in at most one edge in M. The Bipartite Matching Problem is that of finding a matching in G of largest possible size.
Disjoint Paths in Directed and Undirected Graphs
“We say that a set of paths is edge-disjoint if their edge sets are disjoint, that is, no two paths share an edge, though multiple paths may go through some of the same nodes.
Directed Edge-Disjoint Paths Problem is to find the maximum number of edge-disjoint s-t paths in G.
Both the directed and the undirected versions of the problem can be solved very naturally using flows
(7.44) The Ford-Fulkerson Algorithm can be used to find a maximum set of
edge-disjoint s-t paths in a directed graph G in O(mn) time.
(7.42) If f is a 0-1 valued flow of value ν, then the set of edges with flow
value f(e)= 1 contains a set of ν edge-disjoint paths. (basically run BFS, take a resulting path, subtract edge capacities by 1, and continue until no path is found).”
Circulation with demands
“Suppose that there can be a set S of sources generating flow, and a set T of sinks that can absorb flow.
So instead of maximizing the flow value, we will consider a problem where sources have fixed supply values and sinks have fixed demand values, and our goal is to ship flow from nodes with available supply to those with given demands
We use S to denote the set of all nodes with negative demand and T to
denote the set of all nodes with positive demand.
we say that a circulation with demands {dv} is a function f
that assigns a nonnegative real number to each edge and satisfies the following
two conditions.
(i) (Capacity conditions) For each e ∈ E, we have 0 ≤ f(e) ≤ ce.
(ii) (Demand conditions) For each v ∈ V, we have v, fin(v)− fout(v)= dv.
“
Circulations with Demands and Lower Bounds
“These considerations directly motivate the following construction. Let the
graph G′ have the same nodes and edges, with capacities and demands, but
no lower bounds. The capacity of edge e will be ce− ℓe. The demand of node
v will be dv− Lv. “
Survey Design
“More formally, the input to the Survey Design Problem consists of a bipartite
graph G whose nodes are the customers and the products, and there is an edge
between customer i and product j if he or she has ever purchased product j.”
Airline Scheduling
“More formally, the input to the Survey Design Problem consists of a bipartite
graph G whose nodes are the customers and the products, and there is an edge
between customer i and product j if he or she has ever purchased product j.”
Image segmentation
“One of the most basic problems to be considered along these lines is that
of foreground/background segmentation It
turns out that a very natural model here leads to a problem that can be solved
efficiently by a minimum cut computation
For each pixel i, we have a likelihood ai that it belongs to the foreground,
and a likelihood bi that it belongs to the background
for each pair (i, j) of neighboring pixels, there is a separation penalty pij ≥ 0 for placing
one of i or j in the foreground and the other in the background.
(7.55) The solution to the Segmentation Problem can be obtained by a
minimum-cut algorithm in the graph G′ constructed above. For a minimum
cut (A′, B′), the partition (A, B) obtained by deleting s∗ and t∗ maximizes the
segmentation value q(A, B).
“
Project Selection (Open-Pit Mining Problem)
“There is an underlying set P of projects, and each project i ∈ P has an associated
revenue pi, which can either be positive or negative.
Certain projects are prerequisites for other projects, and we model this by an underlying directed
acyclic graph G= (P, E). The nodes of G are the projects, and there is an edge
(i, j) to indicate that project i can only be selected if project j is selected as
well.
The Project Selection Problem is to select a feasible set of projects with maxi-
mum profit
Here we will show that the Project Selection Problem can be solved by reducing
it to a minimum-cut computation on an extended graph G′.
The idea is to construct G′ from G in such a way that the source side of a minimum cut in
G′ will correspond to an optimal set of projects to select.”
