Graph Theory detailed syllabus for Computer Science & Design (CSD) for 2021 regulation curriculum has been taken from the Anna Universities official website and presented for the CSD students. For course code, course name, number of credits for a course and other scheme related information, do visit full semester subjects post given below.
For Computer Science & Design 6th Sem scheme and its subjects, do visit CSD 6th Sem 2021 regulation scheme. For Open Elective-I scheme and its subjects refer to CSD Open Elective-I syllabus scheme. The detailed syllabus of graph theory is as follows.
Course Objectives:
Download the iStudy App for all syllabus and other updates.
Unit I
INTRODUCTION TO GRAPHS
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
Bridges – Trees – Characterization and properties of trees – Cut vertices – Connectivity.
Unit III
Download the iStudy App for all syllabus and other updates.
Unit IV
PLANARITY AND COLOURING
Planar Graphs – The Euler Identity – Non planar Graphs – Vertex Colouring – Lower and Upper bounds of chromatic number.
Unit V
OPTIMIZATION GRAPH ALGORITHMS
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.
Course Outcomes:
At the end of this course, the student will be able to
- Apply graph models for solving real world problem.
- Understand the importance the natural applications of trees and graph connectivity.
- Understand the characterization study of Eulerian graphs and Hamiltonian graphs.
- Apply the graph colouring concepts in partitioning problems.
- Apply the standard optimization graph algorithms in solving application problems.
Text Books:
Download the iStudy App for all syllabus and other updates.
Reference Books:
- Balakrishnan R. and Ranganathan K., “A Text Book of Graph Theory”, Springer – Verlag, New York, 2012.
- Douglas B. West, “Introduction to Graph Theory”, Pearson, Second Edition, New York, 2018.
For detailed syllabus of all the other subjects of Computer Science & Design 6th Sem, visit CSD 6th Sem subject syllabuses for 2021 regulation.
For all Computer Science & Design results, visit Anna University CSD all semester results direct link.