This is an old revision of the document!
Table of Contents
Chapter 7: Network Flow
Section 7.1: The Maximum-Flow Problem and the Ford-Fulkerson Algorithm
Graphs are used to model transportation networks, which are networks whose edges carry traffic and whose nodes act as “switches” to pass the traffic. Each edge has a capacity, a specified amount that they can carry, and there are source and sink nodes which direct the flow of traffic. A flow network is a graph with non-negative edges, that has a single source node s and a single sink node t. Furthermore, we assume that there are no edges entering the source and no edges leaving the sink, each node has an edge and all capacities are integers. Flow through the graph is conserved. That is, if a flow of 10 goes into a node, then 10 leaves the node. The problem generally associated with these graphs are finding the maximum flow across the graph and the minimum cut of the graph. In order to find the maximum flow, we first find the residual graph, which is the graph found be traversing the augmenting paths from s-t, and determining the maximum flow through each path. We can find the “leftover” flow after each of these traversals. This algorithm is outlined on pages 342 and 344 of the text. The section then details how we are able to determine that the Ford-Fulkerson algorithm runs in O(mC) time with m being the number of edges in the graph and C denoting the sum of the flow. This section is a little confusing. It was tough running through the examples in class and the section is a little long-winded. I think writing out another example would probably help me a lot. I would give this section a 8/10 because event though it is a little hard to understand i is an important type of problem and one with interesting uses.
Section 7.2: Maximum Flows and Minimum Cuts in a Network
This section continues to look at the Ford-Fulkerson algorithm and focuses on the idea of cuts. The section strives to prove that F-F returns the maximum possible flow. A cut separates the graph into two sections and limits the flow that can come in and out of a section. Then, we know that after making these minimum cuts, we can tell that the value of every flow is less than or equal to the capacity of every cut.
