The book “Combinatorics and Graph Theory” is the outcome of my conviction that there should be a text-cum-reference book for the newly introduced subject in order that it be understood better by student community at large. The book has its genesis and is the result of some of the young and fresh college teachers who wanted a reliable and comprehensive book which contain simplified yet rigorous treatment of the subject matter. A genuine effort has been made to catch the spirit of the subject. I have tried to acquaint the reader with fine points and details of the subject as best as I can.
The students are already familiar at plus-two level with elementary techniques of Permutation and Combination, Principles of Mathematical Induction, Binomial theorem, etc. In this book, the main idea is to explain students not only the said topics but also extend these further by logical development of the subject. As a result, students would be able to handle problems arising in the application to these topics in Computer Science.
Each concept has been illustrated by suitable solved examples followed by a graded list of problems for practice. The subject of ‘Combinatorics and Graph Theory’ is not a spectator’s sport. Students should try to solve as many exercise problems as possible.
The material in each unit is organized topic-wise. In Unit – I, there are certain complex topics like Combinatorial proofs and Proof without words which according to me are difficult to understand and teach. Unit – I also explains about applications of Catalan numbers in balanced parentheses, mountain ranges and polygon triangulation. Unit – II consists of Graph Theory and problem solving by making use of simple principles of graph theory. I tried to explain how this graph theory can be applicable in problem solving in day-to-day life. In Unit – III, I have tried explaining principles of Min cut – Max flow by giving lucid explanation, suitable examples, algorithms and pictorial presentation.
At the end, I have given/compiled adequate number of problems for Practicals / tutorials to ease teachers’ work in providing these as assignment to student.
Contents –
Unit – I
1. Introduction to Combinatorics
2. Strings, Sets and Binomial Coefficients
3. Induction
Unit – II
4. Graph Theory
5. Applying Probability to Combinatorics
Unit – III
6. Network Flows
7. Combinatorial Applications of Network Flows
8. Polya’s Enumeration Theorem
Practical Questions
Bibliography
