Tip:
Highlight text to annotate it
X
Alright, so next we're going to look at some recursively generated graphs.
We start off with a set of n nodes,
then we create a graph on half of the nodes recursively.
We create a graph on the other half of the nodes recursively.
Then we generate some edges that connect up between these two smaller graphs,
and that's the graph that we return.
So, we can get a bunch of different mechanisms
for generating recursive graphs with this basic structure,
depending on how we create the 1st sub graph,
how we create the 2nd sub graph,
and how we connect the two sub graphs together.
So, let's start off with a really simple example.
So, here is some pseudo Python for generating a graph with n nodes.
What's it's going to do is--to make a graph with n nodes--if n is just 1,
it returns a single node all by itself.
But if it's not, we're going to assume it's some other power of 2.
We make a graph with n/2 nodes, call it G1.
We make a another graph with n/2 nodes, call it G2.
Then we pick a random node from G1, call it i1, a random node from G2, call it i2,
and we link them together.
So, at a high level, create graph G1, create graph G2.
We pick a random node i1, pick another random node i2,
and we link them together.
Now, in this picture it's not really clear what's going on inside of these.
What I'd like you to do is figure it out.
So, maybe take n to be some small power of 2, like 4 or 8
and trace through this pseudo code to try to figure out what kind of graph pops out.
So, here are three choices to choose from what we get out.
Is it a tree, is it a chain or is it a ring?