CS1016 GRAPH THEORY

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 3 0 0 100

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.