Return to Video

## 14-24 Minimum Cover

• 0:00 - 0:04
So maybe you already see a pattern emerging here, but I am now going to
• 0:04 - 0:11
deviate just a little bit from this. I am now going to add 3 vertices here, 3 vertices here,
• 0:11 - 0:17
3 vertices here, 3 vertices here, so this is a total of 12 vertices.
• 0:17 - 0:23
And just so that we keep that in mind here, up here we have 8, here we have 12,
• 0:23 - 0:29
and here we have 24 in these layers here. Now how am I going to connect those?
• 0:29 - 0:34
And this is where the picture gets actually quite messy. I'm going to connect
• 0:34 - 0:41
them to all those here. So each of these 3 vertices here that I've added is connected
• 0:41 - 0:48
to 6 other vertices, so there's 6 edges going out here--1, 2, 3, 4, 5, 6--and what you see
• 0:48 - 0:53
also is that each of the vertices here in this layer--the first layer that I added--
• 0:53 - 1:04
is connected to exactly 5 vertices. So 1, 2, 3, 4, 5. And of course I deliberately
• 1:04 - 1:07
constructed this in this way, and I'm going to draw these out here in a minute.
• 1:07 - 1:13
I just want you to understand the principle. I've added these 12 vertices here in a way
• 1:13 - 1:22
such that the greedy algorithm will first take these 12 here, then it will take these 8 here,
• 1:22 - 1:27
and then it will take these 12 here. So I'm constructing my graph so that the greedy
• 1:27 - 1:32
algorithm will choose the vertices in exactly the reverse order that I am adding them
• 1:32 - 1:37
to the network. And in that way I can make that algorithm behave very, very, very badly.
• 1:37 - 1:41
You would think that theoretical computer science is a clean and not messy science,
• 1:41 - 1:46
but I think I can just show you the opposite here. But you get the principle now.
• 1:46 - 1:54
So these 24 vertices here are the first ones that I have added, and I have now added
• 1:54 - 1:58
these layers here. So I first added these 12 here, then these 8, then these 12 here
• 1:58 - 2:02
in such a way that the greedy algorithm will choose these vertices here to be in a
• 2:02 - 2:08
vertex cover and these here in a vertex cover. So the question, of course, now is,
• 2:08 - 2:13
can I add even more vertices to this so that I am still making the greedy algorithm
• 2:13 - 2:19
take my new vertices that I add? And in fact I can, but it will become really messy
• 2:19 - 2:22
to draw. So I'm more going to explain to you how I'm going to do this rather than
• 2:22 - 2:26
actually draw out every single vertex. So you see for each of the vertices
• 2:26 - 2:31
that I've added here, I've connected them to larger and larger groups of these vertices
• 2:31 - 2:37
here in the middle of those original 24, and I can continue this for a little bit by now
• 2:37 - 2:45
adding 2 vertices which would then be connected to groups of 8 down here.
• 2:45 - 2:53
So this would be connected to all over here, and then I will do the same part here.
• 2:53 - 2:58
So again I can add 2 vertices here, and I will connect them to this group of 8,
• 2:58 - 3:02
then 2 more vertices here, and I will connect them to this group of 8.
• 3:02 - 3:08
And if you want, you can of course check. It will still be such that the 6 vertices
• 3:08 - 3:12
I've now added will be the first ones that are picked by the greedy algorithm.
• 3:12 - 3:16
And then those 12, and then those 8, and then those 12.
• 3:16 - 3:20
What I can then do is I can add another 4 vertices, and this time I will look at
• 3:20 - 3:26
groups of 12. So I will add 4 vertices connected to these 12 here in the middle,
• 3:26 - 3:30
and I will add 4 vertices connected to these 12 here in the middle.
• 3:30 - 3:34
And we'll be done soon, so in case you think this gets very tedious, bear with me
• 3:34 - 3:38
for just another moment here, and we'll be done.
• 3:38 - 3:42
So we've added another 8 vertices, and again these will be the first ones picked by
• 3:42 - 3:46
the greedy algorithm. And final addition of vertices actually. I will add
• 3:46 - 3:53
another 11 vertices. And these vertices will be connected to all 24.
• 3:53 - 3:59
Now my question for you is, how large is a minimum vertex cover for this network
• 3:59 - 4:03
that I've constructed here? And remember every vertex is connected to those 24
• 4:03 - 4:07
vertices here in the middle. So please enter the size of the minimum vertex cover
• 4:07 -
here into this box.
Title:
14-24 Minimum Cover
Team:
Udacity
Project:
CS313 - Theoretical Computer Science
Duration:
04:10
 Amara Bot added a translation

• Amara Bot