Anna University 2013 Regulation - CS6702 Graph Theory and Applications - Syllabus - Download
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.
Anna University 2013 Regulation - CS6702 Graph Theory and Applications - Syllabus - Download
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.
Anna University 2013 Regulation - CS6702 Graph Theory and Applications - Syllabus - Download
0 Comments