# Singapore University of Social Sciences

## Principles of Graph Theory (MTH303)

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