Search | Previous : 618-351 | Next : 618-361
Handbook 1997 : Faculty of Science : Mathematics

618-352 Graph Theory

Credit Points:

15.0

Coordinator:

Dr A Byrne

Prerequisite/s:

Either 618-101 and 618-102 (1995 Handbook), or 618-111 and 618-112, or 618-121 and 618-122, or 618-200, or 618-211, or 618-100 and 618-101 (1995 Handbook), or 618-141 and 618-142. Alternatively, Mathematics 618-290 (Institute of Education).

Timetable:

Semester 2

Contact:

39 lectures (three a week)

Objectives:

On completion of this subject, students 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:

  • skills in implementing algorithms on graphs for finding objects such as minimum spanning trees, maximum matchings and flows;

  • skills at implementing approximation algorithms.

Appreciate:

  • the variety of applications of graph theory both within and outside mathematics.

Content:

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 up to three hours of end-of-semester written examination.
Search | Previous : 618-351 | Next : 618-361
Handbook 1997 : Faculty of Science : Mathematics 
Status:                   OFFICIAL 1997
Last Modified:            Wednesday March 12 3:36 pm
SGML to HTML Conversion:  Information Technology Services
Authorised by:            Academic Registrar
Email Enquiries:          Course_Information@registrar.unimelb.edu.au
Copyright © University of Melbourne 1997.