Chapter 7

• Transportation networks - networks where the edges carry traffic and the nodes act as switches passing traffic between edges
• Source nodes generate traffic
• Sink nodes absorb traffic
• Edges have capacities and flows
  • Capacity shows the maximum amount of flow an edge can take
  • Flow is the amount of flow that is on the edge currently
  • Flow is always less than or equal to capacity
• Flow Network - directed graph:
  • Each edge has a capacity which is a non-negative number
  • There is a single source node s
  • There is a single sink node t
  • No edge enters the source node and no edge exits the sink node
  • There is at least one edge incident to each node
  • All capacities are integers
• Maximum flow problem:
  • Given a flow network, arrange the traffic so that use of the available capacity is as efficient as possible
  • Closely related to finding the value of the minimum cut
• Use of a residual graph helps to solve this problem:
• On page 342 you can find the algorithm augment(f,P) which is used to solve this problem.
• The results of augment(f,P) can then be used in the Max-Flow algorithm on page 344
• Algorithm can be implemented in O(mC) running time

• This subchapter continues analysis of the Ford-Fulkerson Algorithm discussed above in subchapter 7.1
• Use a cut to place upper bounds on max-flow
• Divide notes into two sets: set A and set B so that s is in set A and t is in set B
• We now make a cut between these two sets where the capacity of this cut is the sum of the capacities of all the edges out of A.
• Max flow therefore equals min cut.

• Any way of choosing an augmenting path increases the value of the flow.
• With a better path choice the algorithm can be significantly improved.
• The Scaling Max-Flow algorithm can be found from 353-354
• This algorithm can run in at most O(m^2log2C) time.

As this semester draws to a close I reflect with pride on everything I've accomplished in algorithms. This has been easily the hardest class I've taken in my time here at W&L but by increasing the amount of effort and time I spent on this class I was able to make a huge turn around from my initial average. This last reading assignment was probably the easiest for me as I've finally come around to being able to really understand the material the first time. Readability: 9/10