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

English subtitles

Revisions