Graph Theory

Overview

The course on Graph Theory is a 4 credit course which contains 32 modules. This course deals with some basic concepts in graph theory like properties of standard graphs, Eulerian graphs, Hamiltonian graphs, Chordal graphs, Distances in graphs, Planar graphs, graph connectivity and Colouring of graphs. Further few graph Algorithms have also been discussed. This course is designed on par with the UGC syllabus.The learners, as an outcome of successful completion will have a basic background of graph theory which has diverse applications in the areas of computer science, biology, chemistry, physics, sociology, and engineering.

Syllabus

Week- I
1. Introduction to graphs2. Basic properties of graphs3. Complete and bi-partite graphs
Week - II
4. Isomorphism of graphs5. Paths and circuits
Week - III
6. Eulerian Graphs
7. Hamiltonian cycles
Week - IV
8. Matrix representation of graphs9. Chordal graphs10. Weighted graphs
Week - V
11. Matchings in graphs12. Hall's 'marriage' theorem and its application13. Travelling salesman’s problem & Chinese postman problem
Week - VI
14. Distances in graphs15. Shortest path and Dijkstra’s algorithm16. Floyd – Warshall Algorithm
17. Bellman-Ford Algorithm
Week - VII
18. Trees19. Spanning tree in graphs
Week - VIII
20. Minimum spanning tree algorithms21. Kruskal’s algorithm22. Independence sets and covering in graphs
Week - IX
23. Planar graphs24. Euler's formula
Week - X
25. Cut vertices and Cut edges26. Edge connectivity
Week - XI
27. Vertex Colouring of graphs
28. Edge Colouring of graphs29. The four-colour and five-colour theorems
Week - XII30. Perfect Graphs31. Applications of graphs in switching theory32. Directed Graphs (or Digraphs)