Practice Questions: Routes & Networks
Try yourself: Direction: A significant amount of traffic flows from point S to point T in the one-way street network shown below. Q. If the government wants to ensure that all motorists travelling from S to T pay the same amount ( fuel costs and toll combined ) regardless of the route they choose and the street from B to C is under repairs ( and hence unusable ), then a feasible set of toll charged (in rupees) at junctions A, B, C and D respectively to achieve this goal is :
Points A, B, C and D are junctions in the network, and the arrows mark the direction of traffic flow.
The fuel cost in rupees for travelling along a street is indicated by the number adjacent to the arrow representing the street.
Motorists travelling from point S to point T would obviously take the route for which the total cost of travelling is the minimum.
If two or more routes have the same least travel cost, then motorists are indifferent between them.
Hence, the traffic gets evenly distributed among all the least cost routes The government can control the flow of traffic only by levying appropriate toll at each junction.
For example, if a motorist takes the route S - A - T (using junction A alone), then the total cost of travel would be Rs 14 (i.e. Rs 9 + Rs 5) plus the toll charged at junction A.
Try yourself: Direction: A significant amount of traffic flows from point S to point T in the one-way street network shown below. Q. If the government wants to ensure that all routes from S to T get the same amount of traffic, then a feasible set of toll charged (in rupees) at junctions A, B, C and D respectively to achieve this goal is:
Points A, B, C and D are junctions in the network, and the arrows mark the direction of traffic flow.
The fuel cost in rupees for travelling along a street is indicated by the number adjacent to the arrow representing the street.
Motorists travelling from point S to point T would obviously take the route for which the total cost of travelling is the minimum.
If two or more routes have the same least travel cost, then motorists are indifferent between them.
Hence, the traffic gets evenly distributed among all the least cost routes The government can control the flow of traffic only by levying appropriate toll at each junction.
For example, if a motorist takes the route S - A - T (using junction A alone), then the total cost of travel would be Rs 14 (i.e. Rs 9 + Rs 5) plus the toll charged at junction A.
Try yourself: Direction: A significant amount of traffic flows from point S to point T in the one-way street network shown below. Q. The government wants to devise a toll policy such that the total cost to the commuters per trip is minimized. The policy should also ensure that not more than 70 percent of the total traffic passes through junction B. The cost incurred by the commuter travelling from point S to point T under this policy will be:
Points A, B, C and D are junctions in the network, and the arrows mark the direction of traffic flow.
The fuel cost in rupees for travelling along a street is indicated by the number adjacent to the arrow representing the street.
Motorists travelling from point S to point T would obviously take the route for which the total cost of travelling is the minimum.
If two or more routes have the same least travel cost, then motorists are indifferent between them.
Hence, the traffic gets evenly distributed among all the least cost routes The government can control the flow of traffic only by levying appropriate toll at each junction.
For example, if a motorist takes the route S - A - T (using junction A alone), then the total cost of travel would be Rs 14 (i.e. Rs 9 + Rs 5) plus the toll charged at junction A.
Try yourself: Direction: A significant amount of traffic flows from point S to point T in the one-way street network shown below. Q. If the government wants to ensure that the traffic at S gets evenly distributed along streets from S to A, from S to B, and from S to D, then a feasible set of toll charged (in rupees) at junctions A, B, C, and D respectively to achieve this goal is:
Points A, B, C and D are junctions in the network, and the arrows mark the direction of traffic flow.
The fuel cost in rupees for travelling along a street is indicated by the number adjacent to the arrow representing the street.
Motorists travelling from point S to point T would obviously take the route for which the total cost of travelling is the minimum.
If two or more routes have the same least travel cost, then motorists are indifferent between them.
Hence, the traffic gets evenly distributed among all the least cost routes The government can control the flow of traffic only by levying appropriate toll at each junction.
For example, if a motorist takes the route S - A - T (using junction A alone), then the total cost of travel would be Rs 14 (i.e. Rs 9 + Rs 5) plus the toll charged at junction A.
Try yourself: Direction: A significant amount of traffic flows from point S to point T in the one-way street network shown below. Q. If the government wants to ensure that no traffic flows on the street from D to T, while equal amount of traffic flows through junctions A and C, then a feasible set of toll charged (in rupees) at junctions A, B, C and D respectively to achieve this goal is
Points A, B, C and D are junctions in the network, and the arrows mark the direction of traffic flow.
The fuel cost in rupees for travelling along a street is indicated by the number adjacent to the arrow representing the street.
Motorists travelling from point S to point T would obviously take the route for which the total cost of travelling is the minimum.
If two or more routes have the same least travel cost, then motorists are indifferent between them.
Hence, the traffic gets evenly distributed among all the least cost routes The government can control the flow of traffic only by levying appropriate toll at each junction.
For example, if a motorist takes the route S - A - T (using junction A alone), then the total cost of travel would be Rs 14 (i.e. Rs 9 + Rs 5) plus the toll charged at junction A.
Try yourself: In the adjoining figure, the lines represent one-way roads allowing travel only northwards or only westwards. Along how many distinct routes can a car reach point B from point A?
Try yourself: Eight cities A, B, C, D, E, F, G and H are connected with one-way roads R1, R2, R3, R4, R5 and R6 in the following manner:
R1 leads from A to C via B;
R2 leads from C to D and then via B to F;
R3 leads from D to A and then via E to H;
R4 leads from F to B via G;
R5 leads from G to D; and R6 leads from F to H.
The minimum number of road segments that have to be blocked in order to make all traffic form B to D impossible is
Try yourself: Direction: Natural gas once extracted from a source is purified for commercial use at natural gas plants. From gas plants it is pumped to various destinations through pipelines. There are pumping stations, at intermediate places to maintain recommended pressure in the pipelines. The pumping stations do not produce or process any natural gas. They pump out exactly the quantity they receive from plants or other pumping stations. The following figure depicts a network gas pipelines. The circles denote the locations of gas plants, pumping stations or cities with big demand for natural gas. One location can be only one of these three. The numbers on the arrows are the capacities (in appropriate units) of the pipeline that carry gas in the direction of the arrow. Currently the demand supply situation is such that the capacity utilization of the pipelines is very close to 100%. Q. What is the maximum quantity of natural gas S can receive?
Try yourself: Direction: Natural gas once extracted from a source is purified for commercial use at natural gas plants. From gas plants it is pumped to various destinations through pipelines. There are pumping stations, at intermediate places to maintain recommended pressure in the pipelines. The pumping stations do not produce or process any natural gas. They pump out exactly the quantity they receive from plants or other pumping stations. The following figure depicts a network gas pipelines. The circles denote the locations of gas plants, pumping stations or cities with big demand for natural gas. One location can be only one of these three. The numbers on the arrows are the capacities (in appropriate units) of the pipeline that carry gas in the direction of the arrow. Currently the demand supply situation is such that the capacity utilization of the pipelines is very close to 100%. Q. For which 2 cities it can be safely concluded that they have natural gas plants?
Try yourself: Direction: Natural gas once extracted from a source is purified for commercial use at natural gas plants. From gas plants it is pumped to various destinations through pipelines. There are pumping stations, at intermediate places to maintain recommended pressure in the pipelines. The pumping stations do not produce or process any natural gas. They pump out exactly the quantity they receive from plants or other pumping stations. The following figure depicts a network gas pipelines. The circles denote the locations of gas plants, pumping stations or cities with big demand for natural gas. One location can be only one of these three. The numbers on the arrows are the capacities (in appropriate units) of the pipeline that carry gas in the direction of the arrow. Currently the demand supply situation is such that the capacity utilization of the pipelines is very close to 100%. Q. What is the maximum quantity of natural gas than can be transported from M to R?
Try yourself: 4 cities are connected by a road network as shown in the figure. In how many ways can you start from any city and come back to it without travelling on the same road more than once?
Try yourself: What is the total number of ways to reach A to B in the network given?
Try yourself: Direction: The following sketch shows the pipelines carrying material from one location to another. Each location has a demand for material. The demand at Vaishali is 400, at Jyotishmati is 400, at Panchal is 700, and at Vidisha is 200. Each arrow indicates the direction of material flow through the pipeline. The flow from Vaishali to Jyotishmati is 300. The quantity of material flow is such that the demands at all these locations are exactly met. The capacity of each pipeline is 1,000. Q. The quantity moved from Avanti to Vidisha is
Try yourself: Direction: The following sketch shows the pipelines carrying material from one location to another. Each location has a demand for material. The demand at Vaishali is 400, at Jyotishmati is 400, at Panchal is 700, and at Vidisha is 200. Each arrow indicates the direction of material flow through the pipeline. The flow from Vaishali to Jyotishmati is 300. The quantity of material flow is such that the demands at all these locations are exactly met. The capacity of each pipeline is 1,000. Q. What is the free capacity available in the Avanti-Vidisha pipeline?
Try yourself: Direction: The following sketch shows the pipelines carrying material from one location to another. Each location has a demand for material. The demand at Vaishali is 400, at Jyotishmati is 400, at Panchal is 700, and at Vidisha is 200. Each arrow indicates the direction of material flow through the pipeline. The flow from Vaishali to Jyotishmati is 300. The quantity of material flow is such that the demands at all these locations are exactly met. The capacity of each pipeline is 1,000. Q. The free capacity available at the Avanti-Vaishali pipeline is
