Question

Assume that in addition to having capacities for edges we have capacities for vertices, meaning that the incoming flow to a vertex cannot be more that its capacity. Describe an efficient algorithm to solve the max-flow problem in such a network.

Answer 1

Hey! here is my updated answer please check it and change your.... rating please.....i give my best for this answer please change......thanks for the comment.

The Maximum Flow Problem with vertex capacity :-

• the maximum flow problem is the one in which, in addition to having a capacity c(u, v) for every edge, we also have a capacity c(u) for every vertex, and a flow f(·, ·) is feasible only if, in addition to the conservation constraints and the edge capacity constraints, it also satisfies the vertex capacity constraints.
• It is easy to see that the problem can be reduced to the standard maximum flow problem, by splitting every vertex v into two vertices vin and vout, adding one edge (vin, vout) of capacity c(v), and then converting every edge (u, v) to an edge (u, vin) and every edge (v, w) to an edge (vout, w). It is easy to show that solving the (standard) maximum flow problem on the new network is equivalent to solving the maximum flow with vertex capacity constraints in the original network.

transforming the initial graph into a graph which has no capacity constraint on nodes by adding self loops (adding self-loops to each node and finding paths which includes this self-loops for each node on the path) or adding virtual nodes and edges whose weights supersede the initial node-capacity constraints)

There's a simple reduction from the max-flow problem with node capacities to a regular max-flow problem:

• For every vertex v in your graph, replace it with two vertices v_in and v_out. Every incoming edge to v should point to v_in and every outgoing edge from v should point from v_out. Then create one additional edge from v_in to v_out with capacity c_v, the capacity of vertex v.

So We run Ford-Fulkerson Algorithm on the transformed graph.

Ford-Fulkerson Algorithm for Maximum Flow Problem

• Ford-Fulkerson algorithm is a greedy approach for calculating the maximum possible flow in a network or a graph.
• A term, flow network, is used to describe a network of vertices and edges with a source (S) and a sink (T). Each vertex, except S and T, can receive and send an equal amount of stuff through it. S can only send and T can only receive stuff.

• it is an efficient algorithm to solve the max-flow problem in such a network.
• The Ford-Fulkerson algorithm solves the problem of finding a maximum flow for a given network.
• The Ford-Fulkerson method is iterative. We start with f(u, v) = 0 for all u,v V, giving an initial flow of value 0. At each iteration, we increase the flow value by finding an "augmenting path," which we can think of simply as a path from the source s to the sink t along which we can push more flow, and then augmenting the flow along this path. We repeat this process until no augmenting path can be found.

Given a graph which represents a flow network where every edge has a capacity. Also given two vertices source ‘s’ and sink ‘t’ in the graph, find the maximum possible flow from s to t with following constraints:
a) Flow on an edge doesn’t exceed the given capacity of the edge.

b) Incoming flow is equal to outgoing flow for every vertex except s and t.

For example, consider the following graph .

The maximum possible flow in the above graph is 23.

Ford-Fulkerson Algorithm
The following is simple idea of Ford-Fulkerson algorithm:
1) Start with initial flow as 0.
2) While there is an augmenting path from source to sink.
Add this path-flow to flow.
3) Return flow.

Time Complexity: Time complexity of the above algorithm is O(max_flow * E). We run a loop while there is an augmenting path. In the worst case, we may add 1 unit flow in every iteration. Therefore the time complexity becomes O(max_flow * E).

Terminologies Used

• Augmenting Path :- It is the path available in a flow network.
• Residual Graph:- It represents the flow network that has additional possible flow.
• Residual Capacity:- It is the capacity of the edge after subtracting the flow from the maximum capacity.

• To implement the above Ford-Fulkerson Algorithm ,first to define the concept of Residual Graph which is needed for understanding the implementation.
• Residual Graph of a flow network is a graph which indicates additional possible flow. If there is a path from source to sink in residual graph, then it is possible to add flow. Every edge of a residual graph has a value called residual capacity which is equal to original capacity of the edge minus current flow. Residual capacity is basically the current capacity of the edge.

EXAMPLE:_

thanksssss.................