The Maximum Network Flow Problem

The Maximum Network Flow Problem
Maximum Flow Problem
• How can we maximize the flow in a network from a source or set of sources to a destination or
set of destinations?
• Find maximum flow in a flow network from a single source s to a single sink t
FLOW NETWORK (G)
 Simple directed graph

 1 source s, 1 sink t
 Non-negative capacity for each edge
RESIDUAL GRAPH (Gf)
 Only edges from G that can still have more flow

 Cf(u,v) = c(u,v) – f(u,v)
AUGMENTING PATH
 Path from s to t in Gf
 Residual capacity = smallest capacity of edges of p
Computing Max Flow
• Classic Method:
– Identify augmenting path
– Increase flow along that path
– Repeat
Ford-Fulkerson Method
Example 1
Answer: Maximum flow (Fm) = 12
Example 2

Example 3
Example 4

Spanning trees
A spanning tree of a graph is just a subgraph that contains all the vertices and is a tree. A graph
may have many spanning trees; for instance the complete graph on four vertices
has sixteen spanning trees:
A spanning tree of G is a subgraph T that is:
・Connected.
・Acyclic.
・Includes all of the vertices.

What is a Minimum Spanning Tree?
The cost of the spanning tree is the sum of the weights of all the edges in the tree. There can be
many spanning trees. Minimum spanning tree is the spanning tree where the cost is minimum
among all the spanning trees. There also can be many minimum spanning trees.
There are two famous algorithms for finding the Minimum Spanning Tree
Kruskal’s Algorithm
Kruskal’s Algorithm builds the spanning tree by adding edges one by one into a growing spanning
tree. Kruskal's algorithm follows greedy approach as in each iteration it finds an edge which has
least weight and add it to the growing spanning tree.
Algorithm Steps:
 Sort the graph edges with respect to their weights.

 Start adding edges to the MST from the edge with the smallest weight until the edge of
the largest weight.
 Only add edges which doesn't form a cycle , edges which connect only disconnected
components.
In Kruskal’s algorithm, at each iteration we will select the edge with the lowest weight. So, we will
start with the lowest weighted edge first i.e., the edges with weight 1. After that we will select the
second lowest weighted edge i.e., edge with weight 2. Notice these two edges are totally disjoint.
Now, the next edge will be the third lowest weighted edge i.e., edge with weight 3, which connects
the two disjoint pieces of the graph. Now, we are not allowed to pick the edge with weight 4, that
will create a cycle and we can’t have any cycles. So we will select the fifth lowest weighted edge
i.e., edge with weight 5. Now the other two edges will create cycles so we will ignore them. In the
end, we end up with a minimum spanning tree with total cost 11 ( = 1 + 2 + 3 + 5).
Prim’s Algorithm
Prim’s Algorithm also use Greedy approach to find the minimum spanning tree. In Prim’s
Algorithm we grow the spanning tree from a starting position. Unlike an edge in Kruskal's, we
add vertex to the growing spanning tree in Prim's.
Algorithm Steps:
 Maintain two disjoint sets of vertices. One containing vertices that are in the growing
spanning tree and other that are not in the growing spanning tree.
 Select the cheapest vertex that is connected to the growing spanning tree and is not in
the growing spanning tree and add it into the growing spanning tree. This can be done
using Priority Queues. Insert the vertices, that are connected to growing spanning tree,
into the Priority Queue.
 Check for cycles. To do that, mark the nodes which have been already selected and insert
only those nodes in the Priority Queue that are not marked.
In Prim’s Algorithm, we will start with an arbitrary node (it doesn’t matter which one) and mark it.
In each iteration we will mark a new vertex that is adjacent to the one that we have already
marked. As a greedy algorithm, Prim’s algorithm will select the cheapest edge and mark the
vertex. So we will simply choose the edge with weight 1. In the next iteration we have three
options, edges with weight 2, 3 and 4. So, we will select the edge with weight 2 and mark the
vertex. Now again we have three options, edges with weight 3, 4 and 5. But we can’t choose edge
with weight 3 as it is creating a cycle. So we will select the edge with weight 4 and we end up with
the minimum spanning tree of total cost 7 ( = 1 + 2 +4).
MST is fundamental problem with diverse applications.
・Dithering.
・Cluster analysis.
・Max bottleneck paths.

・Real-time face verification.
・LDPC codes for error correction.
・Image registration with Renyi entropy.
・Find road networks in satellite and aerial imagery.
・Reducing data storage in sequencing amino acids in a protein.
・Model locality of particle interactions in turbulent fluid flows.
・Autoconfig protocol for Ethernet bridging to avoid cycles in a network.
・Approximation algorithms for NP-hard problems (e.g., TSP, Steiner tree).
・Network design (communication, electrical, hydraulic, computer, road).
SOURCE:
https://www.hackerearth.com/practice/algorithms/graphs/minimum-spanning-tree/tutorial/
Exercise:
Answer:

The Maximum Network Flow Problem

Uploaded by

Copyright:

Available Formats

The Maximum Network Flow Problem

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

The Maximum Network Flow Problem

Uploaded by

Copyright:

Available Formats

The Maximum Network Flow Problem

Maximum Flow Problem

FLOW NETWORK (G)

 Simple directed graph

RESIDUAL GRAPH (Gf)

 Only edges from G that can still have more flow

Computing Max Flow

– Identify augmenting path

– Increase flow along that path

Answer: Maximum flow (Fm) = 12

Answer: Maximum flow (Fm) = 19

Answer: Maximum flow (Fm) = 25

Answer: Maximum flow (Fm) = 19

has sixteen spanning trees:

A spanning tree of G is a subgraph T that is:

・Includes all of the vertices.

 Sort the graph edges with respect to their weights.

MST is fundamental problem with diverse applications.

・Max bottleneck paths.

・LDPC codes for error correction.

・Image registration with Renyi entropy.

・Find road networks in satellite and aerial imagery.

・Reducing data storage in sequencing amino acids in a protein.

・Model locality of particle interactions in turbulent fluid flows.

・Autoconfig protocol for Ethernet bridging to avoid cycles in a network.

・Approximation algorithms for NP-hard problems (e.g., TSP, Steiner tree).

・Network design (communication, electrical, hydraulic, computer, road).

You might also like