Tip:
Highlight text to annotate it
X
The next kind of graph we're going to look at is called a hypercube,
and the graph is almost but not quite as cool as the name.
We're going to define a hypercube for any number of nodes as long as
that number of nodes is a power of 2.
Here we have four nodes. That's a power of 2--2².
What we're going to do is we're going to connect edges up in a particular way.
This is how we're going to do it. We're going to imagine that every node has a label.
That label is a bit pattern.
In particular, we're going to imagine that we're going to number each of the nodes,
basically, from 0 up to n - 1.
We're going to connect two nodes if their bit patters differ in exactly one place.
We see this example here.
If we label the nodes--these are now binary numbers 0, 1, 2, 3--
we connect these two nodes because they differ just in the first bit--11, 01.
We connect these two because they differ in the second bit--10, 11.
We connect these two because they differ in the second place--00, 01.
And we connect these two because they differ in the first place--00, 10.
We can generalize this to larger graphs.
Here's a hypercube on eight nodes.
We number the nodes from 0 to 7 in their binary bit patterns.
Then we connect two nodes if they differ in exactly one bit place.
Now, perhaps you can see why these are called hypercubes. This is a cube.
The previous one was a square. What's the next one going to be?
To generate the hypercube for n = 16, we can do this with a very interesting little trick.
What we're going to do is we're going to take two hypercubes of size 8 and 8.
Now 8 and 8 is going to be 16. Let's look at what we can do.
We can leave these bit patterns the way that they are,
and then we can extend them.
Everybody in this hypercube is going to get a 0 in front.
Remember what that means in terms of the binary numbers is that they say the same.
A leading 0 doesn't change anything,
but this second hypercube everyone is going to get a one out in front.
Again, thinking about your binary numbers, what is that doing?
It's adding 8 to all of the number of these nodes,
giving unique bit patterns that we haven't seen before.
Now if we connect the corresponding corners of these two cubes,
which is going to be a little bit messy, and I can draw them deeper,
but it'll start to make the picture a little distracting.
That is a 4-dimensional cube, also known as a hypercube.
We can keep extending this over and over again--5-bit patterns, 6-bit patterns, 7-bit patterns.
Each time what we're doing is connecting two hypercubes of the previous size,
extending them and then connecting the corresponding vertices.