Lecture 19 CEE 270
Popular in System Analysis and Economic Civil Engineering
Popular in Civil and Environmental Engineering
One Day of Notes
verified elite notetaker
This 4 page Class Notes was uploaded by Nathaniel Bautz on Friday April 3, 2015. The Class Notes belongs to CEE 270 at University of Massachusetts taught by Bernd Schliemann in Spring2015. Since its upload, it has received 38 views. For similar materials see System Analysis and Economic Civil Engineering in Civil and Environmental Engineering at University of Massachusetts.
Reviews for Lecture 19
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 04/03/15
CEE 270 LECTURE 19 GRAPHS AND NETWORKS O 90 O 90 O 9 Graphs amp Networks gt Shortest path problem gt Maximum ow problem Network Examples Physical and visible transportation networks Physical and visible integrated circuits Physical and invisible telecommunication networks Virtual social networks Virtual scheduling of tasks for a construction project Network Terminology Node vertex point in the network Supply source origin node ow out gt ow in Demand sink destination node ow in gt ow out Transshipment intermediate node ow in ow out Arc link connecting nodes Directed ow only on one direction indicated by an arrowhead Undirected ow on both directions two directed arcs Capacity maximum amount of ow on the arc Path a series of connecting arcs Shortest Path Applications gt Minimize distance traveled gt Minimize total cost of sequence of activities gt Minimize total time of a sequence of activities Shortest Path Problem gt How does Google Yahoo MSN MapQuest or your GPS navigation system calculate the routes for me when I input the start and ending addresses on a transportation network gt A component of more complicated models e g traffic simulation models that predict when and where traffic congestion will happen and how severe where each vehicle is assumed to take the shortest pat from its origin to destination Maximum Flow Problem gt All ow through a directed and connected network originates as the source and terminates at the sink gt All other nodes are transshipment nodes gt Flow is indicated by an arc s arrowhead gt Objective is to maximize total amount of ow from the source to the sink Maximum Flow Applications gt Maximize ow of vehicles through a transportation network gt Maximize ow of water through an aqueduct system gt Maximize ow of oil through a system of pipelines gt Maximize ow of supplies good through a supply or distribution network Augmenting Path Algorithm VVVVV VVVVVVVVV gt 1 Sketch the residual network gt 2 Optimality test identify an augmenting path where each are has a strictly positive residual capacity gt 3 Identify the minimum of the residual capacities c on this path then increase the ow on this path by c gt 4 Decrease the residual capacity by c increase the residual capacity in the opposite direction by c gt 5 Return to step 2 393 Example gt Consider the maximum ow problem shown below where the source is node A the sink is node F and the arc capacities are the numbers shown next to these directed arcs Determine the maximum ow using the augmenting path algorithm u a L
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'