====== Chapter 7 ======

Network Flow notes

===== Intro & 7.1: Maximum Flow & Ford-Fulkerson =====

    * Network flow problems include the bipartite matching problem, among others. Networks are graphs whose edges carry something and whose nodes facilitate passing traffic between edges.
    * Network models can be seen as having capacity on edges, or how much they can carry.
    * They have sources, or nodes that have no in-edges, and sinks, or nodes without out-edges.
    * We define a flow network as
        * A digraph G=(V,E) with
        * Associated capacity for each edge, c_e
        * A single sink t
        * a single source s
    * We say an s-t flow is a function f: (each edge in E) to a nonnegative real number so that f(e) = flow(e)
        * For each edge, 0<=f(e)<=c_e
        * For each node in V, excluding s and t, the flow into e is equal to the flow out of e.
    * The value of a flow is the amount of flow generated at s.
    * Given a flow network, what if we want to arrange our traffic to efficiently use our capacity?
    * We do this as follows:
        * For each edge e, f(e) is 0 initially
        * While an s-t path remains in the residual graph
            * Consider a simple path s-t path, P
            * f' = augment(f,P)
            * f = f'
            * the residual graph is the residual graph of f'
    * We use augment(f,P):
        * b = bottleneck(P,f)
        * for each (u,v)-edge e in P,
            * if e is a forward edge, increase f(e)+ = b
            * else e = v,u and f(e) - = b
        * return f
    * If all capacities, this algorithm (the Ford-Fulkerson algorithm) terminates in C ( = sum(c_e) for all out edges of s) iterations of the while-loop
       * And it can be implemented in O(mC) time
    * Wordy but interesting, 7/10

===== 7.2: Network Flows & Minimum Cuts =====

   * Consider an s-t cut: a partition (A,B) of V such that s∈A and t∈B. The capacity of an (A,B) cut, or c(A,B) is the sum of all c_e for each out edge e of A.
   * For an s-t flow and an s-t cut (A,B), v(f) = the out flow of A - the in-flow of A
   * For any s-t flow and any s-t cut (A,B), v(f) < = c(A,B).
   * If f is an s-t flow so that the residual graph has no s-t path, there is an s-t cut (_A,_B) in G so that f(v) = c(_A,_B). Then, v(f) is the maximum of all flows in G and (_A,_B) has the minimum capacity of any s-t cut.
   * the Ford-Fulkerson flow is a maximum flow
   * Reminded me of real analysis, straightforward, 7/10

===== 7.5: Bipartite Matching =====

   * We wish to match edges to a subset such that each node appears in max one edge of the edge subset, such that the matching has the largest possible size.
   * We solve this as follows:
       * Look at G, constructing a flow network by directing all edges in G from X to Y, then adding a node s and an (s,x) edge from s to each node in X. We add a node t and an edge (y,t) from every edge in Y to t. We give every edge in the flow network a capacity of 1. Then we compute the maximum s-t flow.
    * The size of the maximum matching in G equals the max flow in the flow network G' and edges carrying flow from X to Y in G' are in the matching in G.
    * We can do this in O(mn) time.
    * What if the graph has no perfect matching?
        * If this //isn't// the case, for all A in side X of G, we have more nodes in A's adjacent nodes than in the A component.
        * Either we can find a perfect matching or an appropriate subset _G in O(mn) time.
    * 4/10

===== 7.7: Maximum Flow Extensions =====

    * What if we have a set of sources and a set of sinks?
    * Consider the case where sources have fixed supply and sinks have fixed demand, like rainway lines shipping from factories to retail outlets.
    * Now the circulation fulfills
        * for each edge e, 0<=f(e)<=c_e
        * for each vertex v, the in minus out flows equal the demand of v.
    * We can also do this with circulations that have lower bounds for demand.
    * Boring and wordy, 2/10