# PDF Archive

Easily share your PDF documents with your contacts, on the Web and Social Networks.

## GraphTheoryAndCombinatoricsSyllabus .pdf

Original filename: GraphTheoryAndCombinatoricsSyllabus.pdf

This PDF 1.4 document has been generated by , and has been sent on pdf-archive.com on 23/08/2015 at 15:26, from IP address 103.5.x.x. The current document download page has been viewed 313 times.
File size: 151 KB (2 pages).
Privacy: public file

### Document preview

Graph Theory and Combinatorics

Sub code:10CS42
Hours/Week:04
Total hours:52

GRAPH THEORY AND COMBINATORICS

10CS42

IA Marks:25
Exam hours:03
Exam marks:100

UNIT-1
Introduction to Graph Theory: Definition and Examples Subgraphs Complements, and Graph
Isomorphism Vertex Degree, Euler Trails and Circuits.
UNIT-2
Introduction the Graph Theory Contd.: Planner Graphs, Hamiloton Paths and Cycles, Graph Colouring
and Chromatic Polynomials.
UNIT-3
Trees : definition, properties and examples, rooted trees, trees and sorting, weighted trees and prefix
codes
UNIT-4
Optimization and Matching: Dijkstra’s Shortest Path Algorithm, Minimal Spanning Trees – The
algorithms of Kruskal and Prim, Transport Networks – Max-flow, Min-cut Theorem, Matching Theory
UNIT-5
Fundamental Principles of Counting: The Rules of Sum and Product, Permutations, Combinations – The
Binomial Theorem, Combinations with Repetition, The Catalon Numbers
UNIT-6
The Principle of Inclusion and Exclusion: The Principle of Inclusion and Exclusion, Generalizations of
the Principle, Derangements – Nothing is in its Right Place, Rook Polynomials
UNIT-7
Generating Functions: Introductory Examples, Definition and Examples – Calculational Techniques,
Partitions of Integers, The Exponential Generating Function, The Summation Operator
UNIT-8
Recurrence Relations: First Order Linear Recurrence Relation, The Second Order Linear Homogeneous
Recurrence Relation with Constant Coefficients, The Non-homogeneous Recurrence Relation, The
Method of Generating Functions

1

Graph Theory and Combinatorics

10CS42

Table Contents

SI NO

Contents

Page No

1

Introduction to Graph Theory

3-36

2

Introduction to Graph Theory Continued

37-70

3

Trees

71-83

4

Optimization and Matching

84-99

5

Fundamental Principles of Counting

100-137

6

The Principle of Inclusion and Exclusion

138-153

7

Generating Functions

154-190

8

Recurrence Relations

191-216

2