Topic outline

  • General

    Collapse all Expand all

  • Study Period

    A revision session will take place in the Maths Lecture Theatre on Wednesday 1 May, 10am-12pm.

    We will look at past exam papers and discuss any questions you send in advance or ask on the day.

    You will be able to join the session remotely.

  • Week 1 - Introduction

    Topics covered in Week 1:
    • Definition and representation of graphs, digraphs, and networks
    • Isomorphic graphs and subgraphs
    • Degrees and neighborhoods
    • Paths and cycles
    By the end of Week 1, you should be able to
    • Define graphs, digraphs, and networks;
    • Determine if two graphs are isomorphic, and whether a graph is a subgraph of another graph;
    • Determine whether a graph exists in which the vertices have given degrees;
    • Identify paths and cycles in a graph and determine their length.

    Preparation

    Before the first lecture, please familiarise yourself with the module page and make sure you understand how the module is taught and examined.

    Lectures

    • Thursday 25 January at 12pm in Bancroft 1.13a
    • Thursday 25 January at 4pm in Bancroft 1.13

    Independent Study

    After revising the material covered this week, attempt the following exercises to test your understanding. Prepare for discussing the exercises in next week's seminar.

    • Mini Quiz

      This is a mini quiz on basic concepts concerning graphs. You can take it at any time, and as many times as you like.

    • Problem Sheet 1 File
      83.3 KB
    • Solutions to Problem Sheet 1 File
      101.6 KB
    • Handwritten Notes File
      This is a copy of what I have written and projected during lectures. The official version of the lecture notes is the typed version, which you can find at the top of the page.
      337.8 KB

  • Week 2 - Paths, Cycles, Trees

    Topics covered in Week 2:
    • Connectivity and strong connectivity
    • Trees
    By the end of Week 2, you should be able to
    • Identify the (strongly) connected components of a (di)graph;
    • Determine if a graph is a tree.

    Lectures

    • Thursday 1 February at 12pm in Bancroft 1.13a
    • Thursday 1 February at 4pm in Bancroft 1.13

    Seminar

    • Thursday 1 February at 5pm in Bancroft 1.13
    The seminar covers exercises from the previous week, and you can vote which exercises you would most like to see covered.

    Independent Study

    After revising the material covered this week, attempt the following exercises to test your understanding. They will be discussed in next week's seminar.

  • The Module

    Module Description

    The module provides an introduction to the theory of graphs from an algorithmic perspective. A graph models a set of objects and a pairwise relation among them, such as locations on a map and roads between these locations. An algorithm is a step-by-step procedure for solving a problem, such as that of finding a shortest path between two locations. Students will learn to model real-world problems using graphs, and to solve them both by hand and with the help of software tools. Mathematical properties of graphs will be used in developing new algorithms and showing that these algorithms work correctly and efficiently.

    Syllabus

    • Analysis of Algorithms. Determinism, Termination, running time. Informal definition of the classes P, NP, Co-NP and the notion of NP-completeness. Examples such as rank of a matrix, greatest common divisors, prime testing, knapsack problem.
    • Graphs and Digraphs. Paths, cycles, trees, connectedness. Algorithms to find the connected components of a graph and the strongly connected components of a digraph. Algorithms to construct breadth first search and depth first search spanning trees of a connected graph. Algorithms of Prim and Kruskal to find a minimum weight spanning tree in a connected graph. Greedy Algorithms.
    • Shortest and Longest paths. Dijkstra's algorithm to find a shortest path spanning tree in a graph or digraph. Moravék's algorithm to find a longest path spanning tree in an acyclic directed network. Critical Path Analysis.
    A selection of topics from the following:
    • Connectivity and flows in graphs. The max flow/min cut theorem. Menger's Theorem. The Ford-Fulkerson algorithm for finding a maximum flow in a network.
    • Matchings in graphs. König-Egerváry Theorem. Hall's Theorem. Algorithms for finding a maximum matching and a maximum weight matching in a bipartite graph. The Optimal Assignment Problem.
    • Euler tours. Euler's theorem. Algorithms for finding an Euler trail in a graph or digraph. The Chinese Postman Problem.
    • Approximation algorithms for hard problems. Examples such as Traveling salesman problem, maximum cut, minimum vertex cover.

    Learning Aims and Outcomes

    The module introduces students to a class of algorithms for solving real-world problems, and to the mathematical theory underlying the design and analysis of these algorithms. Students will learn to model real-world problems via graphs, and to apply common algorithms in order to solve these problems both by hand and with the help of software tools. They will also study mathematical properties of graphs, and learn to use these properties to explain why the algorithms work correctly and efficiently. The overall aim of the module is to provide students with the knowledge to confidently select among different approaches for modelling and solving real-world problems, and to judge the quality of a solution or entire problem-solving approach.

    By the end of the module students will be able to:

    1. Formally define a graph and combinatorial objects in a graph such as paths, flows, and matchings.
    2. Explain the notion of a combinatorial optimisation problem on a graph.
    3. Model real-world optimisation problems as problems of finding optimal paths, flows, or matchings.
    4. Explain and apply the standard algorithms for finding optimal paths, flows, or matchings and apply them to concrete problem instances.
    5. State and prove structural theorems about graphs such as Menger's Theorem and Hall's Theorem and explain their algorithmic significance.
    6. Prove the correctness of algorithms and give bounds on their running time.
    7. Explain the significance of the computational complexity of a problem and the running time of an algorithm and use this understanding to select an appropriate algorithm for solving optimisation problems on graphs.

  • Module Expectations

    Lectures

    • There will be three hours of lectures per week.
    • Lectures will take place live and will be recorded.
    • Lectures will use a virtual whiteboard and will follow the typed notes.
    • Do your best to attend all lectures rather than watching recordings, to ensure you keep up with the module and have the opportunity to ask questions.
    • During lectures you may want to take notes or annotate a copy of the typed notes.

    Independent Study

    • After lectures and before the end of each weak, revise the material covered during that week.
    • Use your notes or your annotations of the typed notes to revise.
    • Make sure you can quote definitions and results, and understand the proofs.

    Exercises

    • A set of exercises will be provided each weak.
    • Exercises are designed to revise concepts and results from lectures and deepen your understanding.
    • You should attempt all exercises at some point during the week, and seek help before the end of the week if you are struggling in any way.

    Tutorials

    • There will be one hour of tutorials per week, which may be listed as "seminars" in your timetable.
    • Tutorials will take place live and will be recorded.
    • In a typical tutorial we will solve one of the week's exercises and address questions you may have about the remaining exercises.

    Assessments

    • The module will be assessed by two pieces of assessed coursework during the semester, and by a final exam.
    • Each piece of assessed coursework will be worth 10% of the overall mark for the module.
    • The final exam will be worth 80% of the overall mark for the module.

  • Textbooks

    Typed lecture notes will be provided covering all examinable material. You will therefore not need any books to study for the module. However, if you would like to read what others have written about the same material, or about material not covered by the module, you could start from the books given in the reading list.

  • Assessment Structure

    The module will be assessed by
    • assessed coursework, worth 20% of the overall mark;
    • a final exam, worth 80% of the overall mark.
    • Two pieces of assessed coursework, each worth 10% of the overall mark for the module, will be due in Week 5 and in Week 10.
    • The final exam will take place online during the exam period. It will be 3 hours in duration with SpLD accommodations handled separately.

  • Final Assessment - 21st May 2024

  • Where to get help

    It is likely that there will be times during term when you get stuck while revising material from lectures or attempting exercises. This is normal, but you should seek help quickly so you do not fall behind.

    The best place to ask your questions is the student forum, where other students can benefit from the answer or you may work out an answer together. The module organiser and tutors will do their best to answer questions in the forum in a timely manner. If you see a question in the forum that you believe you have an answer or partial answer for, do give it a shot!

    You may also email the module organiser with questions, but in this case you may have to wait longer for an answer and should expect to be directed to the student forum.

    It can finally make sense to bring questions to tutorials or office hours, especially if these questions are more vague and you do not require an immediate answer.

  • Assessed Coursework

    • Complete the relevant exercises and upload your solutions before the deadline using the links below.
    • Solutions will be published shortly after each deadline, so late submissions cannot be accepted.

  • Final exam

    The final exam will be a handwritten exam and will be held online.

    I am posting below the exam papers from earlier editions of the module. I will not provide model solutions for these papers, but will be happy to discuss the papers and possible solutions.

    When preparing for the exam and attempting past exam questions, you should bear in mind that questions may differ somewhat depending on whether a past exam was a convential exam or an online exam. There is, for example, little point in asking you to write out a definition in an online exam when you could just copy it from your notes.

  • Feedback

    You will receive feedback on your assessed coursework. You will also be able to obtain further feedback from the module organiser, both in person during seminars and officer hours and via email.

  • Week 3 - Trees

    Topics covered in Week 3:
    • Characterizations of trees
    • Prüfer codes and the number of trees
    By the end of Week 3, you should be able to
    • State basic facts about trees implied by the characterizations;
    • Determine the Prüfer code of a tree, and the tree with a given Prüfer code.

    Lectures

    • Thursday 8 February at 12pm in Bancroft 1.13a
    • Thursday 8 February at 4pm in Bancroft 1.13

    Seminar

    • Thursday 8 February at 5pm in Bancroft 1.13

    Independent Study

    After revising the material covered this week, attempt the following exercises to test your understanding. They will be discussed in next week's seminar.

  • Week 4 - Spanning Trees, Complexity of Algorithms, Graph Traversal

    Topics covered in Week 4:
    • Spanning trees
    • Asymptotic bounds for the running time of an algorithm
    • Computational complexity
    • Breadth-first search and depth-first search
    By the end of Week 4, you should be able to
    • Identify spanning trees of a graph;
    • Give simple upper bounds on the running time of an algorithm;
    • Give informal definitions of the complexity classes P, NP, and NP-complete;
    • Find spanning trees and connected components.

    Lectures

    • Thursday 15 February at 12pm in Bancroft 1.13a
    • Thursday 15 February at 4pm in Bancroft 1.13

    Seminar

    • Thursday 15 February at 5pm in Bancroft 1.13

    Independent Study

    After revising the material covered this week, attempt the following exercises to test your understanding.

  • Online Reading List

  • Week 5 - Graph Traversal, Minimum Spanning Trees

    Topics covered in Week 5:
    • Tree search in graphs and digraphs
    • Directed acyclic graphs and topological orderings
    • Minimum spanning trees
    • Prim's algorithm, Kruskal's algorithm, and reverse-delete algorithm
    By the end of Week 5, you should be able to
    • Find shortest paths and cycles in graphs;
    • Find the strongly connected components of a digraph;
    • Determine if a digraph is a directed acyclic graph;
    • Find a minimum spanning tree of a network.

    Lectures

    • Thursday 22 February at 12pm in Bancroft 1.13a
    • Thursday 22 February at 4pm in Bancroft 1.13

    Seminar

    • Thursday 22 February at 5pm in Bancroft 1.13

    Independent Study

    After revising the material covered this week, attempt the following exercises to test your understanding.

  • Week 6 - Minimum Spanning Trees, Shortest Paths

    Topics covered in Week 6:
    • Conditions for edges contained or not contained in minimum spanning trees
    • Uniqueness of minimum spanning trees
    • Shortest paths and Dijkstra's algorithm
    By the end of Week 6, you should be able to
    • Identify edges contained or not contained in a minimum spanning tree;
    • Find a second minimum spanning tree of a network, or show that the minimum spanning tree is unique;
    • Find shortest paths in networks with non-negative weights.

    Lectures

    • Thursday 29 February at 12pm in Bancroft 1.13a
    • Thursday 29 February at 4pm in Bancroft 1.13

    Seminar

    • Thursday 29 February at 5pm in Bancroft 1.13

    Independent Study

    After revising the material covered this week, attempt the following exercises to test your understanding.

  • Week 8 - Shortest Paths, Negative Cycles, Longest Paths

    Topics covered in Week 8:
    • Bellman-Ford algorithm
    • Moravek's algorithm
    By the end of Week 8, you should be able to
    • find shortest paths or cycles of negative length in directed networks;
    • find longest paths in directed acyclic networks.

    Lectures

    • Thursday 14 March at 12pm in Bancroft 1.13a
    • Thursday 14 March at 4pm in Bancroft 1.13

    Seminar

    • Thursday 14 March at 5pm in Bancroft 1.13

    Independent Study

    After revising the material covered this week, attempt the following exercises to test your understanding.

  • Week 9 - Network Flows

    Topics covered in Week 9:
    • Flows and maximum flows
    • Cuts and minimum cuts
    • Residual capacities and residual network
    • Augmenting paths
    By the end of Week 9, you should be able to
    • explain the concepts of a flow and a cut in a directed network;
    • use a minimum cut to show that a flow is a maximum flow;
    • draw the residual network for a given flow;
    • use the residual network to identify an augmenting path.

    Lectures

    • Thursday 21 March at 12pm in Bancroft 1.13a
    • Thursday 21 March at 4pm in Bancroft 1.13

    Seminar

    • Thursday 21 March at 5pm in Bancroft 1.13

    Independent Study

    After revising the material covered this week, attempt the following exercises to test your understanding. They will be discussed in next week's tutorial.

  • Week 10 - Network Flows, Matchings

    Topics covered in Week 10:
    • Max-flow min-cut theorem
    • Ford-Fulkerson algorithm
    • Matchings
    By the end of Week 10, you should be able to
    • find a maximum flow and a minimum cut of a directed network;
    • show the existence of an integral maximum flow in the case with integral capacities;
    • explain the concepts of a matching, a maximum matching, and a matching saturating a given set of vertices.

    Lectures

    • Thursday 28 March at 12pm in Bancroft 1.13a
    • Thursday 28 March at 4pm in Bancroft 1.13

    Seminar

    • Thursday 28 March at 5pm in Bancroft 1.13

    Independent Study

    After revising the material covered this week, attempt the following exercises to test your understanding.

  • Week 11 - Matchings

    Topics covered in Week 11:
    • Bipartite graphs
    • Maximum matchings in bipartite graphs
    • Alternating and augmenting paths
    By the end of Week 11, you should be able to
    • determine whether a graph is bipartite;
    • find maximum matchings via maximum flows;
    • find maximum matchings via augmenting paths.

    Lectures

    • Thursday 4 April at 12pm in Bancroft 1.13a
    • Thursday 4 April at 4pm in Bancroft 1.13

    Seminar

    • Thursday 4 April at 5pm in Bancroft 1.13

    Independent Study

    After revising the material covered this week, attempt the following exercises to test your understanding.

  • Week 12 - Matchings, Euler Trails

    Topics covered in Week 12:
    • Hall's theorem
    • Euler trails and tours
    • Characterization of graphs containing an Euler trail or tour
    By the end of Week 12, you should be able to
    • prove non-existence of saturating matchings;
    • determine if a graph contains an Euler trail or tour;
    • find Euler trails and tours in graphs where they exist.

    Lectures

    • Thursday 11 April at 12pm in Bancroft 1.13a
    • Thursday 11 April at 4pm in Bancroft 1.13

    Seminar

    • Thursday 11 April at 5pm in Bancroft 1.13

  • Additional Material

    • In Our Time: Paul Erdős URL

      An episode of the BBC's In Our Time on mathematician Paul Erdős. It features graphs and one of the exercises on Problem Sheet 1.