620-352 Graph Theory

Credit Points

HECS Band

Coordinator

Prerequisites

One of 620-112, 620-122, [99]620-142, [99]620-200, 620-211.

Semester

Contact

Subject Description

This subject introduces the basic concepts of graph theory including paths and cycles, trees and counting, automorphism groups, planar graphs, colouring properties, chromatic polynomials, matching theory. Students should develop the ability to implement algorithms on graphs for finding objects such as minimum spanning trees, maximum matchings and flows; and to implement approximation algorithms. This subject demonstrates the variety of applications of graph theory both within and outside mathematics.

Introduction to Graph Theory: Basic concepts, paths and cycles, trees and counting, automorphism groups; planar graphs, colouring properties, chromatic polynomials, matching theory, probabilistic method. Algorithms: Minimum spanning trees, maximum matchings, flows, approximation algorithm.

Assessment

Up to 24 pages of written assignments and a 3-hour end-of-semester written examination.