1 00:00:06,540 --> 00:00:12,330 In this lecture, we are going to begin going over the minimum spanning tree. 2 00:00:12,780 --> 00:00:17,400 And before we start talking about a minimum spanning tree, we just need to get an understanding of 3 00:00:17,400 --> 00:00:21,450 what a spanning tree is and what the rules are for it. 4 00:00:21,690 --> 00:00:23,520 So we have three rules. 5 00:00:24,930 --> 00:00:27,930 The first one is we need to be connected. 6 00:00:30,050 --> 00:00:47,990 The second one is no cycles, and the third one is the number of edges is equal to vertices minus one. 7 00:00:47,990 --> 00:00:52,430 So number of vertices minus one. 8 00:00:53,600 --> 00:01:03,740 So we'll start with something simple and we'll say that we have zero one, two and three, and we're 9 00:01:03,740 --> 00:01:10,670 going from 0 to 1, 1 to 2, 2 to 3, 0 to 3 and 3 to 1. 10 00:01:11,960 --> 00:01:15,140 So we see that we're definitely connected. 11 00:01:15,140 --> 00:01:22,580 We're able to get to every node from any node through some form of a path or another. 12 00:01:23,360 --> 00:01:26,720 But we see that rule number two is currently being broken here. 13 00:01:26,720 --> 00:01:34,790 So this is currently not a spanning tree because we see that 031 is cyclic. 14 00:01:38,000 --> 00:01:50,210 We can go 013 cyclic and we can make a couple of cycles out of this, but we also see that we have more 15 00:01:50,210 --> 00:02:00,920 edges than we do nodes, so too many edges in this case as well. 16 00:02:01,160 --> 00:02:09,980 So for us to make this a spanning tree, we can do 0 to 3 to 2 to 1. 17 00:02:09,980 --> 00:02:11,330 That's a spanning tree. 18 00:02:11,360 --> 00:02:15,230 We can do 0 to 1, to 2 to 3. 19 00:02:15,380 --> 00:02:16,910 That is a spanning tree. 20 00:02:17,330 --> 00:02:23,900 And we can also do 0 to 3 to 1 to 2. 21 00:02:23,900 --> 00:02:25,670 And that is also a spanning tree. 22 00:02:25,670 --> 00:02:28,820 And we can continue making more spanning trees out of this. 23 00:02:28,820 --> 00:02:33,800 But I just wanted to show you some examples of what a spanning tree looks like. 24 00:02:33,800 --> 00:02:34,910 So these are all 25 00:02:37,190 --> 00:02:38,150 spanning. 26 00:02:39,980 --> 00:02:40,760 Trees. 27 00:02:42,150 --> 00:02:49,710 So if we want to start looking at a minimum spanning tree, then the sum of weights. 28 00:02:51,400 --> 00:02:52,880 Oh, the. 29 00:02:52,900 --> 00:02:55,330 Some of the edges. 30 00:02:58,990 --> 00:03:00,010 Wait. 31 00:03:03,320 --> 00:03:04,400 Should. 32 00:03:06,680 --> 00:03:07,400 Be. 33 00:03:10,070 --> 00:03:10,700 Minimum. 34 00:03:12,230 --> 00:03:12,830 All right. 35 00:03:12,830 --> 00:03:23,570 So if we take our same example from above of zero one, two and three, and now we start assigning some 36 00:03:23,570 --> 00:03:38,330 weights to them, so we have 0 to 3 is to zero, or 3 to 2 is one, 0 to 2 is three, 1 to 2 is four 37 00:03:38,480 --> 00:03:41,450 and 0 to 1 is five. 38 00:03:42,320 --> 00:03:49,340 So if we want to create a minimum spanning tree to this, then we want to satisfy our three rules above 39 00:03:49,490 --> 00:03:57,050 of it being connected with no cycles and the number of edges is equal to the number of vertices minus 40 00:03:57,050 --> 00:03:57,620 one. 41 00:03:58,700 --> 00:04:05,480 So for us to do this, we we can start out at vertex zero and we see that from vertex zero, we can 42 00:04:05,480 --> 00:04:10,180 go to three or to one, but we see that we have an edge of weight two. 43 00:04:10,190 --> 00:04:11,300 So let's take that. 44 00:04:12,080 --> 00:04:18,920 And then from three we only have one path that we can go, which is one. 45 00:04:19,130 --> 00:04:23,030 So we can go to number two, vertex two. 46 00:04:23,030 --> 00:04:35,570 And we see that we go we can go from 2 to 0 or 2 to 1, but if we take 2 to 0, then we become, then 47 00:04:35,570 --> 00:04:36,950 we create a cycle. 48 00:04:36,980 --> 00:04:40,160 Therefore, there would no longer be a spanning tree. 49 00:04:40,160 --> 00:04:46,310 So our only path that we can take here is going to be to one as well. 50 00:04:47,120 --> 00:04:58,160 And now we have a connected graph and we are minimum because we have two plus four plus one is equal 51 00:04:58,160 --> 00:04:58,910 to seven. 52 00:04:58,910 --> 00:05:06,650 And every other path that we take from here to create a minimum spanning tree will be greater than seven. 53 00:05:06,890 --> 00:05:10,490 So that was a pretty simple example that we could look at. 54 00:05:10,550 --> 00:05:26,210 And so now we can create a slightly more complex graph where we can say zero one, two, three, four 55 00:05:27,770 --> 00:05:41,870 and five, and we can have one, two, seven, two, one. 56 00:05:43,150 --> 00:05:46,960 Three, six, 57 00:05:49,870 --> 00:05:55,720 four, and from 4 to 2 we will go three. 58 00:05:56,290 --> 00:06:00,520 And from 1 to 3 we will go five. 59 00:06:01,600 --> 00:06:07,120 So we'll start at vertex zero again and we see that we can go two different directions. 60 00:06:07,120 --> 00:06:15,220 We can go to either vertex five or one and we'll go with vertex five because it is has a weight of one. 61 00:06:18,440 --> 00:06:19,220 From five. 62 00:06:19,220 --> 00:06:23,000 We can go to four or we can go to one. 63 00:06:23,390 --> 00:06:32,300 And again we'll choose four because we have the lower weight on that edge from four. 64 00:06:32,390 --> 00:06:37,130 We can go to three or we can go to two. 65 00:06:37,610 --> 00:06:40,760 And if we go to three, we have seven as our weight. 66 00:06:40,760 --> 00:06:43,400 And if we go to two, we have three as our weight. 67 00:06:43,790 --> 00:06:51,800 So we'll go to two since we have a weight of three from two. 68 00:06:53,880 --> 00:07:01,230 We can go to one or we can go to three. 69 00:07:02,910 --> 00:07:04,680 So we will go to one. 70 00:07:08,810 --> 00:07:13,490 And from two, we can also go to three. 71 00:07:15,250 --> 00:07:17,080 Where we have a weight of to. 72 00:07:18,280 --> 00:07:26,110 So here the weight of our minimum spanning tree is going to be equal to nine. 73 00:07:26,680 --> 00:07:29,350 And we see that we are connected entirely. 74 00:07:29,350 --> 00:07:39,220 We have no cycles and we have one, two, three, four, five edges and we have one, two, three, 75 00:07:39,220 --> 00:07:42,070 four, five, six vertices. 76 00:07:42,070 --> 00:07:45,640 So this would be our minimum spanning tree. 77 00:07:46,180 --> 00:07:54,430 So in the next lecture we will go over the implementation for a minimum spanning tree. 78 00:07:54,610 --> 00:08:00,130 So if you have any questions about a minimum spanning tree, please feel free to ask me in the Q&A section.