[MUSIC] [SOUND] Hello everybody, and welcome back to our course on discrete mathematics. Today I want to introduce you to an important concept of graph theory. The one is bipartite graphs. The other is matchings in graphs. But first of all let me make small announcement. Believe it or not today is the first time in my whole life that I'm giving a power point presentation. Now, this sounds ridiculous but that's how it is. So believe it or not, so far I have been using a wonderful program called IPE, I-P-E, to produce the beautiful PDF slides of this course. And then when I was done with the PDFs I used this Surface Pro and the program called Drawboard, to actually give presentations. And write into the PDF in the life fashion and everything went perfect until today, where for some reason, Drawboard installed an update. And now it's unusable for presentation purposes and somehow I cannot downgrade to the previous version. So we just spend two hours figuring out what to do, finally we decided to converge the whole PDF into PowerPoint. And somehow we were able to do this, and it worked kind of okay, it actually looked still quite nice, so I'm very impressed. And this is why I'm today giving the first PowerPoint presentation of my life! Welcome to all of you! Let's start with Matchings in Bipartite Graphs. As a motivating example, suppose you have to organize a three day workshop Monday, Tuesday and Wednesday. And, for this workshop, you invite five keynote speakers Doctor A, Professor B, C, D and E. And you want each of these keynote speakers to give a keynotes talk, keynotes speech in one of the six available time slots. Now of course, the speakers are very busy people so they don't have time all time for example. Dr. A only has time Monday and Tuesday morning, and so on. So now our job is to find an assignment from keynote speakers to available timeslots that fits everybody. So let's try to see whether we can do something meaningful here. For example, I can tell Professor D to take the Wednesday morning slot. This is kind of a safe choice before, because he's the only one who has time Wednesday morning. And by similar reasoning, now here, Professor B can take this slot, Doctor A takes this and so on. All right. Okay, so everybody is happy, every speaker has a time slot, yeah has a preferred time slot it's okay. But now let's look at a second example and try to figure out what we can do here. So for example we can again say professor E should talk Wednesday morning. Professor C should talk Tuesday morning, there is no harm in doing so, there are no conflicts, but now we run into trouble. Because with three remaining unassigned speakers, and they only have time at two timeslots, namely Monday morning and Tuesday afternoon. So, you see here. There is a mismatch. There are still three unassigned speakers and they only have time at two different time slots. So, in this example no matter what we try, we are not able to assign our speakers to available time slots. All right, so I think now that we are ready for some formal setup. The key notion here one of a bipartite graph. A bipartite graph is simply a graph, vertex set and edges, but the vertex set comes partitioned into a left set that we call u. And a right set that we call v, and edges only are allowed to be between these two sets, not within one. So this is a Bipartite graph. Bipartite graph a matching something like this A matching, it's a set m of edges that do not touch each other. So they don't share any end point that's unmatching. What's more, if you look at a set here, for example this as an a, for set a in u on the left hand side, we define gamma of a to be the neighborhood. Neighborhood, meaning all the vertices on the right hand side are adjacent the vertices A. So here the neighborhood would consist of these two vertices, that's Gamma of A. And then, we define the discrepancy of a delta of A to be the sine of A minus gamma of A. That's the discrepancy. So the discrepancy of this set here would be 1 because A has three elements and gamma of A has two elements. And now you see that's exactly the argument we used before, that we don't find a perfect assignment. So now you see every matching must leave at least delta a vertices of a unassigned because there is simply not enough space to assign it to. Let me give you one more example. So another set for example, let's see A is just a set containing this vertex and then what would the neighborhood be? Gamme of this vertex could consist of these four vertices and then the discrepancy is actually a negative. The discrepancy would be minus 3. So we define the discrepancy of the graph to be the maximum overall Delta A for all A on the left hand side over all sets. And now, you see some sets can have negative discrepancy but the total, the maximum discrepancy of the whole graph will always be 0 or more because we can choose an empty set here. And then, the neighborhood of the intercept is also the intercept, and the discrepancy is 0 minus 0 which is 0. So there is maximum discrepancy delta of g, is always a non negative number. All right, here are all these definitions again, a little bit more nicely written for further reference. Now what I informally told you before is something that I like to call Hall's theorem, the easy part. It says if you have a set A on the left side and you have matching, then the matching cannot be bigger than U minus delta A. In other words, the matching must leave at least a delta A vertices unmatched. And well, this is easy to see but what's not easy to see and not easy to prove is the other part which I call the hard part of Hall's Theorem. It says there is actually a matching in the set with these two numbers match. This is called the hard part of the Hall's Theorem. So altogether you can combine these two things into something that's called Hall's theorem if G is a bipartite graph, then the maximum matching has size U minus delta G. So this is an example of a theorem where something that's obviously necessary is actually also sufficient. And we will prove Hall's Theorem in the next session. We don't have time today, but what I want to do today is, I want to talk about algorithms. So, in the beginning I gave you a bipartite graph that had a total of 11 notes, I think where like key five notes speakers and six time slots. And this was reasonably small, so we could figure out by hand that the best thing we could do was to assign four speakers to a time slot, but we couldn't assign all five speakers to a time slot. But if you have a very large bipartite graph, well then you need a clever algorithm to do that. And this is what I'm going to show you now. I'm going to show you an efficient polynomial time algorithm for maximum matching and the cool thing is we actually don't have to do a lot of work. Because we can recycle an algorithm that we have seen in the last sessions. I'm talking about maximum flow. So here is what you do. Here is your bipartite graph, I add two vertices. I add a source vertex s, and a sync vertex t. And I want to take this bipartite graph and make it into a flow network somehow such that I can apply the maximum flow algorithm. So, I do something like this, and like this. So, I give every edge a direction, and I add edges from S to the left side, and so on. To make this a flow network I have to tell you what the capacities are. Capacities are this, like in the middle they have infinite capacity. I know you should shout at me and say well, last time in the last sessions you said the capacity is a real number. But infinity is not a real number. You're right so if you don't like this infinity down here what you could do, you could replace it something like by 2 times U. Where U is the number of vertices on the left side. But conceptually you will see everything works fine but conceptually it's easier to think about this capacity as really being infinity. Good, so now we have a flow network. And we can find a flow here. Now we have to think what doe the flow have to do with a matching? One direction is kind of easy. Suppose I give you the matching in the bipartite graph. We can't extend this matching to a flow in the network. So we start with a matching of site 3 and we extend it to a flow of the U 3. Okay, now the question is, can we invert this? If I give you a flow and you give me a matching of the same sites. Well it seems obvious, right? Here we have a flow of 3 three and we just go back and here is your matching of site 3. Fair enough, but how about a flow like this? This is also a flow of value 3, but can you transform it easily in to a matching? Well now it's more difficult, and it is more difficult because your flow values here in the middle aren't integers. If everything were 0 and 1 it would be easy, right? But here we have a flow of one-half, it's not clear how to extract matching from this. Luckily, we remember from the session about maximum flow that we proved the following theorem. There is a maximum flow that is integral. All the capacities in our network are integers and there is a maximum flow in which every flow is integer. For example like this. And if you study this network, it's easy to see that the flow can only be 0 or 1. So every edge that carries flow has to carry one unit of flow and given such an integral flow it's actually easy to extract the matching. And now you see if you take a maximum integral flow it must be a maximum matching. So the total algorithm looks like this, you start with a bipartite graph you make it into a flow network. You find an integral maximum flow in this network and then you extract your maximum matching. That's it. That's your polynomial time algorithm for maximum flow. And that's it for today, thanks. [MUSIC]
