Grafo de hipercubo

En teoría de grafos , el grafo hipercubo${\displaystyle Q_{n}}$es el grafo de aristas del${\displaystyle n}$hipercubo de dimensión , es decir, es el grafo formado a partir de los vértices y aristas del hipercubo. Por ejemplo, el grafo del cubo${\displaystyle Q_{3}}$es el grafo formado por los 8 vértices y las 12 aristas de un cubo tridimensional. ${\displaystyle Q_{n}}$tiene${\displaystyle 2^{n}}$vértices ,${\displaystyle 2^{n-1}n}$bordes, y es un grafo regular con${\displaystyle n}$aristas que tocan cada vértice.

El grafo hipercubo${\displaystyle Q_{n}}$También se puede construir creando un vértice para cada subconjunto de un${\displaystyle n}$conjunto de elementos, con dos vértices adyacentes cuando sus subconjuntos difieren en un solo elemento, o creando un vértice para cada uno${\displaystyle n}$Número binario de -dígitos , con dos vértices adyacentes cuando sus representaciones binarias difieren en un solo dígito. Es el${\displaystyle n}$Producto cartesiano -múltiple del grafo completo de dos vértices , y puede descomponerse en dos copias de${\displaystyle Q_{n-1}}$conectados entre sí por una perfecta correspondencia .

Los grafos hipercubo no deben confundirse con los grafos cúbicos , que son grafos que tienen exactamente tres aristas que tocan cada vértice. El único grafo hipercubo${\displaystyle Q_{n}}$ese es un gráfico cúbico es el gráfico cúbico${\displaystyle Q_{3}}$.

El grafo hipercubo${\displaystyle Q_{n}}$puede construirse a partir de la familia de subconjuntos de un conjunto con${\displaystyle n}$elementos, creando un vértice para cada subconjunto posible y uniendo dos vértices por una arista siempre que los subconjuntos correspondientes difieran en un solo elemento. De manera equivalente, se puede construir utilizando${\displaystyle 2^{n}}$vértices etiquetados con${\displaystyle n}$Números binarios de -bits y conectando dos vértices por una arista siempre que la distancia de Hamming de sus etiquetas sea uno. Estas dos construcciones están estrechamente relacionadas: un número binario puede interpretarse como un conjunto (el conjunto de posiciones donde tiene un dígito distinto de cero), y dos de dichos conjuntos difieren en un solo elemento siempre que los dos números binarios correspondientes tengan una distancia de Hamming de uno.

Alternativamente,${\displaystyle Q_{n}}$puede construirse a partir de la unión disjunta de dos hipercubos${\displaystyle Q_{n-1}}$, agregando una arista de cada vértice en una copia de${\displaystyle Q_{n-1}}$al vértice correspondiente en la otra copia, como se muestra en la figura. Las aristas de unión forman un emparejamiento perfecto .

La construcción anterior proporciona un algoritmo recursivo para construir la matriz de adyacencia de un hipercubo,${\displaystyle A_{n}}$La copia se realiza a través del producto Kronecker .${\displaystyle \otimes _{K}}$, de modo que las dos copias de${\displaystyle Q_{n-1}}$tener una matriz de adyacencia${\displaystyle \mathrm {1} _{2}\otimes _{K}A_ {n-1}}$,dónde${\displaystyle 1_{d}}$es el${\displaystyle d\times d}$matriz identidad . Mientras tanto, las aristas de unión tienen una matriz de adyacencia.${\displaystyle A_{1}\otimes _{K}1_{2^{n-1}}}$La suma de estos dos términos da como resultado una función recursiva para la matriz de adyacencia de un hipercubo:$${\displaystyle A_{n}={\begin{cases}1_{2}\otimes _{K}A_{n-1}+A_{1}\otimes _{K}1_{2^{n-1}}&{\text{si }}n>1\\{\begin{bmatrix}0&1\\1&0\end{bmatrix}}&{\text{si }}n=1\end{cases}}}$$ Otra construcción de${\displaystyle Q_{n}}$es el producto cartesiano de${\displaystyle n}$ grafos completos de dos vértices${\displaystyle K_{2}}$En términos más generales, el producto cartesiano de copias de un grafo completo se denomina grafo de Hamming ; los grafos hipercubos son ejemplos de grafos de Hamming.

El gráfico${\displaystyle Q_{0}}$consta de un solo vértice, mientras que${\displaystyle Q_{1}}$es el grafo completo en dos vértices.

${\displaystyle Q_{2}}$es un ciclo de longitud 4.

El gráfico${\displaystyle Q_{3}}$es el 1-esqueleto de un cubo y es un grafo planar con ocho vértices y doce aristas .

El gráfico${\displaystyle Q_{4}}$es el gráfico de Levi de la configuración de Möbius . También es el gráfico del caballo para un toroide.${\displaystyle 4\times 4}$tablero de ajedrez . ^{[ 1 ]}

El problema de encontrar el camino o ciclo más largo que sea un subgrafo inducido de un grafo hipercubo dado se conoce como el problema de la serpiente en la caja .

La conjetura de Szymanski se refiere a la idoneidad de un hipercubo como topología de red para comunicaciones. Afirma que, independientemente de cómo se elija una permutación que conecte cada vértice del hipercubo con otro vértice con el que deba conectarse, siempre existe una forma de conectar estos pares de vértices mediante caminos que no comparten ninguna arista dirigida. ^{[ 9 ]}

• Gráfico de De Bruijn
• Ciclos conectados por cubos
• cubo de Fibonacci
• Gráfico de cubo plegado
• Gráfico de Frankl-Rödl
• Gráfico de cubo dividido por la mitad
• Topología de interconexión de hipercubos
• Cubo parcial

• Harary, F .; Hayes, JP; Wu, H.-J. (1988), "Una revisión de la teoría de los grafos hipercubos", Computers & Mathematics with Applications , 15 (4): 277–289 , doi : 10.1016/0898-1221(88)90213-1 , hdl : 2027.42/27522.