Periods/week : 3 Periods & 1 Tut /week.                                                                  Ses. : 30 Exam : 70 Examination (Practical): 3hrs.                                                                                   Credits: 4

PART  I: COMBINATORICS

1.    FOUNDATION:   Basics-   Sets-   Relations-   Proof          methods-   Problem-solving   strategies- Mathematical Induction.
2.    COMINATORICS:    Basics  of  counting-Combinations  and  Permutations-  Enumeration   of Combinations  &  Permutations  without  repetitions  and  without  repetitions-  with  constrained repetitions-Binomial Coefficients-Binomial and Multinomial theorems- Principle  of Inclusion- Exclusion
3.    RECURRENCE RELATIONS: Generating  Functions  of Sequences- Calculating Coefficients of Generating Functions- Recurrence Relations- Solving Recurrence Relations using Substitution and Generating    Functions-Method             of    Characteristic    Roots-Solutions    of    homogeneous    and inhomogeneous recurrence relations.

PART  II GRAPH THEORY

4.    FUNDAMENTAL  CONCEPTS:    what  is  a  Graph-Paths-Cycles-Trails-Vertex  Degrees  and Counting-Directed  Graphs-Trees  and  Distance-Spanning  Trees-Enumeration-Optimization  and Trees.
5.    MATCHINGS AND CONNECTIVITY :   Matchings and Covers-Algorithms and applications of matching-Matchings in General graphs-Cuts and Connectivity-k-connected graphs-Network flow problems.
6.    COLORING  AND  PLANAR  GRAPHS:    Vertex  coloring  and  upper  bounds-Structure  of  k- chromatic  Graphs-Enumerative  Aspects-Embeddings  and  Euler’s  formula-Characterization  of Planar  graphs-Parameters  of  Planarity-Edges  and  Cycles-Line  Graphs  and  edge-coloring- Hamiltonian Cycles-Planarity-coloring and cycles.

 

TEXT BOOKS:

1.    J.L. Mott, Abraham Kandel & Theodore P. Baker, “ Discrete mathematics for Computer
Scientists & Mathematics”, Prentice-Hall of India Ltd.  New Delhi. (Chapters 1,2,3)
2.    Douglas B. West, “Introduction to Graph Theory”, Pearson Education Asia, New Delhi.
(Chapters 1,2,3,4,5,6,7)

REFFERENCE BOOKS:

1.    Michel Townsend,  “Discrete Mathematics: Applied Combinatorics and graph theory”,  The
Benjamin/Cummings Publishing Company”, California.
2.    Kenneth H Rosen.  “Discrete Mathematics and Its Applications, Tata McGrahHill Publishing
Company, New Delhi.
3.    Robin J. Wilson, “Introduction to Graph Theory” Pearson Education Asia, New Delhi.

tejus mahiCSE 3.1 SyllabusIT 4.1 SyllabusCombinatorics & Graph Theory Syllabus,CSE,CSE Syllabus,IT,IT Syllabus
Periods/week : 3 Periods & 1 Tut /week.                                                                  Ses. : 30 Exam : 70 Examination (Practical): 3hrs.                                                                                   Credits: 4 PART  I: COMBINATORICS 1.    FOUNDATION:   Basics-   Sets-   Relations-   Proof          methods-   Problem-solving   strategies- Mathematical Induction. 2.    COMINATORICS:    Basics  of  counting-Combinations  and...