CS2051 GRAPH THEORY

CS2051 GRAPH THEORY L T P C
3 0 0 3
UNIT I NTRODUCTION 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 TREES, CONNECTIVITY, PLANARITY 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 MATRICES, COLOURING AND DIRECTED GRAPH 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 ALGORITHMS 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 ALGORITHMS 9
Algorithms: Shortest Path Algorithm – DFS – Planarity Testing – Isomorphism.
TOTAL: 45 PERIODS
TEXT BOOKS:
1. Narsingh Deo, “Graph Theory: With Application to Engineering and Computer
Science”, Prentice Hall of India, 2003.
REFERENCES:
1. R.J. Wilson, “Introduction to Graph Theory”, Fourth Edition, Pearson Education,
2003.