06CS42 - GRAPH THEORY AND COMBINATORICS Regulation 2006 - 2007 |
PART – A |
UNIT 1 |
1. Introduction to Graph Theory: Definitions and Examples,
Subgraphs, Complements, and Graph Isomorphism, Vertex Degree,
Euler Trails and Circuits |
UNIT 2 |
2. Introduction to Graph Theory contd.: Planar Graphs, Hamilton Paths
and Cycles, Graph Colouring, and Chromatic Polynomials |
UNIT 3 |
3. Trees: Definitions, Properties, and Examples, Routed Trees, Trees
and Sorting, Weighted Trees and Prefix Codes.
|
UNIT 4 |
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.
|
PART – B |
UNIT 5 |
5. Fundamental Principles of Counting: The Rules of Sum and
Product, Permutations, Combinations – The Binomial Theorem,
Combinations with Repetition, The Catalon Numbers |
UNIT 6 |
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 |
7. Generating Functions: Introductory Examples, Definition and
Examples – Calculational Techniques, Partitions of Integers, The
Exponential Generating Function, The Summation Operator.
|
UNIT 8 |
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.
|
REFERENCE |
TEXT BOOKS: |
Discrete and Combinatorial Mathematics, Ralph P. Grimaldi, 5th
Edition, PHI/Pearson Education, 2004.
(Chapter 11, Chapter 12.1 to 12.4, Chapter 13, Chapter 1, Chapter
8.1 to 8.4, Chapter 9 Chapter 10.1 to 10.4).
|
Reference Books |
1. Graph Theory and Combinatorics, Dr. D.S. Chandrasekharaiah,
Prism, 2005.
2. Introduction to Graph Theory, Chartrand Zhang, TMH, 2006.
3. Introductory Combinatorics, Richard A. Brualdi, 4th Edition,
Pearson Prentice Hall, 2004.
4. Graph Theory Modeling, Applications, and Algorithms, Geir
Agnarsson & Raymond Geenlaw, Pearson Prentice Hall, 2007.
* Note.
The Question paper consists of two parts A and B containing 4
questions each. The student is required to answer any 5 questions
selecting at least two questions from each part.
|
|