Scribd
Upload
66 views4 pages

Maximal Flow Problem

The document discusses maximum flow and minimum cut in graphs. It defines these terms and states the max-flow min-cut theorem, which establishes that the maximum flow through a network equals the capacity of its minimum cut. It provides examples calculating max flow and identifying the minimum cut for different networks.

Uploaded by

amanafathima297
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
66 views4 pages

Maximal Flow Problem

The document discusses maximum flow and minimum cut in graphs. It defines these terms and states the max-flow min-cut theorem, which establishes that the maximum flow through a network equals the capacity of its minimum cut. It provides examples calculating max flow and identifying the minimum cut for different networks.

Uploaded by

amanafathima297
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 4

A maximum flow is defined as the maximum amount of flow that the graph or

network would allow to flow from the source node to its sink node.
Minimum Cut in a Graph
In general, a cut is a set of edges whose removal divides a connected graph into
two disjoint subsets. There are two variations of a cut: maximum cut and
minimum cut. Before discussing the max-flow min-cut theorem, it’s important to
understand what a minimum cut is.
The minimum cut of a weighted graph is defined as the minimum sum of
weights of edges that, when removed from the graph, divide the graph into
two sets.

Max-Flow Min-Cut Theorem


The max-flow min-cut theorem states that the maximum flow through any
network from a given source to a given sink is exactly equal to the minimum
sum of a cut

Example: What is the max-flow of this network from the source a to sink f ?

Cut Associated arc Capacity


1 (a, b), (a, c) 9+8=17
2 (d, f), (c, f) , (e, f) 5+3+6=14
3 (b, d), (b, e), (c, f), (c, e) 4+4+3+5=16
4 (b, d ), (c, f), (e, f ) 4+3+6=13
So the minimum cut of this network is (b, d ), (c, f), (e, f ) and its capacity
is13 .
Therefore the maximum flow from the node source a to sink f is 13 units

4. (1,4), (2,5), (3,4), (3,5) 10+30+10+20=70


Minimum cut of this network is (1) and its capacity is 60.
Therefore the maximum flow from the node source 1 to sink 5 is 60 units
1) Let's look at another water network that has edges of different capacities.

In this graphic, each edge represents the amount of water, in gallons, that can pass
through it at any given time.

1. What is the max-flow of this network?

The answer is 10 gallons


2) What is the max-flow of this network from source 1 to sink 5

You might also like