[Script Info]
Title:
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:00.00,0:00:04.00,Default,,0000,0000,0000,,So maybe you already see a pattern emerging here, but I am now going to
Dialogue: 0,0:00:04.00,0:00:11.00,Default,,0000,0000,0000,,deviate just a little bit from this. I am now going to add 3 vertices here, 3 vertices here,
Dialogue: 0,0:00:11.00,0:00:17.00,Default,,0000,0000,0000,,3 vertices here, 3 vertices here, so this is a total of 12 vertices.
Dialogue: 0,0:00:17.00,0:00:23.00,Default,,0000,0000,0000,,And just so that we keep that in mind here, up here we have 8, here we have 12,
Dialogue: 0,0:00:23.00,0:00:29.00,Default,,0000,0000,0000,,and here we have 24 in these layers here. Now how am I going to connect those?
Dialogue: 0,0:00:29.00,0:00:34.00,Default,,0000,0000,0000,,And this is where the picture gets actually quite messy. I'm going to connect
Dialogue: 0,0:00:34.00,0:00:41.00,Default,,0000,0000,0000,,them to all those here. So each of these 3 vertices here that I've added is connected
Dialogue: 0,0:00:41.00,0:00:48.00,Default,,0000,0000,0000,,to 6 other vertices, so there's 6 edges going out here--1, 2, 3, 4, 5, 6--and what you see
Dialogue: 0,0:00:48.00,0:00:53.00,Default,,0000,0000,0000,,also is that each of the vertices here in this layer--the first layer that I added--
Dialogue: 0,0:00:53.00,0:01:04.00,Default,,0000,0000,0000,,is connected to exactly 5 vertices. So 1, 2, 3, 4, 5. And of course I deliberately
Dialogue: 0,0:01:04.00,0:01:07.00,Default,,0000,0000,0000,,constructed this in this way, and I'm going to draw these out here in a minute.
Dialogue: 0,0:01:07.00,0:01:13.00,Default,,0000,0000,0000,,I just want you to understand the principle. I've added these 12 vertices here in a way
Dialogue: 0,0:01:13.00,0:01:22.00,Default,,0000,0000,0000,,such that the greedy algorithm will first take these 12 here, then it will take these 8 here,
Dialogue: 0,0:01:22.00,0:01:27.00,Default,,0000,0000,0000,,and then it will take these 12 here. So I'm constructing my graph so that the greedy
Dialogue: 0,0:01:27.00,0:01:32.00,Default,,0000,0000,0000,,algorithm will choose the vertices in exactly the reverse order that I am adding them
Dialogue: 0,0:01:32.00,0:01:37.00,Default,,0000,0000,0000,,to the network. And in that way I can make that algorithm behave very, very, very badly.
Dialogue: 0,0:01:37.00,0:01:41.00,Default,,0000,0000,0000,,You would think that theoretical computer science is a clean and not messy science,
Dialogue: 0,0:01:41.00,0:01:46.00,Default,,0000,0000,0000,,but I think I can just show you the opposite here. But you get the principle now.
Dialogue: 0,0:01:46.00,0:01:54.00,Default,,0000,0000,0000,,So these 24 vertices here are the first ones that I have added, and I have now added
Dialogue: 0,0:01:54.00,0:01:58.00,Default,,0000,0000,0000,,these layers here. So I first added these 12 here, then these 8, then these 12 here
Dialogue: 0,0:01:58.00,0:02:02.00,Default,,0000,0000,0000,,in such a way that the greedy algorithm will choose these vertices here to be in a
Dialogue: 0,0:02:02.00,0:02:08.00,Default,,0000,0000,0000,,vertex cover and these here in a vertex cover. So the question, of course, now is,
Dialogue: 0,0:02:08.00,0:02:13.00,Default,,0000,0000,0000,,can I add even more vertices to this so that I am still making the greedy algorithm
Dialogue: 0,0:02:13.00,0:02:19.00,Default,,0000,0000,0000,,take my new vertices that I add? And in fact I can, but it will become really messy
Dialogue: 0,0:02:19.00,0:02:22.00,Default,,0000,0000,0000,,to draw. So I'm more going to explain to you how I'm going to do this rather than
Dialogue: 0,0:02:22.00,0:02:26.00,Default,,0000,0000,0000,,actually draw out every single vertex. So you see for each of the vertices
Dialogue: 0,0:02:26.00,0:02:31.00,Default,,0000,0000,0000,,that I've added here, I've connected them to larger and larger groups of these vertices
Dialogue: 0,0:02:31.00,0:02:37.00,Default,,0000,0000,0000,,here in the middle of those original 24, and I can continue this for a little bit by now
Dialogue: 0,0:02:37.00,0:02:45.00,Default,,0000,0000,0000,,adding 2 vertices which would then be connected to groups of 8 down here.
Dialogue: 0,0:02:45.00,0:02:53.00,Default,,0000,0000,0000,,So this would be connected to all over here, and then I will do the same part here.
Dialogue: 0,0:02:53.00,0:02:58.00,Default,,0000,0000,0000,,So again I can add 2 vertices here, and I will connect them to this group of 8,
Dialogue: 0,0:02:58.00,0:03:02.00,Default,,0000,0000,0000,,then 2 more vertices here, and I will connect them to this group of 8.
Dialogue: 0,0:03:02.00,0:03:08.00,Default,,0000,0000,0000,,And if you want, you can of course check. It will still be such that the 6 vertices
Dialogue: 0,0:03:08.00,0:03:12.00,Default,,0000,0000,0000,,I've now added will be the first ones that are picked by the greedy algorithm.
Dialogue: 0,0:03:12.00,0:03:16.00,Default,,0000,0000,0000,,And then those 12, and then those 8, and then those 12.
Dialogue: 0,0:03:16.00,0:03:20.00,Default,,0000,0000,0000,,What I can then do is I can add another 4 vertices, and this time I will look at
Dialogue: 0,0:03:20.00,0:03:26.00,Default,,0000,0000,0000,,groups of 12. So I will add 4 vertices connected to these 12 here in the middle,
Dialogue: 0,0:03:26.00,0:03:30.00,Default,,0000,0000,0000,,and I will add 4 vertices connected to these 12 here in the middle.
Dialogue: 0,0:03:30.00,0:03:34.00,Default,,0000,0000,0000,,And we'll be done soon, so in case you think this gets very tedious, bear with me
Dialogue: 0,0:03:34.00,0:03:38.00,Default,,0000,0000,0000,,for just another moment here, and we'll be done.
Dialogue: 0,0:03:38.00,0:03:42.00,Default,,0000,0000,0000,,So we've added another 8 vertices, and again these will be the first ones picked by
Dialogue: 0,0:03:42.00,0:03:46.00,Default,,0000,0000,0000,,the greedy algorithm. And final addition of vertices actually. I will add
Dialogue: 0,0:03:46.00,0:03:53.00,Default,,0000,0000,0000,,another 11 vertices. And these vertices will be connected to all 24.
Dialogue: 0,0:03:53.00,0:03:59.00,Default,,0000,0000,0000,,Now my question for you is, how large is a minimum vertex cover for this network
Dialogue: 0,0:03:59.00,0:04:03.00,Default,,0000,0000,0000,,that I've constructed here? And remember every vertex is connected to those 24
Dialogue: 0,0:04:03.00,0:04:07.00,Default,,0000,0000,0000,,vertices here in the middle. So please enter the size of the minimum vertex cover
Dialogue: 0,0:04:07.00,9:59:59.99,Default,,0000,0000,0000,,here into this box.