VL4153 Graph Theory and Optimization Techniques Syllabus:
VL4153 Graph Theory and Optimization Techniques Syllabus – Anna University PG Syllabus Regulation 2021
COURSE OBJECTIVES:
To introduce graph as mathematical model to solve connectivity related problems.
To introduce fundamental graph algorithms.
To familiarize the students with the formulation and construction of a mathematical model for a linear programming problem in a real life situation.
To provide knowledge and training using non-linear programming under limited resources for engineering and business problems.
To understand the applications of simulation modelling in engineering problems.
UNIT I GRAPHS
Graphs and graph models – Graph terminology and special types of graphs – Matrix representation of graphs and graph isomorphism – Connectivity – Euler and Hamilton paths.
UNIT II GRAPH ALGORITHM
Graph Algorithms – Directed graphs – Some basic algorithms – Shortest path algorithms – Depth – First search on a graph – Theoretic algorithms – Performance of graph theoretic algorithms – Graph theoretic computer languages.
UNIT III LINEAR PROGRAMMING
Formulation – Graphical solution – Simplex method – Two-phase method – Transportation and Assignment Models.
UNIT IV NON-LINEAR PROGRAMMING
Constrained Problems – Equality constraints – Lagrangean Method – Inequality constraints – Karush – Kuhn-Tucker (KKT) conditions – Quadratic Programming.
UNIT V SIMULATION MODELLING
Monte Carlo Simulation – Types of Simulation – Elements of Discrete Event Simulation – Generation of Random Numbers – Applications to Queuing systems.
TOTAL : 60 PERIODS
COURSE OUTCOMES:
At the end of the course, students will be able to
apply graph ideas is solving connectivity related problems.
apply fundamental graph algorithms to solve certain optimization problems.
formulate and construct mathematical models for linear programming problems and solve the transportation and assignment problems.
model various real life situations as optimization problems and effect their solution through Non-linear programming.
apply simulation modeling techniques to problems drawn from industry management and other engineering fields.
TEXT BOOKS:
1. Taha H.A, “Operation Research: An Introduction”, Ninth Edition, Pearson Education, New Delhi, 2010.
2. Gupta P. K, and Hira D.S., “Operation Research”, Revise Edition, S. Chand and Company Ltd., 2012.
3. Sharma J.K., “Operation Research”, 3rd Edition, Macmillan Publishers India Ltd., 2009.
4. Douglas B. West, “Introduction to Graph Theory”, Pearson Education, New Delhi, 2015.
5. Balakrishna R., Ranganathan. K., “ A text book of Graph Theory”, Springer Science and Business Media, New Delhi, 2012.
6. Narasingh Deo, “Graph Theory with Applications to Engineering and Computer Science”, Prentice Hall India,1997.