Hello everybody. Welcome back to our network flows unit. Today we're going to be talking a little bit about sort of formal definitions and sort of getting a concrete definition of our problem and then some examples of sort of what sorts of problems fall into this category. So, remember last time we discussed the disaster management problem. Today what we're going to do is we're going to have a sort of formal framework for talking about this problem and some similar problems. So to begin with, we're going to want to define what a network is. A network should be thought of like this network of roads that we saw in this previous example. So a network is a directed graph G representing all the roads, but with some additional information. Each edge E is assigned a positive real number called its capacity. This is how much traffic can be handled by that road. Additionally one or more vertexes labeled as a source, this is the city, this is the place where the traffic is coming from. And then one or more vertex is labelled a sink, which is sort of the edges of the graph where everything is going to. So flow goes from sources to sinks along these edges that each have a capacity. So with the example from last time, we have this network of roads, we can turn it into a graph where the city is a node, each of the intersection gives us another vertex, and then we have some extra vertices sort of at the ends where the cars escape to. The city itself is the source of our flow. The four exits give us sinks, labeled T here. And each of the edges has a capacity which says how many cars an hour can drive along that. Fair enough. The next thing we want to be able to discuss are flows. We want to be able to talk about flows of traffic through this network, and talk about what's a valid flow and what isn't. And before we get into anymore detail on that, in the last example we actually talked about sort of exactly which routes different cars take. You know a thousand cars traveled this route and another thousand traveled this route and so on and so forth. But this is a little bit more complicated than we want to do. Rather than talking about where each individual car goes, we're instead just going to concern ourselves with the total number of cars, the total amount of flow along each edge. So in particular, we're just going to figure out how much flow goes along each edge. But this, of course, needs to satisfy a couple of conditions. It can't just be any number we like. The first of these is rate limitation. For any edge E, for one thing the flow along that edge needs to be non-negative. You can't send a negative number of cars along this road. And secondly the flow needs to be at most the capacity of the edge. You can't run more cars along the road than the total capacity of the road fits. The second thing is a little more subtle, it's conservation of flow. The idea here is that if a car drives into an intersection, then eventually it needs to drive out of the intersection. And what this says is that at any vertex except for sources where flow gets created and sinks where flow gets destroyed it needs to be the case that the total flow of cars into that vertex is the same as the total flow coming out of that vertex. So for every vertex, the sum over all edges pointing into the vertex of the flow is the same as the sum over all edges going out of that vertex of the flow along that edge. And so putting this together formally, we define a flow on a network is just an assignment of a real number, f sub e, to each edge e. Such that these two conditions hold for each edge E the flow on that edge is between 0 and the capacity of the edge and for all vertices V except for sources and sinks the total flow into that vertex is the same as the total flow out of that vertex. So that's what a flow is. So for example, in our example from last time, we have all of these cars traveling in various directions, and on each road, we can compute the total amount of flow, the total number of cars flowing along that road. So there are 5,000 along the main highway, the northern highway going up has 2,000 cars an hour, half of them going one way, half of them spooling off the other way. And for each road, you just label how many cars an hour are traveling along that road. And if you look at this for a while, you can actually determine that yes, these satisfy the properties that we want. No road has more flow than its capacity and flow is conserved at each of these three vertices that aren't sources or sinks. So to make sure that we're all on the same page here, we have a network listed up above, and then three possible assignments of flow. Which of these three are valid flows for the given network? Well, you look at these for a while, you compare to the definitions, and you'll find out that C is the only valid flow. A has the problem that it doesn't conserve flow at the denoted vertex. It has six units of flow going into that vertex but seven units of flow coming out. B conserves flow everywhere, but the edge that's highlighted has six units of flow whereas the capacity is five. On the other hand if you look at diagram C, everything works out. Flow is conserved, nothing goes above capacity, it's all great. Okay, so this is what a network flow is, but network flows are actually very useful to study because they actually model a large number of real life phenomena. We've already talked about flows of goods or people along a transportation network which fit very cleanly into this model, but you can also look at flows of electricity along a power grid or flows of water through pipes or even flows of information through a communications network. All of these are going to be examples of network flows in which this sort of formalism that we've developed will be useful for analyzing problems. Now, what types of problems are we going to be studying? Well, the big one that you want to know is the size of a flow. You want to really know how much stuff is actually flowing. How many cars are actually evacuating the city? How many can we get to evacuate the city? And for this, we need to define the size of a flow. And it turns out this can be computed by looking only at the sources. And the idea is that any flow, it gets created at the source, they sort of drive until they hit a sink and then they go away. But if we could just measure how much flow is coming out of the sources, that will tell us how much there is in total. So given the flow after we defined its size to be the sum of all edges that leave a source of the flow coming out of that source minus the sum over all edges going into a source of the total flow through those edges. And so it's the total flow going out of source minus the total flow going into sources, that's the size of the flow. Now, it turns out you can equally well compute this by looking only at sinks. The Lemma says the size of the flow is equal to the sum of flow going into a sink minus the sum of flow going out of a sink. And the argument here is pretty nice, we'll be seeing similar things a lot. So the thing to note is that if you take the sum of all vertices of the total flow going into that vertex minus the total flow going out of that vertex, that's actually zero because each edge, some flow leaves the vertex but then goes into another vertex, so the two terms cancel out. On the other hand, if we take vertices that aren't sources or sinks, but conservation of flow, that inner term is zero. So this is the same as the sum only over sources and sinks of the total flow into that vertex, minus the total flow out of that vertex. Now if we look at the sum only over sources of the flow into the vortex minus the flow out of the vortex, that's minus the size of the flow. And the other term is just the flow into sinks minus the flow out of sinks. And since the sum is zero, the total flow into a sink minus total flow out of a sink Is the same as the size of the flow which what we were trying to prove. Okay so that's what the size of the flow is. The big problem that we're going to be trying to solve, and we'll really discussing how do you solve this problem for the next several lectures, is how much flow can you fit through a network? Formally this is called the maxflow problem. The input should be a network G, so a graph with these capacities and some designated sources and sinks, and the output should be a flow f for the graph G such that the size of the flow f is as large as possible. And this is the problem that we're going to be spending the next several lectures on. So, come back, next lecture we'll start talking about some of the tools that will be useful in designing these algorithms. So I'll see you then.