Max Flow

...

A network flow is a directed graph where each edge has a capacity representing the maximum amount of flow that can be sent through it. It consists of a source node, a sink node, and intermediate nodes connected by edges with capacities. The goal is to find the maximum amount of flow that can be sent from the source to the sink while respecting the capacity constraints.

The Ford-Fulkerson algorithm is an iterative algorithm that finds the maximum flow in a network. It starts with an initial flow of zero and repeatedly augments the flow along the augmenting paths until no more augmenting paths exist. An augmenting path is a path from the source to the sink where each edge has residual capacity (capacity minus current flow) greater than zero.

The algorithm finds an augmenting path using a graph traversal technique such as depth-first search (DFS) or breadth-first search (BFS). Once an augmenting path is found, the algorithm determines the maximum amount of flow that can be sent along the path and updates the flow values accordingly.

function FordFulkerson(graph, source, sink):
    residualGraph := createResidualGraph(graph)
    flow := 0

    while there is an augmenting path in residualGraph:
        augmentingPath := findAugmentingPath(residualGraph, source, sink)
        bottleneck := findBottleneckCapacity(augmentingPath)
        updateFlow(residualGraph, augmentingPath, bottleneck)
        flow := flow + bottleneck

    return flow
Copy

The createResidualGraph function creates a residual graph from the original graph, where each edge's capacity is reduced by the flow already sent along that edge. The findAugmentingPath function finds an augmenting path in the residual graph using a graph traversal technique. The findBottleneckCapacity function determines the maximum amount of flow that can be sent along the augmenting path. The updateFlow function updates the flow values in the residual graph based on the augmenting path and the bottleneck capacity.

The max flow in a network represents the maximum amount of flow that can be sent from the source to the sink. It is equal to the sum of the flow values across all edges leaving the source.

A min cut in a network represents the minimum capacity needed to disconnect the source from the sink. It consists of a partition of the nodes into two sets, S and T, such that the source is in S and the sink is in T. The capacity of the min cut is the sum of the capacities of the edges that cross the partition from S to T.

The max flow in a network is equal to the capacity of any min cut in the same network. This property is known as the max-flow min-cut theorem.

The time complexity of the Ford-Fulkerson algorithm depends on the method used to find augmenting paths. If a simple DFS or BFS is used, the worst-case time complexity can be , where is the number of edges in the graph and maxFlow is the value of the maximum flow. However, this time complexity can be improved by using more efficient algorithms to find augmenting paths, such as the Edmonds-Karp algorithm, which uses BFS and has a time complexity of , where V is the number of vertices and is the number of edges.

It's important to note that the Ford-Fulkerson algorithm may not terminate if the capacities are real numbers instead of integers. To ensure termination, an additional step called capacity scaling or epsilon-scaling can be applied, where the capacities are rounded to multiples of a small value epsilon.

In summary, the Ford-Fulkerson algorithm is an iterative algorithm that finds the maximum flow in a network. It can be used to solve a variety of real-world problems, such as network optimization, transportation planning, and resource allocation. The max flow corresponds to the maximum amount of flow that can be sent from the source to the sink, while the min cut represents the minimum capacity needed to disconnect the source from the sink.