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).