[MUSIC] Hello everybody. As you know, as you might have noticed by now, this is an online course about discrete mathematic. It's not a class about algorithms. But this doesn't mean, we cannot talk about something you might come across in am algorithms course. So, in today's lecture we will talk about, spanning trees in minimum spanning trees. So this is actually a staple of an introductory algorithms class. However, it also makes a lot of sense to talk about it in discrete mathematics, and it will not be completely the same. So here we'll focus a little bit more on the mathematical details and not so much on the implementation in algorithmic details. But let me tell you what spanning tree is, we have a graph here. And what do I have here? Well it's a subgraph okay. It's not an induced subgraph, but it's a subgraph it contains some of the vertices, some of the edges. Now this here is called a spanning subgraph because it contains all the vertices. So a subgraph that contains all the vertices, it's called the spanning subgraph. In the last example, here we see a spanning subgraph that also happens to be a tree and this is called a spanning tree. So this lecture is all about spanning trees. Here is an example that I prepared for you. So this as you can see is a map the Europe. And I put a little dot for every capital of a country in the European Union. So, yes, sorry for the Russians and Ukrainians and so on, but in this example, I focus on the European Union. So let's consider the following scenario, by some miracle the European Union has a lot of money, and for some reason they don't want to spend it on rescuing banks or financing agriculture or something. They want to spend it, on building a high speed internet across Europe. So as a first step what they want, they want to connect all the capitals of the member countries by a new technology, by a new high speed internet technology. So here you see the 25 capitals of the European Union and how can we connect them such that, how can we basically find a connected graph? Well, here is an example, that probably is connected. So, I haven't actually checked. It is most likely not the most efficient way to do it. So, what does efficient means? Efficient means, you some how want to minimize the distances. Because this new technology is expensive, so it probably makes no sense to make a direct link from Lisbon all the way in the west to Athens all the way in the east. That's kind of stupid. So you want to do something like this that looks nice that minimizes the sum of distances. So this problem here is called minimum spanning tree, you want to find the spanning tree of minimum cost. So here the definition is as it follows we have a graph g and we have a cost function, so every edge has a cost. And we want to find the tree for example like this, and we are interested in the cost of the tree. The cost of the tree is simply the sum of the edge costs. And obviously we want to find a tree that, you want to find a spanning tree that minimizes the total cost, so how can we do that? Well let's see, so one algorithm is the following it's called Kruskal's algorithm, we take all the edges and we sort them from cheapest. To most expensive and we just insert them one by one if necessary. So example here. What is the cheapest edge? Well this is the cheapest edge, so lets insert it, then we have edge one here. Do we have another edge of course one? No, so we add edges of two, like this. Okay, then we add this edge. But now, we see this edge is actually not necessary. So, we don't have to add it. But, maybe we add this edge, we add this edge, this edge, this edge. But now, we see we created a cycle. So, we delete this edge but don't insert it. We go through all edges of weight 2. And now we are done I think? Are we done? I think we are done. And now we take the edges of week three. So for example this, 3. This edge we don't take, because it would create a cycle, we don't take either. And that's the edges of weight 3. And then we take edges of weight 4. This obviously we don't take. This we don't take either. Here is an edge of weight 4, this we don't take either. And this we take and now we are done. Okay, now we have find a spanning tree. Now the question is, is that the optimal spinning tree can we find some thing better? The answer is yes, it always finds the optimal spanning tree. And here is, there is kind of several ways to prove that I'll show you the most flexible. It's kind of for me my personal opinion the most accessible proof and it's also the most flexible. So the definition goes as follows, a set is good if there is a minimum spending tree that contains it. So let's make an example, the empty set is good, right because it's contained in a spanning tree. If x is good, then of course x is acyclic. And if x prime is a subset of x, then x prime is also good. Okay and our goal is the following, we start with the empty set, right? And then we add an edge in every step if t doesn't create a cycle. So we have to show if at any moment we have a good set. Then the set in the next step where we add an edge will also be good. So in the end we'll have a tree which consists good set of edges. And this means it's a minimum spanning tree because it's contained in the minimum spanning tree so it must be a minimum spanning tree. So we have to show the following cut lemma. I let you read through it for a while and then I show you to do an example. All right. So, basically what it means here we have a set of good set of edges and it's not connected, so we can partition it into two parts. Like this for example and other several edges crossing it, maybe here is an edge, maybe this is an edge, maybe this. And now the lemma says, of all these edges, take the one of minimum cost. Like this and then I take this edge and I insert it so let's say I make it red and then x + e is good too. That's what the lemma says, and if you think about this will actually show you that the algorithm is correct because the algorithm in every step takes the cheapest edge that connects two connected components. So obviously, crosscals algorithm satisfies the condition of this cut lemma. So your edge sets stays good all the time and in the end you end up with a good set so you have minimum spanning tree. So now, it suffices to prove the cut lemma. Okay, let's try to prove it. So first of all, let's take a partition into two sets. This is S. This is S bar. And now, let's take the edge to this cheapest. It goes from S to S bar. Let's say this is, this edge. This is e, okay. So what do we know? Well x is good, so x is contained in some minimum spanning tree. So case one, if our set E is an X M, sorry, E is of course not in X. And if E is in T, then we are done. Because in obviously X plus E is also contained in T. Second, if not, Then we do the following, we consider T and we add the edge here. And because now this has n edges, it must have a cycle. It has a cycle containing E. So the cycle looks somewhat like this, contains e, but because it is a cycle At some point it must cross the cut again. So let's say this edge up here- Is called f. It might actually cross it several times. But at least once, right? It crosses it at E and at least some other time. And this edge we'll process it the second time, let's call this edge f. So we know that the weight of f is at least the weight of e. Because the weight of e was chosen to be the cheapest edge that crosses the cut. And now you define T prime to be the following, we take T we add E, which creates a cycle and we remove f, and now you have to convince yourself that this is again a tree. Well, how could you convince yourself of it? Well it has n minus one edges Is it connected, well maybe, but it truly is acyclic right, because adding e creates one cycle then we remove an edge from the cycle so it breaks the cycle. So it's acyclic and by the tree theorem we have proved a couple lessons ago it must again be a tree. Okay so what is the cost of T, the cost of T is just the cost well actually I wrote, I think I used C instead of W, cost instead of weight so let's be consistent. C of F, okay C(T prime) is c (T) + c(e)- c(f). And because c of f is larger than c of E at least is large, this is utmost c of T. But t is a minimum spanning tree. So actually c (T prime) must be equal to c(T). So T prime is also a minimum spanning tree. And it contains the set X + e. So we see X together with e as contained in the edge set of T prime and therefore it's good too. So, that proves the theorem and it proves the Cut Lemma. And it also proves the correctness of our algorithm. And notice the beauty of the Cut Lemma. It gives us a lot of flexibility, so we can come up with other algorithms that were differently from Causcal's algorithm. And by the Cut Lemma, we also see that they are correct. So, let's go back a little bit to our example. And I'll show you something that's called Prim's Algorithm. You start with a vertex in the intersects. And now, you take the cuts where this is S and the rest is S bar. So what is the cheapest edge, this. Okay, so the Cut Lemma says we can actually add this edge and now these are two connected components right. This is one connected component. So this is a cut, and now we choose the cheapest edge that goes out. So let's take this edge. At the Cut Lemma it's still a good set, so we're on the right track. Then we let this be S and we chose a cheapest edge going out. Like this. And if we continue until we find a tree, until everything is connected okay? That's called Prim's algorithm. And again by the Cut Lemma, it is correct. It gives you a minimum spanning tree. But you can also come up with different algorithms. Now you could say, well you know you want S to be this. And this here is S bar. And you take the cheapest edge crossing the cut. It would be this edge. And your algorithm add this. I don't know whether it will make sense, I don't know whether this would be faster in any way more efficient than the prim's. Or Kruskal's algorithm, but the cut lemma allows you to do that, it gives you a lot of flexibility. All right, so today we have seen minimum spanning trees, we have seen two algorithms for finding a minimum spanning tree and we have thoroughly proven why these algorithms are correct. All right I think that's enough for today, thanks. [MUSIC]
