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