Course Materials for MATH20902 : Discrete Mathematics
Lecture Notes
The notes linked below are meant as an example for those considering the module in 2020-21: I'll provide
similar, complete notes for all the materials I'll discuss (on video) this year. For additional reading I urge you to have
a look at the online versions of Dieter Jungnickel's very useful book, Graphs, Networks and Algorithms.
I wrote the course while studying a copy of the
2nd edition,
but you might also like to look at the
4th edition,
which appeared in 2013.
You can also get the
notes for the whole term in a single file.
to the top
Opportunities for feedback
The main channel for formal, written feedback in this module is the coursework. It will be a problem set similar
to the ones below, but devoted to an application that uses the ideas from the course. You'll prepare written solutions
and I'll mark them over the Easter Break, providing both written comments and a mark. In addition, the weekly examples classes
provide further opportunities for verbal feedback and—for students who bring written solutions to the
exercises—on-the-spot marking and written feedback as well.
Problem Sets & Solutions
The problem sets, which appear roughly every week throughout
the term, are an important part of the course. I always
publish the problems and the solutions at the same time.
to the top
Coursework & Exams
|
Coursework
|
End-of-Term Formative Assessment
Exams
|
to the top
Intended Learning Outcomes
Once you've successfully completed this module you should be able to:
-
Define what it means for two graphs to be isomorphic
and determine, with rigorous supporting arguments, whether two
(small) graphs are isomorphic.
-
Explain what the chromatic number of a graph is,
determine it for small graphs and apply the idea to scheduling
problems.
-
Say what it means for a graph to be Eulerian
and determine whether small graphs or multigraphs are
Eulerian.
-
Say what it means for a graph to be Hamiltonian
and use the Bondy-Chávtal theorem to prove that a graph
is Hamiltonian.
-
Construct the graph Laplacian and apply the Matrix-Tree
Theorem to count the number of spanning trees or spanning
arborescences contained in a graph.
-
Construct the adjacency matrix of a graph and exploit the
connection between powers of the adjacency matrix to count walks.
Also, define the operations
of tropical arithmetic, construct the weight matrix associated with
a weighted graph and use its tropical matrix powers to find the
lengths of shortest paths.
-
Given a project defined by a set of tasks, along with their
their durations and prerequisites, use critical path analysis
to determine how quickly the project can be completed.
-
Say what it means for a graph to be planar; state
and apply Kuratowski's theorem and determine whether a graph
is planar or not.
|