Today we're gonna finish off our discussion of graph processing by looking at Max Flow algorithms. This is another general problem solving model for which we have efficient algorithms, so where at the difference between having a good algorithm and not having one makes a difference between being able to solve all kinds of practical problems and not being able to address them at all. As an introduction we'll take a look at what the problem is and some of it's implications. So first we'll start with what's called the mincut problem. So this is a. takes as input a Edge Weighted Digraph and now we are going to assume that the edge weights are positive, and we referred to the weight as a capacity and you will see why in just a minute. And also we specify a source and a target vertex. This is not an absolute requirement but it will simplify our discussion for the lecture. So we have an edge weighted digraph where the source and target vertex and every edge has a positive capacity. Now a cut, an ST cut, S and T are specified remember? Is the partition of the vertices into two disjoint sets, Where s is one set and t is in the other. And we'll indicate a cut as we've done before by coloring the vertices in one set. So in this case, the cut consists of s in one set, and all the other vertices in the other. So s is in, one set and t is in the other, that's an st cut. Now given a cut. We talk about the capacity of the cut. And that's gonna be the sum of the capacity of the edges that go from the set containing s to the set containing b If you have edge going the other way we don't count it. So in this case, the, this cut with the vertex containing just s in one set has capacity 30 ten + five +fifteen. Here's another cut this one contains three vertices, S and two at the bottom there. Again it's an ST cut, cause s is colored t is not. And then we can look at the capacity of that cut. Again, we count the vertic, the edges that go from to the cut containing s to the cup containing b, B. In this case, is ten + eight + sixteen That's the edges going out is 34. That's the capacity. We don't count the edges that go in from the sec containing t to the sec containing s Capacity of the cut is the sum of the capacities of the edges going out. Here's the third example, and this one's got capacity 28. Now the three cuts that we've seen you notice have different capacities: 30, 34, 28. So the mincut problem, clearly, is to find the minimum capacity cut. Find a way to divide the vertices into two sets, one containing s and the other containing t with the property that the capacity of the cut is minimized. That's the mincut problem. And this an important practical problem with all kinds of applications. Just for fun we take an application from the 1950's. This is around time these sorts of problems were first articulated. So this is, has to do with the cold war and these are rail networks that connects the Soviet Union with countries in Eastern Europe. This map actually wasn't declassified until 1999. But it shows a graph with the vertices, directed graph with vertices corresponding to cities and edges corresponding to rail lines. And if you look closely, you can see that, Each of the edges is labeled with a capacity. The goal. So the goal of the free world say if there was gonna be a real war was to find a way to cut the Soviet Union from Eastern Europe. And they wanna do that. You can assume maybe the cost of cutting a rail line is proportional to its capacity. So they wanna find the cheapest way to cut off supplies. From Soviet Union, Eastern Europe. That's an example of a min cut application. We'll look at some other applications later on. Well, look at a future, well maybe this is a cut for today's world. So now you have a huge graph, maybe a social network. And maybe there's a government and power in some area of the world, and the goal of that government would be to cut off the communication to some set of people. And again, they want to do that in the cheapest way possible. Find the minimum way to cut off communication. And certainly, people are writing programs to process graphs like this with such goals in mind nowadays. These are huge, huge graphs and certainly are going to need efficient algorithms. In the 1950s, the graphs were pretty huge by 1950s standards. And it wanted efficient algorithms then too, for sure, 'cause computers were slower. Alright, that's one problem. So let's talk about a different problem, called the max-flow problem. And it's the same setup inputs and edge weighted digraphs, source for text s, and a target for text t, every edge has a positive capacity. And now what we're gonna talk about is what's called a flow. It's a assignment of values to the edges. So, we have the capacities, and we're gonna assign another integer to each edge, called its flow. And then flow has to satisfy two properties. The first one is that the flows have to be positive and they can't be greater than the capacity. You can think of the, edges again as a rail line containing some commodity or a pipe containing some fluid. So the flow is how much stuff can you put through that edge? You can more than zero but you can't put more than capacity. The other thing about a flow is that there has to be local equilibrium at the vertices. And again that's a natural constraint to think about stuff flowing in on rail lines to a city and you want, you want to keep things going the local elibrium constrains says that the stuff coming in has to equal the stuff going out at every vertex except for the source everything leaves from the source. And the target, everything goes to the target. And those have the source has no inflow and the target has no outflow. So what you want is the inflow at a vertex, say, in this example inflow at v, there's five coming in on this edge and five coming in on that edge. So that's a total of ten coming in and there has to be just ten going out. So that's, happens on this one edge. And that has to be satisfied at every vertex. So this flow's got five coming in there and five going out. Ten going in there and five going out each way and so forth. Every vertex except S and T. And we can even make it true for S and T by drawing an edge from T all the way back to S. So that's the max flow problem, well, the, that's the definition of a flow, and of course the max flow problem is to assign a value to the flow. Well that's how much stuff you can get to the source. To the target. Or equivalently, how much stuff can you push out of the source. And so the value is how much can you get into the target. There's lots of different ways to assign flows to the network to satisfy the capacity equilibri-, equilibrium constraint. Which one maximizes the flow, that's the maximum ST flow problem, or the max flow problem. So that's two different problems. The min cut problem. How do we cut the graph efficiently, with a minimal amount of work. And the max flow problem. What's the maximum amount of stuff that we can get through the graph? And again, if we look at, the 1950's graph. What the Soviet Union wanted to do was find a way to maximize the flow of supplies to Eastern Europe. Now that was their goal in this case, and again you can see in this whole map, this is a assignment of a flow to this network that does maximize the flow for this network, So they figured it out. And nowadays in the huge graph, maybe the free world wants to do the opposite. They want to maximize the flow of information to some specified set of people. How do we get the most information in there and is there another way to think of it? And again, these are huge graphs and we want efficient algorithms. So that's two problems both have an input weighted digraph with a specified source and target and then cut problem is to find them in capacity cut and max flow problem is find a maximum value flow. It's a lot of computation to do for example in the max flow problem we have to assign a value to each edge. So that's more work than just finding a path as we've done in other graph processing problems. So it's more complicated and the amazing thing about these two problems is that they're actually pretty much the same problem. They're what we call dual. If you solve one you're able to solve the other. So that's an introduction to max flow