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