Singapore University of Social Sciences

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
E-Learning: BLENDED - Learning is done MAINLY online using interactive study materials in Canvas. Students receive guidance and support from online instructors via discussion forums and emails. This is supplemented with SOME face-to-face sessions. If the course has an exam component, this will be administered on-campus.

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