University of Hyderabad Logo School of Mathematics and Statistics University of Hyderabad

Programmes → I.M.Sc. in Mathematical Sciences; M.Sc in Mathematics/Applied Mathematics

← Back to Courses

Graph Theory and Algorithms

Course Code: MA 491; MM 581; AM 581  |  Credits: 4  |  Prerequisite: Complex Analysis-I, Vector Calculus, Ordinary Differential Equations-I, Partial Differential Equations-I

Syllabus Details

  • Unit I:(Introductions to Graphs) Vertex Degree, Hand Shake Lemma, Subgraphs, isomorphism of graphs, Paths, Cycles and matrix representations of graphs, Trees, Spanning Trees, vertex connectivity.
  • Unit II:(Connectivity problems) Shortest path problems (Breadth first Search algorithm), Minimal spanning tree problem (Kruskal’s and Prim’s algorithms), Dijkstra’s algorithm in weighted graphs, with proofs of validity of each algorithms, Whitney’s theorem (2-connectivity).
  • Unit III:(Euler and Hamiltonian graphs) Euler’s tours and Hamiltonian cycles in graphs, Necessary and sufficient conditions for a graph to have Euler tour and Hamiltonian Cycles, Fluery’s algorithm, Chinese postman Problems and Traveling Salesman Problems.
  • Unit IV:(Matchings in Graphs) Matchings and M-Augmenting Paths, Hall’s Marriage Theorem, Tutte’s 1-factor theorem, Hungarian algorithm (maximal matching), Personal & Optimal Assignment Problems, Kuhn-Munkres Algorithm, general Chinese Postman problem.
  • Unit V:(Planar Graphs and Colouring) Euler’s formula, classification of Platonic bodies, Kuratowski’s theorem, Vertex and Edge colouring, Four Colour Problem.
  • Unit VI:(Directed graphs and Networks) Indegree and Outdegree of a vertex, Tournaments, Network flows and cuts, Max-Flow-Min-Cut Theorem and Menger’s theorem.

Course Learning Objective

  1. Learn basic notions such as Paths, Cycles and Spanning Trees.
  2. Learn about connectivity of graphs and solve shortest path problems.
  3. Solve Hall’s Marriage problem (Matchings).
  4. Learn about Eulerian tours and solve Chinese postman problem, Hamiltonian graphs and solve Traveling salesman problems.
  5. Understand Four Colour problem and planar graphs.
  1. Harary, F. Graph Theory. Addison-Wesley Publishing Co., London, 1969
  2. Clark, J. and Holton, D. A. A First Look at Graph Theory. World Scientific Publ. Co., Allied Publishers, 1995
  3. Gibbons, A. Algorithmic Graph Theory. Cambridge University Press
  4. Diestel, R. Graph Theory. GTM 173, Springer, 2010
← Back to Courses