The following is a series of case studies on Network Flows. Network flows can be representative of many types of systems. Whether the network is used to transmit data from computer to computer or server to server, transfer goods across the county, or deliver liquid flows to the desired location, networks must be studied to find the most efficient path for the given media to travel across. Locating the most efficient path for media allows systems to run at maximum efficiency without overloading any particular portion of the network, which would slow or even inhibit delivery to the desired destination. Example 1
Example 1 introduces the scenario of Joe the plumber, and his piping network. Joe states that his system of connections can deliver a flow of 3 gpm from point s to point t through his series of connections. By studying his system on a capacitated s,t graph the flow tolerances can be mapped from point to point. Point s supplies 4 gpm to point a, point a then splits into two edges to points b and d which can flow 3 and 2 gpm respectively. Throughout the network there are differing capacities among the connections however, combined the edges always equal a flow of ≥3. This implies that the network will be able to deliver the necessary flow demands to t.
Example 2 introduces the need to block an inland city from the sea using mines. These mines are placed in channels of river R in varying amounts as needed by the area that needs to be covered. The task is to block access to sea from city s using the least amount of mines possible. City s can be isolated from the sea with a minimum of 7 mines. The mines should be placed in the following locations and amounts: 1 mine placed between point d and point g
2 mines placed between point e and point g
2 mines placed between point e and point h
1 mine placed between point f and point h
1 mine placed between point f and point l
This is shown in the graph R below. By placing mines in these locations and numbers city s would not be able to gain access to the sea without crossing a channel protected by mines.
Example three presents the scenario of a professor that is seeking to hire graders for assignments. These assignments span 30 different courses and 100 different sections. Each grader is asked their desired amount of sections they wish to review. An s,t graph can be created to represent this problem. Courses and sections are represented as vertices on a graph and the edges show the desired amount of sections a grader requested as well as the amount of sections the professor assigns each grader, shown as (g,p) on the edges of the graph. With each edge of the graph the amount of sections needing to be covered drops depending on the amount assigned by the professor starting at point s and ending at point t, the point at which all sections will be covered. The text provides a condensed version of how the graph would be comprised. Below you can see that before the edges meet at vertex t all of the courses and sections are covered.
Real World Situation
For my real world example I will use example 1 as a reference and compare it to my current work environment. Energy Plaza would like to begin using reclaim water for cooling tower make-up instead of potable water. In order to accomplish this, piping must be installed from the reclaim plant to the cooling tower basins. The basins can require up to a million gallons of water a day, which breaks down to just over 694 gallons per minute. Moving this large amount of water without putting high pressures on the system will require a pipe at least 24” in diameter. However, due to space limitations the single largest diameter pipe that can be placed is a 12” line and in some places only a 6” line. Using a capacitated s,t graph the correct system combination can be found.