Singapore University of Social Sciences

Applications of Graph Theory

Applications of Graph Theory (MTH304)

Synopsis

Graph theory has widely used in many areas such as operational research, computation, chemistry and electronics as graphs are natural models for a variety of situations. This course focuses on some important real-world applications which include the topics of project planning and scheduling, electrical circuit analysis, kinematic design, some geometric design, error-correcting codes and experiment design

Level: 3
Credit Units: 5
Presentation Pattern: Every January

Topics

  • Planning and scheduling.
  • Knapsack problem.
  • Circuit analysis.
  • Solving circuit equations.
  • Geometric design.
  • Incidence structures.
  • Kinematic design.
  • Planar kinematic systems.
  • Error-correcting codes.
  • Hamming codes.
  • Blocking in experimental design.
  • Balanced design and codes.

Learning Outcome

  • Show how to prove a mathematical statement in graph theory.
  • Determine whether a given design is balanced.
  • Calculate the vertices, edges, faces of a given polyhedron.
  • Demonstrate mathematical reasoning by providing proofs to mathematical statements in graph theory.
  • Apply algorithms covered in this course to graph theory problems.
  • Compute spanning trees of a given graph.
Back to top
Back to top