CS6702 GRAPH THEORY AND APPLICATIONS | Syllabus

CS6702 GRAPH THEORY AND APPLICATIONS L T P C 3 0 0 3

OBJECTIVES:
 The student should be made to:

• Be familiar with the most fundamental Graph Theory topics and results.
• Be exposed to the techniques of proofs and analysis.

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                   (8)
 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.

UNIT IV                             PERMUTATIONS & COMBINATIONS                                             (9)
Fundamental principles of counting - Permutations and combinations - Binomial theorem - combinations with repetition - Combinatorial numbers - Principle of inclusion and exclusion - Derangements - Arrangements with forbidden positions.

UNIT V                             GENERATING FUNCTIONS                                                               (10)
 Generating functions - Partitions of integers - Exponential generating function – Summation operator - Recurrence relations - First order and second order – Non-homogeneous recurrence relations - Method of generating functions.
TOTAL: 45 PERIODS

TEXT BOOKS:
1. Narsingh Deo, “Graph Theory: With Application to Engineering and Computer Science”, Prentice Hall of India, 2003.
2. Grimaldi R.P. “Discrete and Combinatorial Mathematics: An Applied Introduction”, Addison Wesley, 1994.

REFERENCES:
1. Clark J. and Holton D.A, “A First Look at Graph Theory”, Allied Publishers, 1995.
2. Mott J.L., Kandel A. and Baker T.P. “Discrete Mathematics for Computer Scientists and Mathematicians” , Prentice Hall of India, 1996.
3. Liu C.L., “Elements of Discrete Mathematics”, McGraw Hill, 1985.
4. Rosen K.H., “Discrete Mathematics and Its Applications”, McGraw Hill, 2007.


Click here to download full syllabus                           AULibrary.com