[Script Info]
Title: 
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:00.00,0:00:02.00,Default,,0000,0000,0000,,Here's our last random graph of this unit.
Dialogue: 0,0:00:02.00,0:00:05.00,Default,,0000,0000,0000,,We're going to again generate a graph on n nodes recursively.
Dialogue: 0,0:00:05.00,0:00:07.00,Default,,0000,0000,0000,,Same structure as before.
Dialogue: 0,0:00:07.00,0:00:09.00,Default,,0000,0000,0000,,If there's 1 node, we just return that node.
Dialogue: 0,0:00:09.00,0:00:12.00,Default,,0000,0000,0000,,Otherwise, we do it recursively.
Dialogue: 0,0:00:12.00,0:00:15.00,Default,,0000,0000,0000,,So we generate a graph on n/2 nodes--call that G1.
Dialogue: 0,0:00:15.00,0:00:18.00,Default,,0000,0000,0000,,We generate a graph on n/2 nodes and call it G2--different graph.
Dialogue: 0,0:00:18.00,0:00:21.00,Default,,0000,0000,0000,,Now we randomly scramble the nodes in those two,
Dialogue: 0,0:00:21.00,0:00:24.00,Default,,0000,0000,0000,,keeping the edges in their appropriate way.
Dialogue: 0,0:00:24.00,0:00:26.00,Default,,0000,0000,0000,,Just consider them in a particular order.
Dialogue: 0,0:00:26.00,0:00:30.00,Default,,0000,0000,0000,,Then we connect the first node in this ordering in G1 to the first node in this ordering in G2,
Dialogue: 0,0:00:30.00,0:00:34.00,Default,,0000,0000,0000,,the second one in this ordering in G1 to the second one in G2,
Dialogue: 0,0:00:34.00,0:00:37.00,Default,,0000,0000,0000,,third one to the third one, forth one to the forth one, and so on.
Dialogue: 0,0:00:37.00,0:00:41.00,Default,,0000,0000,0000,,Now we get a set of edges that now breach across these two graphs,
Dialogue: 0,0:00:41.00,0:00:43.00,Default,,0000,0000,0000,,and we call this G and return it.
Dialogue: 0,0:00:43.00,0:00:45.00,Default,,0000,0000,0000,,So based on this random generation process we can ask,
Dialogue: 0,0:00:45.00,0:00:47.00,Default,,0000,0000,0000,,what kind of graph structure did we make?
Dialogue: 0,0:00:47.00,0:00:51.00,Default,,0000,0000,0000,,Is it a ring, a tree, a hypercube, or maybe none of these?