Overview

• Preliminaries.
  • Admin.
  • Upcoming Work.
  • Extra Credit.
  • Questions.
• The max-flow problem.
• Augmenting paths.
• The Ford-Fulkerson algorithm.
• Bipartite matching.

Preliminaries

Admin

• Homework due next Wednesday
  • 6-20, 6-21, 6-23, 6-24, 6-25
• We will look at the coding problems on Monday.

Extra Credit

Academic

• Any other Long-String event (e.g., Friday night concert)
• CS Table Tuesday: Something Positive
• CS Extras Thursday: ?

Peer

Questions

The max-flow problem

Given a weighted, directed graph, and two labeled vertices find the most "information" (the max flow) from source to target.

Augmenting paths

Used for finding max-flow.

A path from source to target with only positive edge weights.

Incorrect algorithm

while augmenting paths exist
  choose one
  identify the least edge weight
  decrement every edge in the path by that weight
  increment every corresponding edge in the flow graph by that weight

Why is it incorrect? Make a graph in which picking an augmenting path makes it impossible to get the max flow.

The Ford-Fulkerson algorithm

while augmenting paths exist
  choose one
  identify the least edge weight
  decrement every edge in the path by that weight
  increment every back edge in the path by that weight
  increment every corresponding edge in the flow graph by that weight

Ford-Fulkerson is slow if you don't make good choices about which path to take.

Normal solution: Use DFS to find the path.

Bipartite matching

Two sets of vertices, L and R, with edges only between L and R (no edges within L, no edges within R).

Find maximal set of edges, M, s.t. each vertex in L is incident to at most one edge in M, each vertex in R is incident to at most on edge in M.

Solve this using Max Flow

Yay! Many of you could.