English subtitles

← Tangled Hypercube - Intro to Algorithms

Get Embed Code
3 Languages

Showing Revision 2 created 05/25/2016 by Udacity Robot.

  1. Here's our last random graph of this unit.
  2. We're going to again generate a graph on n nodes recursively.
  3. Same structure as before.
  4. If there's 1 node, we just return that node.
  5. Otherwise, we do it recursively.
  6. So we generate a graph on n/2 nodes--call that G1.
  7. We generate a graph on n/2 nodes and call it G2--different graph.
  8. Now we randomly scramble the nodes in those two,
  9. keeping the edges in their appropriate way.
  10. Just consider them in a particular order.
  11. Then we connect the first node in this ordering in G1 to the first node in this ordering in G2,
  12. the second one in this ordering in G1 to the second one in G2,
  13. third one to the third one, forth one to the forth one, and so on.
  14. Now we get a set of edges that now breach across these two graphs,
  15. and we call this G and return it.
  16. So based on this random generation process we can ask,
  17. what kind of graph structure did we make?
  18. Is it a ring, a tree, a hypercube, or maybe none of these?