0
2106

# CS8077- GRAPH THEORY AND APPLICATIONS Syllabus 2017 Regulation

GRAPH THEORY AND APPLICATIONS Syllabus 2017 Regulation,CS8077- GRAPH THEORY AND APPLICATIONS Syllabus 2017 Regulation

CS8077Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  GRAPH THEORY AND APPLICATIONSÂ  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  L P T CÂ
Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â 3 0 0 3

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 Enumeration- Labeled 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 ,