THE UNIVERSITY OF
COURSE INFORMATION 2004
Three lectures per week:
Monday 2 pm in Carslaw 173
Lectures run for 13 weeks. The last lecture will therefore be on Friday 29 October.
Wednesday 2 pm in Carslaw 173
Friday 2 pm in Carslaw 173
Room: Carslaw 521
Phone: 9351 4077
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
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.
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.
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.
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.
Tutorial and assignment solutions will be available
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.
A weekly outline of the content covered in lectures will be provided
Back to MATH2009 page.