MTH6105 Algorithmic Graph Theory

Week 5: Maximum Network Flows 1

  Covered this week:
Lecture 1:
Networks, Maximal_Rooted_Network_Subtree algorithm. Edge cuts in networks. Notes PDF file icon
Lecture 2:
Flows in networks. Net flow of a vertex or set of vertices and a key Lemma. Notes PDF file icon
Lecture 3:
Cuts vs flows. Max flow vs min cut. The 'minimax' idea. Notes PDF file icon

Week 5 Coursework: watch the boxes below!
Coursework 5
Solutions
Download pdf
Submit: 15.02
Download pdf

Extra: the fascinating history of maximum flows

Week 4 Week 6 Back to MTH6105 main page School of Maths Sciences