Introduction to flow networks (classroom lecture)
Introduction to flow networks and the Ford–Fulkerson algorithm.
This is an old recording of one of my lectures that I found on a CD-ROM today. In case you are wondering, I don't have a recording of the follow-up lecture.
00:00 The maximum-flow problem
07:26 Idea for algorithm
12:02 Residual capacity and network
21:21 Ford-Fulkerson algorithm
25:28 Cuts
31:34 Max-flow min-cut theorem
Extended list of times
00:00 The maximum-flow problem
01:10 Flow network
03:43 Small example
04:45 Flow
07:26 Idea for algorithm
10:33 Ford-Fulkerson overview
12:02 Residual capacity and network
14:58 Residual network
17:25 flow in residual network
18:09 Augmenting flow
21:21 Ford-Fulkerson algorithm
23:49 Properties of Ford-Fulkerson
25:28 Cuts
30:13 max-flow less or equal min-cut
31:34 Max-flow min-cut theorem
32:23 Proof, step 1
33:08 Proof, step 2
36:00 Proof, step 3