Skip to content

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 … For more content click the Read More button below.

Offerings

S2-01-CLAYTON-ON-CAMPUS

Rules

Enrolment Rule

Contacts

Chief Examiner(s)

Professor David Wood

Unit Coordinator(s)

Professor David Wood

Notes

This Level 4 unit and its Level 3 counterpart MTH3170 share the same core content and learning activities such as seminars and applied classes. However, studies at Level 4 are distinguished from those at Level 3 by a deeper understanding of mathematical theories and their applications, higher levels of critical thinking, and greater autonomy in learning

Learning outcomes

On successful completion of this unit, you should be able to:
1.

Critically analyse and synthesise concepts in graph theory.

2.

Evaluate and illustrate the extensive applications and significance of graph theory across diverse fields, particularly in mathematics and computer science

3.

Apply some of the most famous theorems in graph theory, such as the max-flow-min-cut theorem, the marriage theorem, and the 4-colour theorem, to solve complex problems.

4.

Construct mathematical proofs of theorems about graphs, demonstrating creativity and depth of understanding

5.

Design, implement, and critically evaluate algorithms for solving various graph optimisation problems.

6.

Exhibit mastery in advanced problem-solving techniques, working both independently and collaboratively with staff and fellow students.

7.

Communicate complex mathematical arguments and concepts related to graph theory with clarity and precision, both in written and oral forms, suitable for academic and professional contexts

Teaching approach

Active learning

Assessment

1 - Continuous assessment

2 - Final assessment - Exam (3 hours and 10 minutes)

Scheduled and non-scheduled teaching activities

Applied sessions

Seminars

Workload requirements

Workload

Other unit costs

Costs are indicative and subject to change.

Miscellaneous items required (unit course reader, printing, stationery) - $120.

Availability in areas of study

Advanced computer science
Applied mathematics
Computational science
Mathematical statistics
Mathematics
Pure mathematics