BSc CS sem 3 Combinatorics and Graph Theory techmax/notes Download |
Objectives:
To give the learner a broad exposure of combinatorial Mathematics through applications especially
the Computer Science applications.
Expected Learning Outcomes:
1. Appreciate beauty of combinatorics and how combinatorial problems naturally arise in
many settings.
2. Understand the combinatorial features in real world situations and Computer Science
applications.
3. Apply combinatorial and graph theoretical concepts to understand Computer Science
concepts and apply them to solve problems
Unit I
Introduction to Combinatorics: Enumeration, Combinatorics and
Graph Theory/ Number Theory/Geometry and Optimization, Sudoku
Puzzles.
Strings, Sets, and Binomial Coefficients: Strings- A First Look,
Combinations, Combinatorial, The Ubiquitous Nature of Binomial
Coefficients, The Binomial, Multinomial Coefficients.
Induction: Introduction, The Positive Integers are Well Ordered, The
Meaning of Statements, Binomial Coefficients Revisited, Solving
Combinatorial Problems Recursively, Mathematical Induction, and
Inductive Definitions Proofs by Induction. Strong Induction
15L
Unit II
Graph Theory: Basic Notation and Terminology, Multigraphs: Loops
and Multiple Edges, Eulerian and Hamiltonian Graphs, Graph Coloring,
Planar Counting, Labeled Trees, A Digression into Complexity Theory.
Applying Probability to Combinatorics, Small Ramsey Numbers,
Estimating Ramsey Numbers, Applying Probability to Ramsey Theory,
Ramsey’s Theorem The Probabilistic Method
15L
Unit III
Network Flows: Basic Notation and Terminology, Flows and Cuts,
Augmenting Paths, The Ford-Fulkerson Labeling Algorithm,
15L
A Concrete Example, Integer Solutions of Linear Programming
Problems. Combinatorial Applications of Network Flows: Introduction,
Matching in Bipartite Graphs, Chain partitioning, Pólya’s Enumeration
Theorem: Coloring the Vertices of a Square.
Textbook(s):
1) Applied Combinatorics, Mitchel T. Keller and William T. Trotter, 2016,
http://www.rellek.net/appcomb.
Additional Reference(s):
1) Applied Combinatorics, sixth.edition, Alan Tucker, Wiley; (2016)
2) Graph Theory and Combinatorics, Ralph P. Grimaldi, Pearson Education; Fifth edition
(2012)
3) Combinatorics and Graph Theory, John Harris, Jeffry L. Hirst, Springer( 2010).
4) Graph Theory: Modeling, Applications and Algorithms, Agnarsson, Pearson Education India
(2008).