OMA351 Syllabus - Graph Theory - 2021 Regulation - Open Elective | Anna University

OMA351 Syllabus - Graph Theory - 2021 Regulation - Open Elective | Anna University

OMA351	GRAPH THEORY	L T P C

3003

COURSE OBJECTIVES:

• To understand the graph models and basic concepts of graphs.
• To study the characterization and properties of trees and graph connectivity.
• To provide an exposure to the Eulerian and Hamiltonian graphs.
• To introduce Graph colouring and explain its significance.
• To provide an understanding of Optimization Graph Algorithms.

UNIT I	INTRODUCTION TO GRAPHS	9

Graphs and Graph Models – Connected graphs – Common classes of graphs – Multi graphs and Digraphs – Degree of a vertex – Degree Sequence – Graphs and Matrices – Isomorphism of graphs.

UNIT II	TREES AND CONNECTIVITY	9

Bridges – Trees – Characterization and properties of trees – Cut vertices – Connectivity.

UNIT III	TRAVERSABILITY	9

Eulerian graphs – Characterization of Eulerian graphs – Hamiltonian graphs – Necessary condition for Hamiltonian graphs – Sufficient condition for Hamiltonian graphs.

UNIT IV	PLANARITY AND COLOURING	9

Planar Graphs – The Euler Identity – Non planar Graphs – Vertex Colouring – Lower and Upper bounds of chromatic number.

UNIT V	OPTIMIZATION GRAPH ALGORITHMS	9

Dijkstra’s shortest path algorithm – Kruskal’s and Prim’s minimum spanning tree algorithms – Transport Network – The Max-Flow Min-Cut Theorem – The Labeling Procedure – Maximum flow problem.

TOTAL: 45 PERIODS

COURSE OUTCOMES: At the end of this course, the student will be able to

CO1: Apply graph models for solving real world problem.
CO2: Understand the importance the natural applications of trees and graph connectivity.
CO3: Understand the characterization study of Eulerian graphs and Hamiltonian graphs.
CO4: Apply the graph colouring concepts in partitioning problems.
CO5: Apply the standard optimization graph algorithms in solving application problems.

TEXT BOOKS:

1. Gary Chatrand and Ping Zhang, “Introduction to Graph Theory”, Tata McGraw – Hill companies Inc., New York, 2006.
2. Ralph P. Grimaldi, “Discrete and Combinatorial Mathematics, An applied introduction" Fifth edition, Pearson Education, Inc, Singapore, 2004.

REFERENCES:

1. Balakrishnan R. and Ranganathan K., “A Text Book of Graph Theory”, Springer – Verlag, New York, 2012.
2. Douglas B. West, “Introduction to Graph Theory”, Pearson, Second Edition, New York, 2018.