Singapore University of Social Sciences

Principles of Graph Theory

Applications Open: 01 October 2019

Applications Close: 30 November 2019

Next Available Intake: January 2020

Schemes: Lifelong Learning Credit (L2C)

Language: English

Duration: 6 months

Fees: To be confirmed

Area of Interest: Science & Technology


Synopsis

Graph theory is a branch of discrete mathematics that formalizes methods for describing how things are connected. In the study of graphs, it becomes evident the efficient algorithms are necessary for solving problems of any significant magnitude. This course has been designed to emphasize the close tie between the theoretical and algorithmic aspects of graph theory. It covers the following topics: different types of graphs or digraphs, trees, connectivity and network flow, matching, planar graphs, vertex and edge coloring of graphs, as well as basic data structure and complexity analysis for basic algorithms. MTH303 is a blended on-line course, with at least 3 face-face sessions.

Level: 3
Credit Units: 5
Presentation Pattern: Every January
E-Learning: BLENDED - Learning is done MAINLY online using interactive study materials in MyUniSIM. 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

  • Graphs and digraphs.
  • Matrix representation.
  • Trees and properties of trees.
  • Spanning and counting trees.
  • Connectivity and flows.
  • Multi-terminal flows.
  • Matchings.
  • Transportation problems.
  • Planarity and coloring.
  • Independence and dominance.
  • Graphs and computing.
  • Divide-and-Conquer.

Learning Outcome

  • Verify structures as graphs and evaluate graph properties.
  • Interpret connected/network problems as a graph.
  • Analyze and test spanning trees, connectivity and network flow problems.
  • Employ matching and transportation problems.
  • Implement vertex, edge and general graph colorings.
  • Analyze graph algorithms.
  • Construct and formulate a range of mathematical techniques to solve a variety of quantitative problems.
  • Formulate solutions to problems individually and/or as part of a team.
  • Analyze and solve a number of problem sets within strict deadlines.
Back to top
Back to top