﻿[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?