BSc Computer Science and Mathematics / Course details

Year of entry: 2020

Course unit details:
Discrete Mathematics

Unit code MATH20902
Credit rating 10
Unit level Level 2
Teaching period(s) Semester 2
Offered by Department of Mathematics
Available as a free choice unit? No

Overview

Modern Discrete Mathematics is a broad subject bearing on everything from logic to logistics. Roughly speaking, it is a part of mathematics that touches on those subjects that Calculus and Algebra can't: problems where there is no sensible notion continuity or smoothness and little algebraic structure. The subject, which is typically concerned with finiteor at the most countablesets of objects, abounds with interesting, concrete problems and entertaining examples.

Pre/co-requisites

Unit title Unit code Requirement type Description
Foundations of Pure Mathematics A MATH10101 Pre-Requisite Compulsory
Foundations of Pure Mathematics B MATH10111 Pre-Requisite Compulsory

Aims

This module aims to engage students with a circle of concrete problems and applications, algorithmic techniques and basic theorems arising in graph theory.

 

Learning outcomes

On completion of this unit successful students will 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-Chvátal 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 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.

 

 

 

Syllabus

Graph Theory & Applications: [22]


The basic definitions about graphs should be familiar from the Mathematical Workshop MATH10001, so after a brief review we will treat the following topics:
 

• Basic notions & notations, trees [5]
• Eulerian tours & Hamiltonian cycles [4]
• The Principle of Inclusion/Exclusion and the Matrix-Tree Theorem [4]
• Shortest paths & applications to scheduling [4]
Planar graphs & map colouring [5]
 

Assessment methods

Method Weight
Other 20%
Written exam 80%
  • Coursework; Weighting within unit 20%. This will consist of a problem set due on the last Friday before Easter and handed out two weeks earlier.
  • 2 hours end of semester examination; Weighting within unit 80%

Feedback methods

Feedback tutorials will provide an opportunity for students' work to be discussed and provide feedback on their understanding.  Coursework or in-class tests (where applicable) also provide an opportunity for students to receive feedback.  Students can also get feedback on their understanding directly from the lecturer, for example during the lecturer's office hour.

Recommended reading

Recommended: Dieter Jungnickel (2013), Graphs, Networks and Algorithms, 4th edition, Springer.
Further Reading:
Harris, Hurst & Mossinghoff (2008), Combinatorics and Graph Theory, Springer.
Marcus (2008), Graph Theory: a problem oriented approach, Mathematical Association of America.
Biggs (1993), Algebraic Graph Theory, 2nd edition, CUP.
Cameron (2017), Notes on Counting: An Introduction to Enumerative Combinatorics, CUP.

Study hours

Scheduled activity hours
Lectures 24
Tutorials 11
Independent study hours
Independent study 64

Teaching staff

Staff member Role
Mark Muldoon Unit coordinator

Return to course details