# Graph Theory And Combinatorics

 Course Code : 10CS42 Author : uLektz University : Visvesvaraya Technological University, Karnataka (VTU) Regulation : 2010 Categories : Computer Science Format : ePUB3 (DRM Protected) Type : eBook

FREE

Description :Graph Theory And Combinatorics of 10CS42 covers the latest syllabus prescribed by Visvesvaraya Technological University, Karnataka (VTU) for regulation 2010. Author: uLektz, Published by uLektz Learning Solutions Private Limited.

Note : No printed book. Only ebook. Access eBook using uLektz apps for Android, iOS and Windows Desktop PC.

##### Topics
###### Unit - 1 Introduction to Graph Theory:

1.1 Definitions and Examples

1.2 Subgraphs, Complements and Graph Isomorphism

1.3 Vertex Degree, Euler Trails and Circuits.

###### Unit – 2 Introduction to Graph Theory contd.:

2.1 Planar Graphs

2.2 Hamilton Paths and Cycles

2.3 Graph Colouring and Chromatic Polynomials.

###### Unit - 3 Trees:

3.1 Definitions, Properties and Examples, Rooted Trees, Trees and Sorting, Weighted Trees and Prefix Codes

###### Unit - 4 Optimization and Matching:

4.1 Optimization and Matching: Dijkstra’s Shortest Path Algorithm

4.2 Minimal Spanning Trees, The algorithms of Kruskal and Prim, Transport Networks

4.3 Max-flow, Min-cut Theorem, Matching Theory.

###### Unit - 5 Fundamental Principles of Counting:

5.1 Fundamental Principles of Counting: The Rules of Sum and Product, Permutations, Combinations

5.2 The Binomial Theorem, Combinations with Repetition, The Catalon Numbers

###### Unit - 6 The Principle of Inclusion and Exclusion:

6.1 The Principle of Inclusion and Exclusion, Generalizations of the Principle

6.2 Derangements – Nothing is in its Right Place, Rook Polynomials.

###### Unit - 7 Generating Functions:

7.1 Introductory Examples, Definition and Examples

7.2 Calculational Techniques, Partitions of Integers, The Exponential Generating Function, The Summation Operator.

###### Unit - 8 Recurrence Relations:

8.1 Recurrence Relations: First Order Linear Recurrence Relation, The Second Order Linear Homogeneous Recurrence Relation with Constant Coefficients, The Non-homogeneous Recurrence Relation

8.2 The Method of Generating Functions.