Tuesday, July 10, 2012

CS9032-GRAPH THEORY-ANNA UNIVERSITY SYLLABUS IT


CS9032-GRAPH THEORY-ANNA UNIVERSITY SYLLABUS IT


CS9032                                         GRAPH THEORY                                           L T P C
3  0 0 3
AIM:
Knowledge of basic Graph Theory and development of skills in problem solving.

OBJECTIVES:

·         Acquiring knowledge of the basic tools in Graph Theory. Some advanced topics including some algorithms.

UNIT I             INTRODUCTION                                                                                        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 BOOK: 

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.


CLICK HERE FOR ALL SUBJECTS

7/10/2012 12:27:00 PM

0 comments:

Post a Comment

Related Posts Plugin for WordPress, Blogger...