Graphs in Network Flows

  • V manjula Basic Engineering Department, DVR & Dr HS MIC College of Technology, Kanchikacherla, Krishna State, Andhra Pradesh 521180 India.


This paper presents a collection of basics and application of Network flows in Graph theory which is an out- growth of set of lecture notes on Graph applications. It is not only a record of material from text books but also a reflection of precise graphical concept which will be useful for students where such facts are needed. There are many real life problems dealing with discrete objects and binary relations and graph is very convenient form of its representation. A network flow graph G=(V,E) is a directed graph with two special vertices: the source vertex s, and the sink vertex t. Many problems in the real world are to be solved using maximum flow. "Real" networks, like the Internet or electronic circuit boards, are good examples of flow networks. Generally graphs can be used in two situations. Firstly since graph is a very simple, convenient and natural way of representing the relationship between objects. Secondly we have graph as model solve the appropriate graph theoretic problem then interpret the solution in terms of original problem In the modern world, planning efficient routes is essential for business and industry, The flow of information or water or gas etc in a network are useful to find the max rate of flow that is possible from one station to another A Transport network represents a general model for transportation of material from origin of supply to destination through shipping routes. The objective of this paper is to discuss the concepts and terminology of Network flows with Graphical representations.


G S Singh, Graph Theory, Prentice Hall of India, 2010.

N Deo, Graph Theory with Applications to Engineering and Computer Science, Prentice Hall of India, 1974.

S D Sharma, Operations Research, Kedarnadh and Ramnadh, 2006.

J K Truss, Discrete Mathematics for Computer Scientists, Addison Wesley, 1999.

D B West, Introduction to graph theory, PHI Learning, 2001.

M K Das, Discrete mathematical structures for computer scientists and engineers, Narosa, 2007.

Dieter van Melkebeek, Network Flow, Lecture Notes, CS 787.

Richard Johnsonbaugh, Discrete mathematics, Pearson, 2007.

J’L Molt, Discrete Mathematics for Computer Scientists, Prentice Hall of India, 2005

Critical Path Analysis and PERT, Mind Results.

PERT/CPM for Project Scheduling & Management, Google search results.

Jeremy Siek, Graphs and Network Flows, Lecture Notes.

Combinatorial Algorithms Graphs and Network Flows, Lecture Notes, CS 660, San Diego State University.

Research Articles