Chapter 7

• want to model a flow network
• associated with edges are capacity, which is non negative
• single source node s
• single sink node t
• Need to define flow
• need to figure out how to get maximum flow over network
• Need a residual graph
• algorithm on p. 342
• algorithm O(mC)

• let f be any s-t flow, and (A, B) any s-T cut then V(f) = Fout(a) - fin(a)
• proofs of why this is maximum flow on 347
• max flow = min cut
• 7.9 - if f is an s-t flow sucht that there is no s-t path in the residual graph Gf, then there is an s-t cut (a*, b*) in G for which v(F) = c(A*,B*) consequently f has maximum value of any flow in G, and (A*, B*) has the minimum capacity of any s-t cut in G.
• 7.10 - the flow f returned by the ford - fulkerson algorithm is a maximum flow.
• 7.11 given a flow f of maximum value, we can compute as s-t cut of minimum capacity in O(m) time.
• 7.13 - in every flow network, the maximum value of an s-t flow is equal to the minimum capacity of an s-t cut. 7.14 if all capacities in the flow network are integers, then there is a maximum flow f for which every flow value f(e) is an integer.

• going back to our bipartite problem, but there is a source node and a sink node. and the bipartite two teams are split one with the source node and one with the sink node
• 7.34 m' contains k edges
• each node in x is the tail of at most one edge in m'
• each node in y is the head of at most one edge in m'
• the size of the maximum matching in G is equal to the value of the maximum flow in G' and hte edges in such a matching in G are the edges that carry flow from x to y in G.
• can use the ford fulkerson to find this maximum matching in bipartite graphs in O(mn) time

The problem

• Circulations with demands
• we have demand nodes and supply nodes
• the supply has negative deamnd

design the algorithm

• put all the supply nodes with one source node
• put all the demand nodes with the one sink node
• pretty simple if we think of it that way.

The problem

• questions for consumers abotu products
• only a certain number of questions for each consumer
• only a certain number of customers have each product
• more details on the algorithm on page 286
• images are so helpful on 386