24.1.8.4. Hypercube Graph (Q-n)

We also have another special simple undirected graph called as the n cube or the hyper cube denoted by this notation Q_n. So, this graph will have 2^n nodes, where each node represents a possible n bit string.

The hypercube graph, Q_n, is a specific type of graph in which the number of nodes (vertices) is determined by the formula 2^n, where n signifies the number of dimensions of the hypercube. Each node corresponds to an n-length binary string, which can consist of 0s and 1s. For example, if n=2, then there will be 2^2 = 4 nodes representing the strings 00, 01, 10, and 11.

To visualize this, think of a simple light switch that has two states: on (1) and off (0). If you have a system of n switches, each unique combination of switches represents a unique state (node) in the hypercube. For two switches, they can be in one of the following states: both off (00), the first one on and the second one off (01), the first one off and the second one on (10), or both on (11).

You have an edge between the ith vertex and the jth vertex if the bit strings represented by the ith vertex and the jth vertex differ in exactly one bit position.

In a hypercube graph, an edge connects two vertices if their corresponding bit strings differ by exactly one bit. For instance, if we consider Q_2 with the vertices for 00, 01, 10, and 11, the edge will exist between vertices 00 and 01 because they differ in the last bit, and between 00 and 10 because they differ in the second bit. If two vertices differ in more than one bit position, like 00 and 11, then there is no edge connecting them.

Imagine you are standing on a chessboard (which can represent a hypercube). Each square is a vertex, and moving from one square to an adjacent one (edge) requires a single move. If you want to move from square A (e.g., 00) to square B (e.g., 01), you can only change one square (one bit) at a time. Jumping across multiple squares means changing too many bits at once.

To construct Q_n, you take two copies of the graph Q_(n-1) and add edges depending upon the bit strings differing in one bit position.

The construction of a hypercube graph follows a recursive pattern. Q_n is built using two copies of the previous hypercube graph, Q_(n-1). Each vertex of Q_(n-1) gets a unique prefix (either 0 or 1) in their binary representation for Q_n. For instance, to create Q_2, you can start from two copies of Q_1 (with vertices 0 and 1) and add edges to represent different combinations by adding the 0 or 1 prefix accordingly.

Think of building a family tree. Each generation represents a level in the hypercube (n). As you go up each level, you take all individuals from the previous generation (Q_(n-1)) and assign them prefixes (like 'I' and 'II'). Each time you go one level higher, you double the number of individuals but maintain connectivity based on their relationships (the edges).

If I want to define or get the graph Q_3, I take two copies of Q_2 and extend the length of the bit strings of the nodes by adding one at the beginning of all the strings in the first copy.

Hypercube graphs grow exponentially in terms of the number of vertices and contribute to increased complexity in terms of edges. For example, Q_3 is created by taking two copies of Q_2, where one copy has '1' prefixed to each of its nodes and the other has '0'. This creates a bridge that connects vertices which differ by one bit position, ensuring connectivity in higher dimensions.

Picture a team of dancers rehearsing a routine where each dancer represents a node. As the team grows (moving from Q_1 to Q_2 and to Q_3), they break into smaller groups but still maintain connections through their shared choreography (bit strings). The extra dancers (new dimensions) increase the complexity of the overall performance, creating a larger yet unified dance.

--