# CS1016 Graph Theory Syllabus

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.

Previous
Next Post »