Hello, everybody. Welcome back to our network flows unit. Today we're going to talk about an application of some of these network flow algorithms we've been discussing, to a problem called bipartite matching. So to get started on this, suppose you're trying to coordinate housing in a college dormitory. So what you have is, you've got n students and m rooms. Each student is giving you a list of rooms that they consider to be acceptable, and what you'd like to do is place as many students as possible in an acceptable room. Now, of course, there's a limitation here that you can't place more than one student in the same room. Okay, so this is the problem. How do we organize this data? Well, I mean, you got a bunch of students. You got a bunch of rooms. And there's some pairs of students in rooms, without students willing to be in that room. And so a great way to organize this data pictorially is by with this bipartite graph. A bipartite graph is a graph G whose vertex set is partitioned into two subsets, U and V, students and rooms. They're sort of two types of vertices, so that all edges in the graph are between a vertex of U and a vertex of V, so all the edges that connect the student to a room now connect the student to a room to a room. And so if we just redraw that graph and call two sides U and V instead of Students and Rooms, it's exactly a bipartite graph. So what we'd like to do on this graph is find what is called a matching. We want to find a bunch of pairs of different rooms, that's a bunch of edges in a graph, but it needs to be the case that each student gets assigned only one room, and each room is assigned to only one student, and that says that no two of these edges that we pick can share an end point. So in our example if you look at the blue edges here, that will give us a matching. We've got a bunch of pairings of students get paired to rooms that they were acceptable to be paired with. And each student assigned only one room, and each room is assigned to at most one student. So the big problem we're going to try and solve is known as bipartite matching. Given bipartite graph G, we try to find a matching of G that consists of as many edges as possible and ideally one that pairs up all of the vertices with each other. So, just to be sure that we're on the same page, if I give you the bipartite graph, what's the size of the number of edges in the largest possible match? Well, you have to play around with it for a bit. You can find that you can actually get matchings of size three here and it takes a while, but you should be able to convince yourself that it's not actually possible to get the matching here of size four, five. So, let's talk about applications. Bipartate matching actually has a bunch of applications. One thing, need be is matchmaking. Suppose you have a bunch of men, women, some pairs of them are attracted to each other and you would like to sort of pair them off into as many possible couples as possible, such that nobody is dating more than one person at the same time. Now, we have to be a little bit careful here. If there are gay people, then this doesn't quite fit into the context of bipartite matching, because there are men attracted to men or women attracted to women. The graph is no longer bipartite. And there's nothing wrong with this necessarily, but it will make the problem computationally more complicated. Another example that you might want to consider is maybe a scheduling problem. You have sort of a bunch of events that need to be scheduled at different times. Each event has some blocks of time that would work for it and you need to make sure that no two events get the same time block. Once again, sort of a bipartite matching problem. So how are we going to solve this problem? They key idea is there's a connection between this problem and network flows, sort of what you want to solve in bipartite matching is you want to connect nodes on the left to nodes on the right without putting too many connections though a given node. This sounds sort of like a flow problem. You want to have flows running from left to right without too much flow running through any given node. So to make this work, you add source nodes and connect them to the left and have the right node to connect to a sink node and build up a network. So in particular, we start with our bipartite graph. You direct all of the edges left to right. We're going to add a source and sink node. We're going to hand the source node to the vertices on the left and connect the vertices on the right to the sink and we're going to define all the edges of this graph to have capacity one. This gives us a network associated to our bipartite graph, and it turns out that for every matching in our bipartite graph there's a corresponding flow on the network. And so to be formal about this, if G is the bipartite graph and G prime the corresponding network, there's actually a one to one correspondence between bipartite matchings on G and integer value flows on G prime. And just to prove this, well, if you have a matching, we can produce a flow by running flow through each edge of the matching. Then to make everything balance out, each vertex of U, which we had flow running through it, we need to have flow coming to that vertex from S, and then that edge goes to some vertex and V and that needs to extend through the edge to t, and that will give us a flow. Now if we have a flow and wants to go back to a matching, you just look at these middle edges between U and V and say which ones of them have flow? And those edges, we use in the matching. Now, we can't have two edges coming out of same vertex of view because there wont be enough flow going into that vertex. There is only one unit of flow going in at most and so there can't be two units coming out. And we also can't have the edges sharing the same vertex on V for basically the same reason. And so there's a relationship between bipartite matching and integer valued flows. However, you'll note that it was a Lemma that we proved that you can always find an integer valued maximum flow. And so our max flow algorithm sort of already worked for solving this problem. So this gives a very simple a algorithm for solving bipartitematching. You construct the corresponding network G'. You compute a maxflow for G' in such a way that gives you an integer maxflow. You then find the corresponding matching and return it. That solves the problem. Now, we could just say that we're done here, but there's something very interesting going on. So Maxflow-Mincut, relating to maximum flow to the minimum cut, which is sort of nice as a theoretical tool. But here these bipartite graphs, the maximum matching relates to a maxflow and lets see what these cuts relate to. So if we have the network corresponding to a matching and look at a cut in this network, well, this cut contains the source and it contains some set x of vertices on the left and some set y of vertices on the right. And we'd like to make this cut as small as possible. Now if we fix x, the vertices on the right will sort of, when do they contribute to the cut? Well, vertices in Y, they have edges to T which produces sort of one edge to the cut. But if you had an edge from X to a vertex not in Y, then that would also give you one edge that breaks the cut. And because of this it actually can be shown that you can basically afford to just let your elements in Y be exactly the elements in the right hand side that are connected to by some element of X. Now if we do that, what edges break the cut? Well, you've got edges from S to elements of U that aren't in X. Now, by the way we constructed these, vertices in X can only connect to vertices in Y that are also in the cut. But vertices in Y they connect to T and those also give you edges out of the cut. So the total size of the cut is the size of U minus X plus the size of Y. However, you'll note that all edges in G connect to either a vertex in Y or a vertex in U minus X. So one way to find a bound on your matching is by finding a set of vertices such that every edge in your graph connects to one of those vertices. And working this out gives us what's called Konig's theorem, which says if G is a bipartite graph and k is the size of the maximal matching, then there has to be a set S of only k vertices of the graph, such that each edge in G connects to one of these vertices of S. And you'll note that if you have such an S, that gives you a bound in the maximal matching, because each edge needs to use up one of those vertices and no two edges can share a vertex. And so Konig's Theorem says that sort of the maximum matching on the graph is the same as the minimum when it's called vertex cover set s of vertices that connect to all edges. So, for example, if we have the following graph, you'll note that these four vertices connect to every single edge in the graph. So that says immediately the maximum match can size at most four and it turns out that in this case its tight. Now theres one more special case of Konig's theorem that's worth mentioning. That the case where G is a bipartite graph with n vertices one each side. One thing that you might want to do is produce what's called a perfect pairing on G. That is a match that uses every single vertex on both sides. Now, it's a theorem that you should have specialized Konig's Theorem to this case, you can show that there's always a perfect pairing, unless there's some set of only M vertices on the left hand side, such that the total number of vertices that they connect to is strictly less than that. So you can always pair up your n men with your n women, unless there's some collection of M men that pair with a total of fewer than M possible women, and if that's the case, these M men can not all simultaneously have distinct dates, and so it's clearly not possible to produce your perfect pair. So in summary, we've got this interesting problem of maximum matching, and we can solve it by resulting it to a problem of finding maximum flows. Furthermore, maxflow-mincut gives us some interesting characterizations of the sizes of this maximum action. So, that's all I have to say about bipartite matching. Come back next session, we'll talk about one more problem that you can solve using this maxflow technology that we've developed.