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

• 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.
Back to top
Back to top