10. Network Flows

In the bandwidth allocation problem, we use one variable per path in order to encode a network flow problem as a linear program and we argued that does not an efficient way to do it. So, let us look at a mode direct way to represent network flows in terms of linear programs.

This chunk introduces the concept of network flows and explains how bandwidth allocation is formulated using linear programming. It also mentions that there is a more direct way to represent these flows, signaling that the coming sections will explore better methods of handling network flow problems.

Imagine you are managing traffic in a city. Instead of tracking every individual car on every road, it's more efficient to track overall traffic volume on major highways. Just like that, representing network flows as linear programs simplifies the problem.

Suppose we have an oil network which is shown as given in this directed graph. So, we have a source vertex s and we have a target or a sink vertex t and our aim is to shift as much oil as we can from s to t given the pipes that we are given.

In this example, we visualize a directed graph representing an oil pipeline system, where 's' is the source of the oil and 't' is the sink or destination. The goal is to maximize the flow of oil from 's' to 't' through the network, analogous to finding the best route for oil transportation.

Think of a water system where you need to get water from a reservoir to a park using pipes. You'll want to use the pipes that can carry the most water efficiently, just like finding the best pipelines in the oil network.

One property of a flow is that it is must flow, so I cannot keep any quantity at any intermediate node. So, anything that enters b must leave b, anything that enters d must leave d.

This principle explains that in a network flow, any oil that enters an intermediate node must leave it; there is no storage allowed. This is a conservation law in flows ensuring that every node maintains a balance, promoting efficient flow throughout the network.

Imagine traffic at a junction: cars that arrive must continue through and cannot just stop waiting. If they did, it would create a backlog and slow down the whole traffic system; similar principles apply to network flows.

If we try to do this, then for instance this green quantity represents one possible flow, I send two units from s to a 1 from s to b 4 from s to c and you can check that these are interact with in the capacity there could for sent a 3, 3 and 4 and I have set 2, 1 and 4.

This part details an example flow through the network, showing specific values transferred between nodes. It emphasizes checking that the assigned flow does not exceed the specified capacities of each pathway in the graph.

Think of a delivery system where you are dispatching packages. If your truck can carry only a limited weight, you need to ensure you do not exceed this limit while distributing packages to various destinations.

The problem just to face it formally is that we have given a special type of graph, it is a directed graph and it has two special nodes, a source and a sink.

This chunk outlines the formal structure of the flow problem, describing the graph as directed along with two crucial nodes: the source (where the oil starts from) and the sink (where the oil is intended to go). The statement clarifies that maximizing the flow through this network is the central challenge.

Consider a delivery service where packages must flow from a central warehouse (source) to customers (sink). The challenge lies in ensuring that the packages travel through the most efficient routes without exceeding the limits of any vehicle's load capacity.

We can set up a linear program, what we associate do is we associate and said one variable for each edge. So, for instances for the edge s a we have f s a and then for the edge b d for example, we have f b d and then for c e, we have f c e.

In this section, the focus is on representing the network's flow mathematically by assigning a variable to each edge in the graph. These variables represent the flow along those edges and will be constrained by the edge capacities defined in the network.

Imagine each delivery truck on a route as a variable representing how many packages can be sent along that route while being limited by truck capacity—this is like assigning variables to each edge for flow calculation.

Each variable is constrained by the capacity of the corresponding edge. So, f b a, so b a is now this edge, it has a capacity of 10. So, whatever flow I finally arrive at from b to a must be less than 10.

This chunk describes the constraints applied to the variables in the linear program: each flow variable cannot exceed the capacity defined for its corresponding edge. It highlights the importance of adhering to capacity limits to maintain realistic flow calculations.

Think of setting capacity limits on a series of water pipes. The water flow from one pipe to another cannot exceed its maximum capacity to prevent bursting—similar to the constraints in our flow model.

The objective is to maximize what happens on these three edges f s a plus f s b plus f s c, this is our objective function.

This section explains the goal of the linear program: to maximize the total flow output from the source node 's' through its edges. The objective function serves as a mathematical representation of this goal, guiding the optimization process.

Consider planning to maximize the number of goods delivered from a distribution center. The objective function helps you decide the most efficient routes for delivery trucks to serve the most customers.

This is an algorithm called the Ford-Fulkerson algorithm which actually tries to directly solve a network flow problem by gradually building up an optimum flow.

The Ford-Fulkerson algorithm aims to find the maximum flow in a network by starting with zero flow and progressively increasing it. It systematically explores paths in the network and augments flow until no more flow can be added.

Think of a water reservoir gradually filling up through pipes. The Ford-Fulkerson method is similar to gradually letting water flow through various pathways until no more can be added, thereby maximizing the reservoir's capacity.

So, this is what we call the residual graph, so in the residual graph what we will do is we will actually take the flow that we just contracted and then we will change the capacities.

In a residual graph, after establishing a flow, the capacities of the original edges are updated to reflect the flow. Forward edges lose capacity based on the flow, and new backward edges are created to allow for rearranging flows if necessary.

Imagine changing the parameters of a delivery system after each route is used. For example, if a particular route gets fully utilized, the capacity on that route is adjusted, and alternatives are created to redirect deliveries if needed.

So, the solution is to save that even if you are taken back path, one of the thinks we can do is reverse the decision we made earlier.

This section discusses how the Ford-Fulkerson algorithm can adjust flows by using backward edges established in the residual graph. If a chosen path is not optimal, the algorithm can decrease flow in that path and explore alternative routes.

Think of revising a planned delivery route. If traffic blocks your way, rather than sticking to the original plan, you can redirect deliveries through an alternate path, similar to adjusting flow in the Ford-Fulkerson method.

So, it is pretty clear that the maximum flow cannot exceed the minimum cut because it has the cross this cut.

This critical theorem establishes the relationship between maximum flow and minimum cut in a network. It asserts that the maximum flow possible from the source to the sink cannot exceed the minimum capacity that would separate them—this is a fundamental concept in network flow problems.

Imagine trying to siphon water from one tank to another using a narrow pipe. No matter how hard you try, the water flow cannot exceed the pipe's diameter—just as the flow from the source cannot exceed the limitations set by the minimum cut.

--