YoVDO

Graph Theory

Offered By: Indian Institute of Science Education and Research, Pune via Swayam

Tags

Graph Theory Courses Computer Science Courses Engineering Courses Chemistry Courses Physics Courses Sociology Courses Biology Courses Mathematical Analysis Courses Graph Algorithms Courses

Course Description

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)


Taught by

Prof. Soumen Maity

Tags

Related Courses

Aplicaciones de la teoría de grafos a la vida real
Miríadax
Aplicaciones de la Teoría de Grafos a la vida real
Universitat Politècnica de València via UPV [X]
Introduction to Computational Thinking and Data Science
Massachusetts Institute of Technology via edX
Genome Sequencing (Bioinformatics II)
University of California, San Diego via Coursera
Algorithmic Information Dynamics: From Networks to Cells
Santa Fe Institute via Complexity Explorer