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.
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)