Graph Theory and Applications

CS6702
CSE IT

Unit 1

INTRODUCTION

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. 99

Part A (2m) Part B (16m)

Unit 2

TREES, CONNECTIVITY & PLANARITY

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. I

Part A (2m) Part B (16m)

Unit 3

MATRICES, COLOURING AND DIRECTED GRAPH

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.

Part A (2m) Part B (16m)

Unit 4

PERMUTATIONS & COMBINATIONS

Fundamental principles of counting - Permutations and combinations - Binomial theorem - combinations with repetition - Combinatorial numbers - Principle of inclusion and exclusion - Derangements - Arrangements with forbidden positions.

Part A (2m) Part B (16m)

Unit 5

GENERATING FUNCTIONS

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.

Part A (2m) Part B (16m)
Related Notes