CODEWITHSUNDEEP
algorithmgraphford-fulkerson
globus1988
globus1988

Reputation: 75

Find the maximum flow in any network by a given algorithm

can you help me with the following problem?:

Suppose we have an algorithm to solve the problem of maximum flow in a flow network in which each node's outdegree is at most 2. I need to show how to use this algorithm to solve the problem of maximum flow in any network.

If this is a repetition then kindly redirect me to relevant answers.

Thank you all

Upvotes: 1

Views: 330

Answers (1)

danbanica
danbanica

Reputation: 3038

It is indeed possible to transform the graph in such a way that the out-degree of each node is at most 2, and the maximum flow in the transformed graph is equal to the maximum flow in the initial graph.

One such transformation is described below. Assume we have a node whose out degree is larger than 2. Then we can add as many intermediary nodes as the out-degree of this node and connect them in the way depicted in the following image.

![transformation

The infinite capacity edges ensure that we can send the same flow as initially from A to any of its successors. The edges from X nodes to B nodes ensure that we can not send a flow larger than it was initially possible.

By repeating this transformation for each node with out-degree larger than 2 we obtain a graph where each node has out-degree at most 2, and whose maximum flow is equal to the maximum flow of the initial graph.

Upvotes: 1

Related Questions