Page 282 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 14: Network Flows
Mandeep Kaur, Lovely Professional University

Unit 14: Network Flows Notes

CONTENTS

Objectives
Introduction
14.1 Network Flow
14.1.1 Ford Fulkerson Method
14.1.2 Comparison Networks

14.2 Network Flow Problem
14.3 Minimum Spanning Tree
14.3.1 Kruskal’s Algorithm
14.3.2 Prim’s Algorithm

14.4 Summary
14.5 Keywords
14.6 Self Assessment
14.7 Review Questions
14.8 Further Readings

Objectives

After studying this unit, you will be able to:
Explain network fl ow
Describe problem of network fl ow
Know minimum spanning tree

Introduction
We use graphs as models of practical situations involving routes: the vertices represent the cities
and edges represent the roads or some other links, specially in transportation management,
Assignment problems and many more optimization problems. Electric circuits are another
obvious example where interconnections between objects play a central role. Circuits elements
like transistors, resistors, and capacitors are intricately wired together. Such circuits can be
represented and processed within a computer in order to answer simple questions like “Is
everything connected together?” as well as complicated questions like “If this circuit is built, will
it work?”

14.1 Network Flow

Network flow is an advanced branch of graph theory. The problem resolves around a special
type of weighted directed graph with two special vertices: the source vertex, which has no
incoming edge, and the sink vertex, which has no outgoing edge. By convention, the source
vertex is usually labelled s and the sink vertex labelled t.

LOVELY PROFESSIONAL UNIVERSITY 277