MTH3175 · Network mathematics (Advanced)

Overview

This unit provides an introduction to graph theory, which is the mathematics of networks. Topics covered include trees, Eulerian tours, Hamiltonian cycles, shortest path problem, bipartite graphs, matchings, graph colouring, max-flow problem, graph connectivity, independent sets, planarity, random graphs. Applications to a variety of the sciences will be presented. You will learn how to write proofs and analyse algorithms.

Areas of study: Minor in Mathematics Major in Mathematics Extended major in Mathematics Major in Pure mathematics Extended major in Pure mathematics Extended major in Applied mathematics Applied studies (Discrete mathematics) in the Bachelor of Applied Data Science Major in Computer science (approval pending)

Offerings

Assessment

The Handbook lists an examination for this unit.

Assessment details may change. Please refer to the assessment information in Moodle closer to the start of the teaching period.

Requisites

Learning outcomes

1. Apply the basic concepts of graph theory;
2. Demonstrate the importance and breadth of applications of graph theory in mathematics and the sciences, especially computer science;
3. Apply some of the most famous theorems of graph theory such as the max-flow-min-cut theorem, the marriage theorem, and the 4-colour theorem;
4. Understand, construct and write mathematical proofs of theorems about graphs;
5. Execute and analyse and prove correctness of algorithms for solving various graph optimisation problems;
6. Demonstrate advanced problem solving skills, both individually and collectively with staff and fellow students;
7. Demonstrate advanced skills in the written and oral presentation of mathematical arguments.

Workload

• Three 1-hour seminars; • One 2-hour applied class (in weeks 2-12) and • 7 hours of independent study per week.

Student experience, not official rules. Nothing here changes what the Handbook says.