Contenus

Toggle## Corrected exercises on maximum flow problems

This page contains various corrected exercises on max flow problems. These problems mainly use the algorithm Ford-Fulkerson and the min-cut solution.

## Exercise 1

Using the Ford-Fulkerson method, calculate a maximum throughput in the following network:

## Exercise 2

The figure below shows a stream network on which an st stream is displayed. The capacity of each edge appears as a label next to the edge, and the numbers in the boxes indicate the amount of flow sent on each edge. (Edges without boxed numbers have no flux sent over them.) What is the value of this flux? Is this a maximum flow st in this graph? If not, find a maximum bitrate st. Find a minimal cut. (Specify which vertices belong to the sets in the section.)

The value of this rate is 17. No, it is not a maximum rate. A maximum throughput can be found by looking at the residual network. In this case, from the given flux, we can get maximum flux with a single augmentation path, szyxwt. The maximum flow rate therefore has the value 19.

A minimum cut can be found by using the residual network for the final maximum flow. From s, find all vertices reachable from s in the residual network. This forms a set in the minimal cut. The other vertices form the other defined part of the cut. So, a minimal cut in this case are the two sets {s; z} and {x; w; y; t}.

You can check that the capacity of this cut (i.e. the total capacity of the edges from {s;z} to {x;w;y;t}, consisting of the directed edges (s;w); ( s; x); (z; y); and (z; t) is 19, as guaranteed by the max flow/min cut theorem.

## Exercise 3

Describe a algorithm efficient which finds a new maximum flux if the capacity of a particular edge increases by one unit. Describe an efficient algorithm that finds a new maximum flux if the capacity of a particular edge decreases by one unit.

Suppose the edge of u to v increases its capacity by one. From the previous maximum flux F, it suffices to make a new iteration of the Ford-Fulkerson algorithm with the graph modified: The residual flux graph increases the capacity of the edge (u; v) by one. Do a graph search to see if there is a path in the residual flow graph along which the flow can increase. If there is, there must be a stream of size one (because all streams are integers). If there is no flow in the residual flow graph, F is always the maximum flow.

Suppose the edge of u to v decreases its capacity by one. If the previous maximum rate F did not use the full capacity of (u;v), such a change does not matter at all. Otherwise, we update the feed as follows:

Since the flux entering u is greater by one unit than the flux leaving it and the flux entering v is less than the flux leaving it by one unit, it is impossible to transfer a unit flux from u to v . So, search the residual flow graph for a path from u to v along which the flow can increase by one. If there is such a path, we update F with the stream.

If there is no such path, we must reduce the flow from s to u and from v to t by one unit. To do this, we find a path from u to s in the residual flux graph along which the flux can increase by one and a path from t to v along which the flux can increase by one. (There must be such paths, because we had a stream from s to t via (u;v).) Then update F with these two streams.

## Exercise 4

Considering the following flow, how to increase the flow?

The minimum cut is made, so we know the bottlenecks on the chart. The sum of the capacities at the source is 22, and 24 at the sink, we deduce that we cannot have more than 22. We must therefore find a path from to to increase the flow rate by 2, and a path from to to increase the flux by 1. The previous exercise gives an algorithm an idea to achieve this goal. We can increase capabilities on minimal cutting edges.

## Exercise 5

In the bipartite graph opposite, vertices T1…T6 represent workers and vertices E1…E6 represent jobs. A benefit connects a worker to a job if the worker has the necessary qualifications for that job. How to allocate jobs to workers to minimize the number of unemployed?

Assigning a job to a person is like “selecting” an edge. Ti are connected to a fictitious source with a capacity of 1 (same for the Ei to a fictitious sink). The edges of the bipartite graph have a capacity of 1. It then searches for a maximum flow.

## Exercise 6

Suppose you are organizing a conference where researchers present papers they have written. Researchers wishing to present a paper send a communication to the conference organizers. Conference organizers have access to a committee of reviewers who are each willing to read papers each.

Each article submission is reviewed by as many reviewers as possible. Additionally, each submission has a particular topic and each reviewer has a specialization for a set of topics, so articles on a given topic are only reviewed by reviewers who are experts in that topic.

Conference organizers must decide which reviewers will review each paper (or, equivalently, which papers will be reviewed by which reviewers). Explain how they could use a stream network to solve this problem.

There is an A set of articles and a B set of reviewers. Add a directed edge (α,β) to the graph if an article α in A can be reviewed by a reviewer β in B, i.e. the article is about a topic in which the reviewer is an expert. Set the capacity of this edge to be 1. Add a vertex s (source) and a vertex t (terminal). For each α in A, add an edge (s, α) of capacitance mA. For each β of B, add an edge (β , t) of capacity mB. Run Ford-Fulkerson to get the maximum flow rate and calculate the corresponding cut (A,B). This gives the set of edges that correspond to the assignment of articles to reviewers.

## Exercise 7

Consider a set of machines and tasks. A Li machine can be used at most ai time. A task Cj can be used at most bj time. The supply and demand chart represents machines and tasks, and the ability to perform a task on a given (empty) machine.

Create a bipartite graph, then make a fictitious source (fictitious sink) with arc capacities ai (and bj). Then solve the flow problem.