Unit Code: MTH907

Unit Name: Graph Theory and Applications

Description: The first part of this course is a brief introduction to the mathematical theory of graphs such as paths, connections and cycles, trees, cut edges and bonds, graph Isomorphism, and Bipartite graphs. Discuss vertex colourings, edge colourings, edge Chromatic Numbers, directed graphs and spanning trees. The second part is a discussion on the applications of this material to some areas such as the shortest path problem and Sperner\'s Lemma, the Connector problem, the Construction of Reliable Communication Networks, the Chinese Postman Problem, the travelling Salesman Problem, Assignment Problem, the Optimal Assignment Problem, the Timetabling problem, a storage problem, planarity algorithm and Perfect Square.

Learning Target Outcomes:

Prerequisite: Minimum Entry Requirements of the programme

Prerequisite Sentence: N/A

Credit Point: 30

Offered In: Semester 1,2