CSC301.01 2015F, Class 31: Network Flows
========================================

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