Graph Theory
This is a course intended for second year B.Math students.
The following syllabus (prone to changes and not strictly same as the official syllabus) is only indicative of the topics to be covered. The topics covered so-far in the class have been coloured in green.
Syllabus: Graphs, Motivation, Examples and Basic properties - Degree, Path, Cycle, Girth, Diameter. Connectivity. k-connectivity. Euler cycles. Trees, Spanning trees, Cayley's formula, Minimal spanning trees, Algorithms. Min-Cut-Max-Flow theorem. Menger's Theorem. Hall's marriage theorem. Covers, Matchings, Independent sets. Tutte's 1-Factor Theorem. Berge-Tutte Formula. Planar Graphs. Euler's formula. Five Colour theorem. Dual Graphs. Vector spaces and matrices associated with Graphs - Cycle space, Cut space, Boundary space, Incidence Matrix, Adjacency Matrix and Laplacian matrix. Kirchoff's Matrix tree theorem.
References 1 and 2 are the primary references for the course. Reference 5 is very useful for the last part on algebraic graph theory.
Special Topics :
1) Sperner's Lemma and an introduction to Probabilistic method ( This part was a special lecture by Manjunath Krishnapur, IISc).
2) Electrical Networks and Graphs.
Teaching Assistant : Sagnik Sen. Office : S16.
References :
1. B. Bollobas: Modern Graph Theory.
2. Douglas B. West : Introduction to Graph Theory.
3. F. Harary : Graph Theory.
4. R. Diestel : Graph Theory.
5. R. B. Bapat : Graphs and Matrices
Assignments :
For past exams, see the following webpage and for time-table, exam schedule et al., see the following webpage.
Additional Notes : (unless mentioned the notes are not written by me)
2) Maze generation via spanning tree algorithms.
3) Other visualizations : Prim's Algorithm, Kruskal's algorithm, Boruvka's algorithm, Dijkstra's Algorithm
4) Visualizing complexity of Shakespeare's plays.
5) Graph isomorphism algorithm.
8) MIT Notes on Planar Graphs.
Mark Allotment :
Assignments/Quizzes : 25
Mid-Semester : 25
End-Semester : 50.