[go: up one dir, main page]
Scribd
Upload
19 views2 pages

TD 4

Uploaded by

Ss Dzvirus
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
19 views2 pages

TD 4

Uploaded by

Ss Dzvirus
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

University Sétif 1 - Ferhat Abbas

Department of Computer Science


Academic Year 2024-2025
Course: Graph Theory (2nd Year Computer Science LMD) Instructor Prof. S. BOUAMAMA
Assignment 4
Exercise 1
Prove that this flow is not maximal. Increase it. How many maximum value flows are there?

Exercise 2
Apply the Ford-Fulkerson algorithm to the
following flow (at each iteration, provide an
augmenting path, but do not detail the
calculation of the path). At the end of the
algorithm's execution, demonstrate that the
flow is indeed maximal by using a theorem
covered in class.

Exercise 3

Three water towers A, B, and C supply four villages D, E, F, and G. On the


arcs of the following graph, the capacities of the existing pipelines are
indicated. On the water towers, the maximum flow capacities are noted
in parentheses. On the villages, the desired flow rates are noted in
parentheses. The objective is to determine the best possible supply.
Apply the Ford-Fulkerson algorithm. What is the maximum flow value? Is
it possible to meet the villages' desired flow rates? Subsequently, the
capacity of the arc (A, D) is increased by 5. Resume the execution of the
Ford-Fulkerson algorithm starting from the previously obtained flow

Exercise 4
Consider the transportation network below with the source vertex E and the sink vertex S. The weights on the arcs
represent the capacities of the channels.

a) Complete the following flow:

b) The previous flow is not maximal. Explain why.


c) Find the maximum flow by applying the Ford-Fulkerson algorithm.
1/2
Exercise 5
The server S is connected to machine T through a network with nodes A, B, C,
D. The connection capacities between the nodes (in Mbit/s) are given in the
adjacent table.
The user of machine T is downloading a very large file from server S. We aim to
find the routing that maximizes the throughput.
a) Represent this situation using a graph.
b) b) Which algorithmic problem from the course corresponds to this
routing problem? What is the name of the algorithm used to solve it?
c) Apply this algorithm, providing only the final step of its application. Deduce the maximum throughput.

Exercise 6: Determine a complete (non-maximal) flow for this graph.

Exercise 7:

Two water reservoirs supply 3 cities through a network of pipelines that also includes pumping stations. Each
reservoir has a limited capacity of 100,000 m³. The cities have expressed demands of 45,000 m³ for City 1, 40,000
m³ for City 2, and 80,000 m³ for City 3. The pipelines between the reservoirs and the cities have limited flow
capacities. For example, the pipeline connecting Reservoir 1 to City 1 has a maximum flow capacity of 30, while
the pipeline connecting Pumping Station 1 to City 2 has a maximum flow capacity of 50 (in thousands of m³). These
values are shown on the graph in parentheses along the pipelines. The problem is to determine whether it is
possible to meet the demands of the 3 cities through this network, and if so, how.

C1 C2
S1 S2

V1 V2 V3

a) Model this water distribution problem as a transportation network, then determine the maximum flow
for this graph as well as the corresponding minimum cut.

b) The water service for City V1, being well-informed, believes it is possible to increase the amount of water
supplied to it. If this is feasible, what would this new quantity be? Justify your answer.

c) Seeing this, City V2 also requests an increase in its supply, following V1's successful increase. Is it possible
to do so without altering what has been distributed to the other two cities? Justify your answer.

d) Meanwhile, the officials of City V3, who would also like to see their supply increased, propose to fund work
to increase the capacity of a pipeline supplying their city. Which pipeline is it, and what would its new
capacity be?

2/2

You might also like