Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

English subtitles

← Subsets - Intro to Algorithms

Get Embed Code
3 Languages

Showing Revision 3 created 05/24/2016 by Udacity Robot.

  1. The first part of the subset question asks about planar graphs and trees.
  2. The first thing to note is that not all planar graphs are trees.
  3. For example, here's a ring, which is a planar graph and it's not a tree.
  4. And so planar graphs are not a subset of trees. On the other hand, all trees are planar graphs.
  5. For most trees, it's fairly intuitive to see how it can be drawn in the plane.
  6. For example, this one is already planar.
  7. But for other trees, it might not be so obvious that we can rearrange everything
  8. to lay it outside in the plane, and so it'd be nice to have a proof that all trees are planar
  9. instead of relying just on intuition.
  10. One way to prove this is to show that any tree can be drawn inside of a triangle.
  11. And then larger trees can be constructed by combining these triangles.
  12. More formally, what we want to show is that any tree can be drawn in a plane inside a triangle
  13. with any given node at the apex of the triangle.
  14. And so for the base case of one node, we can draw the node at the apex of the triangle
  15. and this is trivially in a plane.
  16. And so, our inductive step is to assume that the claim is true for all graphs with less than n nodes.
  17. And we want to show that the claim is true for all graphs with n nodes.
  18. So we'll start with a tree with n nodes. We use this for example.
  19. We're going to pick any node kind of at random and we'll call it r.
  20. For example, one of this node be r. And then we remove r.
  21. Because our original graph was a tree, this separates the graph into separate disjoint trees.
  22. And now since each of these trees have less than n nodes,
  23. we can draw each one inside of a triangle.
  24. First, we can take this tree of four nodes and draw it inside of the triangle.
  25. Notice that the node that was connected to r is at the apex of the triangle.
  26. And then we could do the same for the other two trees.
  27. And then in our last step, we'll make a bigger triangle and we put r at the apex
  28. and then connect it to the apexes of the other triangles.
  29. This verifies our claim and shows that all tree graphs are planar.
  30. They are definitely neither due to the definition of trees.
  31. A tree can have no cycles and a ring must have a cycle.
  32. The answer is neither. >>Yeah. >>Cool.
  33. I never got a really specific definition of a chain besides just the example which was enough but--
  34. Yeah, same idea kind of a chain doesn't have a cycle whereas a ring does.
  35. And the other thing we got definitely was that the edges in the chain is the number of nodes minus 1
  36. and the edges in the ring is equal to the nodes.
  37. Therefore, there can be no crossover between them. They're mutually exclusive.
  38. All chains are trees but not all trees are chains and so its the first one.
  39. It satisfies the definition of a tree graph that it's connected but there are no cycles,
  40. and then the other description of a tree graph that every pair of nodes in the graphs
  41. has a unique path between them.
  42. I mean a chain does that also.
  43. This is definitely one that answer intuitively by looking at the examples.
  44. It gives me 100% confidence in making that claim.
  45. Yeah and just kind of a quick example of--that's a tree and that is not a chain so--
  46. Correct. And the way I convinced myself of that is drawing an example of a hypercube
  47. that was not a ring and a ring that was not a hypercube.
  48. Unless you have a ring that is anything but four nodes it's not a hypercube.
  49. Okay. >>And any hypercube that's anything but four nodes is definitely not a ring.
  50. Great. So yeah I'll draw one for you and it's just a normal cube.
  51. Right. >>And our second to the last problem is just grids and chains.
  52. All chains are grids but not all grids are chains so it's the--chains are the opposite of grids.
  53. Yeah. >>Any chain within nodes is a 1xn grid.
  54. Once you get a grid that has more than one in either of the two directions, it's no longer a chain.
  55. And no matter how long you make a chain-- >>Yeah. So this is--
  56. You can add a node to the chain--a node of n to the chain, that makes it not a grid.
  57. Kind of the first thing you said we have like a 1xn grid and it's also a chain but yeah.
  58. Yeah. This is for example not a chain. >>Correct. >>Cool.