Hello Readers

Happy New Year 2018

Hope you are doing well.

Today I am going to post a very very important topic of Graph theory that is Network Flows. Let us think two questions “What and Why” about Network Flows.

Readers, just imagine you are a courier service provider and you have to deliver some items from one city to another using various flights but each flight has a limited amount of space that you can use. So what is important here to think, ” How much of your items can be shipped to the destination using the different flights available?”

First think yourself then you would be able to relate it what is called “Network Flow Graphs”.

You can think so many different problem which can be modeled using such a graph.

Some of them are as follows:

1. Teliphone Lines
2. Highways
3. Rail Roads
4. Pipelines of Oil/Gas/Water etc.

In the above networks, users are interested to know the maximum rate of flow that is possible from one station to another in the network. This type of a network graph is represented by a weighted connected graph considering vertices as stations and edges as lines through which the given commodity flows.

Before discussing further, have a look on the following definitions:

Capacity of Edge/ Line: It is maximum amount of flow possible per unit of time.

Network Flow Graph: A connected directed graph with two special vertices say source vertex s and destination/sink vertex t is called Network flow graph.

in our above example of discussion vertices u and v are cities , edge (u,v) is a flight that flies directly from u to v and capacity is the amount of space available on the flight.

In the next coming post, I shall be discussing Max Flow Min Cut Theory, problems and concepts on how to solve Max Flow Problems.

 

 

Hope this post is helpful for you to understand the concept of Network Flow.

If you have any doubt /query then feel free to drop it on the comment box.

Thank You for reading.

Stay Connected, Stay Learnt

Namita Tiwari