Syllabus  |   Lectures  |   Downloads  |   FAQ  |   Ask a question  |  
Course Co-ordinated by IIT Patna
Coordinators
 
Dr.Rajiv Misra
IIT Kanpur

 

Download Syllabus in PDF format



Untitled Document
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.
 

Week

Topics

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.

2.


Trees and Distance, Properties of Trees, Spanning Trees and Enumeration, Matrix-tree computation, Cayley's Formula, Prufer code.

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.

4.


Stable Matchings and Faster Bipartite Matching, Factors & Perfect Matching in General Graphs, Matching in General Graphs: Edmonds’ Blossom Algorithm

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.

6.


Vertex Coloring and Upper Bounds, Brooks’ Theorem and Color-Critical Graphs, Counting Proper Colorings.

7.


Planar Graphs, Characterization of Planar Graphs, Kuratowski's Theorem, Wagner's Theorem.

8.

Line Graphs and Edge-coloring, Hamiltonian Graph, Traveling Salesman Problem and NP-Completeness, Dominating Sets.

Discrete Mathematics


  1. D.B. West, Introduction to Graph Theory, Prentice Hall, 2001
  2. Jon Kleinberg and Eva Tardos, Algorithm Design, Addison-Wesley, 2005
  3. J.A.Bondy and U.S.R.Murty: Graph Theory, Springer, 2008.
  4. R.Diestel: Graph Theory, Springer( low price edition) 2000.
  5. F.Harary: Graph Theory, Narosa, (1988)
  6. C. Berge: Graphs and Hypergraphs, North Holland/Elsevier, (1973)

nil


nil



Important: Please enable javascript in your browser and download Adobe Flash player to view this site
Site Maintained by Web Studio, IIT Madras. Contact Webmaster: nptel@iitm.ac.in