620-352 Graph Theory

Note

Students may only gain credit for one of 620-352 and 618-352 (1997 Handbook).

Credit Points

Coordinator

Prerequisites

620-111 and 620-112 (1997 Handbook 618-111 and 618-112); or 620-121 and 620-122 (1997 Handbook 618-121 and 618-122); or 620-141 and 620-142 (1997 Handbook 618-141 and 618-142); or 620-200 (1997 Handbook 618-200); or 620-211 (1997 Handbook 618-211).

Semester

Contact

Subject Description

Students completing this subject should comprehend

• the basic concepts of graph theory including paths and cycles, trees and counting, automorphism groups, planar graphs, colouring properties, chromatic polynomials, matching theory, cycle space;

have developed the ability to

• implement algorithms on graphs for finding objects such as minimum spanning trees, maximum matchings and flows;
• implement approximation algorithms;

and appreciate

• 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, cycle space. Algorithms: Minimum spanning trees, maximum matchings, flows, approximation algorithm.

Assessment

Up to 26 pages of written assignments and a three-hour end-of-semester written examination.