## March 27, 2010

### CS1016 GRAPH THEORY SYLLABUS B.E. COMPUTER SCIENCE AND ENGINEERING ANNA UNIVERSITY CHENNAI– REGULATIONS – 2004

ANNA UNIVERSITY CHENNAI: CHENNAI – 600 025
B.E DEGREE PROGRAMME COMPUTER SCIENCE AND ENGINEERING
(Offered in Colleges affiliated to Anna University)
CURRICULUM AND SYLLABUS – REGULATIONS – 2004
B.E. COMPUTER SCIENCE AND ENGINEERING
LIST OF ELECTIVES FOR COMPUTER SCIENCE AND ENGINEERING

CS1016 GRAPH THEORY

AIM
To provide fundamental ideas on graph theory required for the study of Computer Science.

OBJECTIVES
• Understand basic notions of Graph Theory
• Knowing Fundamental Theorems in Graph Theory
• Study of algorithmic Graph Theory

UNIT I 9
Graphs – Introduction – Isomorphism – Sub graphs – Walks, Paths, Circuits – Connectedness – Components – Euler Graphs – Hamiltonian Paths and Circuits – Trees – Properties of trees – Distance and Centers in Tree – Rooted and Binary Trees.

UNIT II 9
Spanning trees – Fundamental Circuits –Spanning Trees in a Weighted Graph – Cut Sets – Properties of Cut Set – All Cut Sets – Fundamental Circuits and Cut Sets – Connectivity and Separability – Network flows – 1-Isomorphism – 2-Isomorphism – Combinational and Geometric Graphs – Planer Graphs – Different Representation of a Planer Graph.

UNIT III 9
Incidence matrix – Submatrices – Circuit Matrix – Path Matrix – Adjacency Matrix – Chromatic Number – Chromatic partitioning – Chromatic polynomial - Matching - Covering – Four Color Problem – Directed Graphs – Types of Directed Graphs – Digraphs and Binary Relations – Directed Paths and Connectedness – Euler Graphs – Adjacency Matrix of a Digraph.

UNIT IV 9
Algorithms: Connectedness and Components – Spanning tree – Finding all Spanning Trees of a Graph –Set of Fundamental Circuits – Cut Vertices and Separability – Directed Circuits.

UNIT V 9
Algorithms: Shortest Path Algorithm – DFS – Planarity Testing – Isomorphism
TOTAL : 45
TEXT BOOK
1. Narsingh Deo, “Graph Theory: With Application to Engineering and Computer Science”, PHI, 2003.
REFERENCE
1. R.J. Wilson, “Introduction to Graph Theory”, Fourth Edition, Pearson Education, 2003.