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

Contacts

Chief Examiner(s)

Professor David Wood

Unit Coordinator(s)

Professor David Wood

Notes

IMPORTANT NOTICE:
Scheduled teaching activities and/or workload information are subject to change in response to COVID-19, please check your Unit timetable and Unit Moodle site for more details.

Learning outcomes

On successful completion of this unit, you should be able to:
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.

Construct and write mathematical proofs of theorems about graphs.

5.

Execute, 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.

Teaching approach

Active learning

Assessment

1 - In-semester assessment
2 - Examination (3 hours and 10 minutes)

Scheduled and non-scheduled teaching activities

Applied sessions
Lectures

Workload requirements

Workload

Learning resources

Recommended resources

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