BSc Computer Science and Mathematics

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.

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

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.

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]
 

• 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.
• End of semester examination; Weighting within unit 80%

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: 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.

The independent study hours will normally comprise the following. During each week of the taught part of the semester:

·         You will normally have approximately 60-75 minutes of video content. Normally you would spend approximately 2-2.5 hrs per week studying this content independently

·         You will normally have exercise or problem sheets, on which you might spend approximately 1.5hrs per week

·         There may be other tasks assigned to you on Blackboard, for example short quizzes or short-answer formative exercises

·         In some weeks you may be preparing coursework or revising for mid-semester tests 

Together with the timetabled classes, you should be spending approximately 6 hours per week on this course unit.

The remaining independent study time comprises revision for and taking the end-of-semester assessment.