# Singapore University of Social Sciences

## Principles of Graph Theory (MTH303)

Applications Open: 01 October 2022

Applications Close: 30 November 2022

Next Available Intake: January 2023

Language: English

Duration: 6 months

Fees: \$1378 View More Details on Fees

Area of Interest: Science & Technology

Schemes: Alumni Continuing Education (ACE), Lifelong Learning Credit (L2C)

Funding: To be confirmed

School/Department: School of 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

### 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

• Show how to prove a mathematical statement in graph theory.
• Determine whether given graphs are Hamiltonian/semi-Hamiltonian, Eulerian/semi-Eulerian and/or planar.
• Calculate the chromatic number, dominance number or independence number of a given graph.
• Demonstrate mathematical reasoning by providing proofs to mathematical statements in graph theory.
• Apply algorithms covered in the course to graph theory problems.
• Compute edge connectivity/vertex connectivity, weights of spanning trees and/or number of spanning trees of a given graph.