THE UNIVERSITY OF SYDNEY

MATH2009 GRAPH THEORY


COURSE INFORMATION 2004

Lectures

Three lectures per week:
Monday 2 pm in Carslaw 173
Wednesday 2 pm in Carslaw 173
Friday 2 pm in Carslaw 173
Lectures run for 13 weeks. The last lecture will therefore be on Friday 29 October.

Lecturer

Sandra Britton
Room: Carslaw 521
Phone: 9351 4077
email: S.Britton@maths.usyd.edu.au

Tutorials

Tutorials (one per week) start in week 2. You should attend the tutorial given on your timetable. Printed tutorial sheets will be distributed in lectures. Any spare sheets will be placed in the wooden boxes in the corridor on Level 7 of Carslaw. Tutorial sheets will also be available here.

Assessment

Your final raw mark for this unit will be calculated as follows:
70%: Two-hour exam at end of semester 1.
10%: Assignment mark.
20%: Quiz mark.

Assignments

Two assignments will be collected and marked. Each assignment is worth 5% of your final raw mark.
Assignments will be due (in room 521) by 1 pm on
Friday 27 August and Friday 8 October.

You are encouraged to work with others in solving the assignment problems, but the work submitted must be your own.
Marked assignments will be returned to the pigeonholes on Carslaw Level 3.

Quizzes

Two quizzes will be held during the lecture hour, on
Wednesday 8 September and Wednesday 20 October.

Each quiz is worth 10% of your final raw mark.

Reference books

There is no textbook, but Introduction to Graph Theory by Robin Wilson is a very useful reference book.
Also recommended is the little blue book by Britton, Coleman and Henderson, which contains useful stuff from first year mathematics.
Both books are available at the Co-op Bookshop.

Another useful reference book is Discrete Mathematics with Graph Theory by Edgar Goodaire and Michael Parmenter.

Solutions

Tutorial and assignment solutions will be available here.

Consultation Times

I will try to be in my office every Monday from 1pm - 2pm, for consultation. However, you are welcome to come and see me at other times if I am not busy.

The aims of this course

  • To interest you in the subject matter of Graph Theory.
  • To illustrate some of the widespread applications of Graph Theory.
  • To encourage the development of methods of thinking which will be of benefit in some 3rd year mathematics courses, and in many other areas of applied mathematics and technology.
  • To extend your appreciation of mathematics, and to convince you that there is much more to it than just being able to handle the mechanics of evaluating integrals or solving equations.

    The objectives of this course

    By the end of this course, students should:

  • know the meaning of the following terms (in the context of Graph Theory): graph, vertex, edge, digraph, simple, complete, bipartite, degree of a vertex, degree sequence, isomorphic, walk, trail, path, cycle, connected, subgraph, Eulerian, Hamiltonian, tree, planar.
  • be able to determine whether or not a graph is Eulerian, and find an Euler trail.
  • be able to apply the shortest path algorithm, Kruskal's algorithm, Prim's algorithm, the algorithm for finding a maximum flow and a minimum cut in a transport network.
  • be able to count the number of spanning trees, using the matrix tree theorem.
  • be able to determine chromatic numbers, chromatic indices and chromatic polynomials.
  • know the hand-shaking lemma, Euler's formula for planar graphs, and Hall's theorem on matching, and use these results in problem solving.
  • know what is meant by the 4-colour map problem, and its solution.
  • be able to find the critical path in an activity network.

    The syllabus

    A weekly outline of the content covered in lectures will be provided here.


    Back to MATH2009 page.