Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2018:journals:holmesr:section_7.1 [2018/04/02 15:27] – created holmesr
+++ courses:cs211:winter2018:journals:holmesr:section_7.1 [2018/04/03 03:37] (current) – holmesr
@@ Line 1: / Line 1: @@
 ====== Section 7.1 The Maximum-Flow Problem and the Ford-Fulkerson Algorithm ======
+To begin our discussion of the Maximum-Flow problem and the Ford-Fulkerson algorithm (FF), we must first lay down some terminology. The network on which we will be measuring flow can be represented as a graph with nodes and edges. Each edge e has a non-negative capacity, which will be referred to as c<sub>e</sub>. Additionally, within the set of nodes there will be a single source node s and a single sink, or destination, node t. All other nodes are referred to as internal nodes. For simplicity, we will assume that no edges enter the source s and none leave the sink t. Additionally, all nodes have at least one incident edge and all capacities will be integers.
+There are also two properties that a flow must have to be reasonable for us to examine. The first of these conditions are the capacity conditions, which state that for each edge in our set of edges, the flow carried by the edge must be between zero and the capacity of the edge, inclusive. We also have the conservation conditions, which state that for each node in our set of nodes, the sum of the flows into the node must be equal to the sum of the flows out of the node.
+After some consideration, it is clear to see that a greedy solution or a dynamic programming solution will not provide our optimal solution. In fact, the key to solving this problem is a construct called the //residual graph//. We can name this G<sub>f</sub> and give it the same nodes as our graph G. Additionally, the capacity for an edge e, which we will call a //forward edge//, in G<sub>f</sub> will be the maximum capacity of the edge minus the flow that is currently being pushed through the edge. The //backwards edges// e' are the edges that tell us how many units of flow are being pushed through the edge at the current time, which we could 'undo' if needed.
+Now we are able to discuss "augmenting" a path. The augmenting algorithm returns a new flow f' in G that allows for more units to pass from the the source to the sink by identifying the bottleneck in the graph. We use this augmentation algorithm inside of the Max-Flow algorithm that repeatedly identifies a path in the residual graph and augments it until no path remains because at least on edge on each path has reached maximum capacity and thus no more units can pass from source to sink.
+Since our algorithm will only run on integer values for capacities and the capacity will increase by at least 1 during each iteration, then the loop driving the algorithm will run for at most the number of times which is the sum of the capacities of the edges coming out of the source node. Extending this, we can say that, since the residual graph which is the product of the augment function inside the loop, runs in O(m) time, the entire FF algorithm will run in O(mC) time.