Problem: Telephone calls from New York to Los Angeles are transported as follows. The call is sent first to either Chicago or Memphis, then routed through either Denver or Dallas, then finally sent to Los Angeles. The number of phone lines joining each pair of cities is shown below.
(a) Formulate an LP that can be used to determine the maximum number of calls that can be sent from New York to Los Angeles at any given time.
(b) Use the Ford-Ftdkerson algorithm to determine the maximum number of calls that can be sent from New York to Los Angeles at any given time.
(c) For your final graph, draw the associated residual graph.
(d) Find the cut so that "max-flow=min-cut".
|
Cities
|
No. Lines
|
|
NY-Chicago
|
500
|
|
NY-Memphis
|
400
|
|
Chicago-Denver
|
300
|
|
Chicago-Dallas
|
250
|
|
Memphis-Denver
|
200
|
|
Memphis-Dallas
|
150
|
|
Denver-LA
|
400
|
|
Dallas-LA
|
350
|