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.

• EC8007 Low power SoC Design Syllabus
• EC8702 Ad hoc and Wireless Sensor Networks Syllabus
• Regulation 2017 EC8351 Electronic Circuits I Syllabus
• Regulation 2017 EC8393 Fundamentals Of Data Structures In C Syllabus
• Regulation 2017 CS8085 Social Network Analysis Syllabus
• 2017 Regulation CS8076 Gpu Architecture and Programming Syllabus
• 2017 Regulation GE8073 Fundamentals of Nano Science Syllabus
• 2017 Regulation IT8077 Speech Processing Syllabus
• 2017 Regulation CS8001 Parallel Algorithms Syllabus
• 2017 Regulation CS8084 Natural Language Processing Syllabus
• Regulation 2017 CS8078 Green Computing Syllabus
• 2017 Regulation CS8080 Information Retrieval Techniques Syllabus
• 2017 Regulation GE8076 Professional Ethics in Engineering Syllabus
• 2017 Regulation CS8086 Soft Computing Syllabus
• 2017 Regulation CS8074 Cyber Forensics Syllabus