Regulation 2017 CS8077 Graph Theory and Applications Syllabus

OBJECTIVES:

• To understand fundamentals of graph theory.
• To study proof techniques related to various concepts in graphs.
• To explore modern applications of graph theory.

UNIT I 9

Introduction – Graph Terminologies – Types of Graphs – Sub Graph- Multi Graph – Regular Graph – Isomorphism – Isomorphic Graphs – Sub-graph – Euler graph – Hamiltonian Graph -Related Theorems.

UNIT II 9

Trees -Properties- Distance and Centres – Types – Rooted Tree– Tree EnumerationLabeled Tree – Unlabeled Tree – Spanning Tree – Fundamental Circuits- Cut Sets -Properties – Fundamental Circuit and Cut-set- Connectivity- Separability -Related Theorems.

UNIT III 9

Network Flows – Planar Graph – Representation – Detection – Dual Graph – Geometric and Combinatorial Dual – Related Theorems – Digraph – Properties – Euler Digraph.

UNIT IV 9

Matrix Representation – Adjacency matrix- Incidence matrix- Circuit matrix – Cut-set matrix -Path Matrix- Properties – Related Theorems – Correlations. Graph Coloring – Chromatic Polynomial – Chromatic Partitioning – Matching – Covering – Related Theorems.

UNIT V 9

Graph Algorithms- Connectedness and Components- Spanning Tree- Fundamental Circuits- Cut Vertices- Directed Circuits- Shortest Path – Applications overview.

TOTAL : 45 PERIODS

OUTCOMES:

Upon completion of this course, the students should be able to

• Understand the basic concepts of graphs, and different types of graphs
• Understand the properties, theorems and be able to prove theorems.
• Apply suitable graph model and algorithm for solving applications.

TEXT BOOKS:

• 1. Narsingh Deo, “Graph Theory with Application to Engineering and Computer Science”, Prentice-Hall of India Pvt.Ltd, 2003.
• 2. L.R.Foulds , “Graph Theory Applications”, Springer ,2016.

REFERENCES:

1. Bondy, J. A. and Murty, U.S.R., “Graph Theory with Applications”, North Holland Publication,2008.
2. West, D. B., ―Introduction to Graph Theory‖, Pearson Education, 2011.
3. John Clark, Derek Allan Holton, ―A First Look at Graph Theory‖, World Scientific Publishing Company, 1991.
4. Diestel, R, “Graph Theory”, Springer,3rd Edition,2006.
5. Kenneth H.Rosen, “Discrete Mathematics and Its Applications”, Mc Graw Hill ,2007.