Differences

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

--- courses:cs211:winter2018:journals:mccaffreyk:7 [2018/04/03 01:34] – mccaffreyk
+++ courses:cs211:winter2018:journals:mccaffreyk:7 [2018/04/03 01:37] (current) – mccaffreyk
@@ Line 17: / Line 17: @@
 from a given edge cannot exceed the amount of flow into it(conservation condition). The maximum flow problem involves
 finding a flow of maximum possible value in some flow network. To solve this, we will focus on how some node's capacities put
-bounds on flow. A "cut" of a flow network is a set of edges which cannot be directly connected across nodes that some quantity of flow follows between nodes from source
+bounds on flow. A "cut" of a flow network is a set of edges which cannot be directly connected all across two distinct groups of nodes that some quantity of flow follows between nodes from source to sink. Unfortunately, Dynamic Programming does not work here. It is important to note that we can divide flow distribution along multiple cuts in our network. For this reason, we cannot appear to use a greedy algorithm either. A graph representation made after the flow has been distributed is called a residual graph. Capacity values are placed by each edge(now represent actual expected flow values) and each node can have both backward and forward edges. A backward edge is made when flow is diverted from the current path back to go on a different cut. Flow can only be diverted when the current node's capacity is exceeded. Clearly, residual graphs will often have more edges than non residual graphs. New capacities of each edge are called residual capacities. Bottleneck capacity is the lowest capacity of any node in some path. We build a function augment to manage the flows of various edges in residual graphs. For each edge in some cut, if the edge is forward, its flow is increased by the bottleneck and if it is backward its flow is decreased by the bottleneck. Finally, we can use a simple algorithm to compute the residual graph with max flow. All that this algorithm does is apply the augment function to some s-t path in the graph while an s-t path exists. We call this the Ford-Fulkerson Algorithm. This section was a little complicated at times but I found the material interesting and intuitive. This gets an 8/10.
-to sink. Unfortunately, Dynamic Programming does not work here. It is important to note that we can divide flow distribution along
-multiple cuts in our network. For this reason, we cannot appear to use a greedy algorithm either. A graph representation made
-after the flow has been distributed is called a residual graph. Capacity values are placed by each edge(now represent actual expected flow values) and each node can have both backward and forward edges. A backward edge is made when flow is diverted from the current path back to go on a different cut. Flow can only be diverted when the current node's capacity is exceeded. Clearly, residual graphs will often have more edges than non residual graphs. New capacities of each edge are called residual capacities. Bottleneck capacity is the lowest capacity of any node in some path. We build a function augment to manage the flows of various edges in residual graphs. For each edge in some cut, if the edge is forward, its flow is increased by the bottleneck and if it is backward its flow is decreased by the bottleneck. Finally, we can use a simple algorithm to compute the residual graph with max flow. All that this algorithm does is apply the augment function to some s-t path in the graph while an s-t path exists. We call this the Ford-Fulkerson Algorithm. This section was a little complicated at times but I found the material interesting and intuitive. This gets an 8/10.
 === Section 7.2: Maximum Flows and Minimum Cuts in a Network ===