IIT Patna free course on Advanced Graph Theory / FDP
Advanced Graph Theory
IIT Patna
Overview
IIT Patna has launched the online course on Advanced Graph Theory. This course will start from 15 Feb 2021, It's an 8-week online course by the online platform SWAYAM. 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.
Instructor
Prof. Rajiv Misra
This is an AICTE approved FDP
Topics
The following topics will be covered in this online course,
- 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.
- Trees and Distance, Properties of Trees, Spanning Trees and Enumeration, Matrix-tree computation, Cayley's Formula, Prufer code.
- Matchings and Covers, Hall's Condition, Min-Max Theorem, Independent Sets, Covers, and Maximum Bipartite Matching, Augmenting Path Algorithm, Weighted Bipartite Matching, Hungarian Algorithm.
- Stable Matchings and Faster Bipartite Matching, Factors & Perfect Matching in General Graphs, Matching in General Graphs: Edmonds’ Blossom Algorithm
- 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.
- Vertex Coloring and Upper Bounds, Brooks’ Theorem and Color-Critical Graphs Counting Proper Colorings.
- Planar Graphs, Characterization of Planar Graphs, Kuratowski's Theorem, Wagner's Theorem.
- Line Graphs and Edge-coloring, Hamiltonian Graph, Traveling Salesman Problem and NP-Completeness, Dominating Sets.
Certificate
The exam is optional for a fee of Rs 1000/- (Rupees one thousand only). Without a certificate this course is free.
PREREQUISITES
Discrete Mathematics
Eligibility
UG & PG (both)