Introduction to Graph Theory: Definitions and Examples, Subgraphs, Complements, and Graph Isomorphism, Vertex Degree, Euler Trails and Circuits
Introduction to Graph Theory contd.: Planar Graphs, Hamilton Paths and Cycles, Graph Colouring, and Chromatic Polynomials
Trees: Definitions, Properties, and Examples, Routed Trees, Trees and Sorting, Weighted Trees and Prefix Codes
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
Fundamental Principles of Counting: The Rules of Sum and Product, Permutations, Combinations – The Binomial Theorem, Combinations with Repetition, The Catalon Numbers
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
Generating Functions: Introductory Examples, Definition and Examples – Calculational Techniques, Partitions of Integers, The Exponential Generating Function, The Summation Operator
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