Advanced Graph Theory focuses on problem solving using the most important notions of graph theory with an in-depth study of concepts on the applications in the field of computer science. This course provides an in-depth understanding of Graphs and fundamental principles and models underlying the theory, algorithms, and proof techniques in the field of Graph Theory. Emerging applications of Graph Theory in Computer Science domain will be covered for significant impact. Upon completing this course, students will have intimate knowledge about how the graph theory play an important role to solve the technology driven and research oriented problems.INTENDED AUDIENCE : UG & PG (both)PREREQUISITES : Discrete MathematicsINDUSTRY SUPPORT : Companies like Microsoft Research, Google,Facebook, LinkedIn and also start-ups are most eager to apply graph technology.
Advanced Graph Theory
Indian Institute of Technology Kanpur , Indian Institute of Technology Patna and NPTEL via Swayam
Overview
Syllabus
Week 1:Introduction to Graphs & its Applications, Basics of Paths, Cycles, and Trails, Connection, Bipartite Graphs, Eulerian Circuits, Vertex Degrees and Counting, Degree-sum formula, The Chinese Postman Problem and Graphic Sequences.Week 2:Trees and Distance, Properties of Trees, Spanning Trees and Enumeration, Matrix-tree computation, Cayley's Formula, Prufer code.Week 3:Matchings and Covers, Hall's Condition, Min-Max Theorem, Independent Sets, Covers and Maximum Bipartite Matching, Augmenting Path Algorithm, Weighted Bipartite Matching, Hungarian Algorithm.Week 4:Stable Matchings and Faster Bipartite Matching, Factors & Perfect Matching in General Graphs, Matching in General Graphs: Edmonds’ Blossom AlgorithmWeek 5:Connectivity and Paths: Cuts and Connectivity, k-Connected Graphs, Network Flow Ford-Fulkerson Labeling Algorithm, Max-Flow Min-cut Theorem, Menger's Proof using Max-Flow Min-Cut Theorem.Week 6:Vertex Coloring and Upper Bounds, Brooks’ Theorem and Color-Critical Graphs, Counting Proper Colorings.Week 7:Planar Graphs, Characterization of Planar Graphs, Kuratowski's Theorem, Wagner's Theorem.Week 8:Line Graphs and Edge-coloring, Hamiltonian Graph, Traveling Salesman Problem and NP-Completeness, Dominating Sets.
Taught by
Rajiv Misra
