Gráfico de hipercubo

En teoría de grafos , el hipercubo Q _n es el grafo formado a partir de los vértices y las aristas de un hipercubo n -dimensional . Por ejemplo, el cubo Q ₃ es el grafo formado por los 8 vértices y las 12 aristas de un cubo tridimensional. Q _n tiene 2 ⁿ vértices , 2 ^{n – 1} n aristas y es un grafo regular con n aristas que tocan cada vértice.

El grafo hipercubo Q _n también puede construirse creando un vértice para cada subconjunto de un conjunto de n elementos, con dos vértices adyacentes cuando sus subconjuntos difieren en un solo elemento, o creando un vértice para cada número binario de n dígitos , con dos vértices adyacentes cuando sus representaciones binarias difieren en un solo dígito. Es el producto cartesiano n -fold del grafo completo de dos vértices , y puede descomponerse en dos copias de Q _{n – 1} conectadas entre sí por una correspondencia perfecta .

Los grafos hipercubicos no deben confundirse con los grafos cúbicos , que son grafos que tienen exactamente tres aristas que tocan cada vértice. El único grafo hipercubico Q _n que es un grafo cúbico es el grafo cúbico Q ₃ .

El grafo hipercubo Q _n puede construirse a partir de la familia de subconjuntos de un conjunto con n elementos, haciendo 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, puede construirse utilizando 2 ⁿ vértices etiquetados con números binarios de n 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 1 ), y dos de estos conjuntos difieren en un solo elemento siempre que los dos números binarios correspondientes tengan una distancia de Hamming de uno.

Como alternativa, Q _n puede construirse a partir de la unión disjunta de dos hipercubos Q _{n − 1} , añadiendo una arista de cada vértice de una copia de Q _{n − 1} al vértice correspondiente de la otra copia, como se muestra en la figura. Las aristas que se unen forman una correspondencia perfecta .

La construcción anterior proporciona un algoritmo recursivo para construir la matriz de adyacencia de un hipercubo, A _n . La copia se realiza a través del producto de Kronecker , de modo que las dos copias de Q _{n − 1} tienen una matriz de adyacencia , donde es la matriz identidad en dimensiones. Mientras tanto, los bordes de unión tienen una matriz de adyacencia . La suma de estos dos términos proporciona una función recursiva para la matriz de adyacencia de un hipercubo:${\displaystyle \mathrm {1} _{2}\otimes _{K}A_{n-1}}$${\displaystyle 1_{d}}$${\estilo de visualización d}$${\displaystyle A_{1}\otimes_{K}1_{2^{n-1}}}$

${\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 Q _n es el producto cartesiano de n grafos completos de dos vértices K ₂ . De manera más general, el producto cartesiano de copias de un grafo completo se denomina grafo de Hamming ; los grafos de hipercubos son ejemplos de grafos de Hamming.

El gráfico Q ₀ consta de un solo vértice, mientras que Q ₁ es el gráfico completo en dos vértices.

Q ₂ es un ciclo de longitud  4 .

El grafo Q ₃ es el 1-esqueleto de un cubo y es un grafo plano con ocho vértices y doce aristas .

El grafo Q ₄ es el grafo de Levi de la configuración de Möbius . También es el grafo del caballo de un tablero de ajedrez toroidal . ^[1]${\displaystyle 4\times 4}$

Todo grafo hipercubico es bipartito : se puede colorear con solo dos colores. Los dos colores de esta coloración se pueden encontrar a partir de la construcción de subconjuntos de grafos hipercubicos, dando un color a los subconjuntos que tienen un número par de elementos y el otro color a los subconjuntos con un número impar de elementos.

Todo hipercubo Q _n con n  > 1 tiene un ciclo hamiltoniano , un ciclo que visita cada vértice exactamente una vez. Además, existe un camino hamiltoniano entre dos vértices u y v si y solo si tienen colores diferentes en una coloración 2 del grafo. Ambos hechos son fáciles de demostrar utilizando el principio de inducción sobre la dimensión del hipercubo y la construcción del grafo del hipercubo uniendo dos hipercubos más pequeños con un correspondiente.

La hamiltonicidad del hipercubo está estrechamente relacionada con la teoría de los códigos de Gray . Más precisamente, existe una correspondencia biyectiva entre el conjunto de códigos de Gray cíclicos de n bits y el conjunto de ciclos hamiltonianos en el hipercubo Q _n . ^[2] Una propiedad análoga se cumple para los códigos de Gray acíclicos de n bits y los caminos hamiltonianos.

Un hecho menos conocido es que cada coincidencia perfecta en el hipercubo se extiende a un ciclo hamiltoniano. ^[3] La cuestión de si cada coincidencia se extiende a un ciclo hamiltoniano sigue siendo un problema abierto. ^[4]

El gráfico del hipercubo Q _n (para n > 1 ):

• es el diagrama de Hasse de un álgebra booleana finita .
• es un grafo mediano . Todo grafo mediano es un subgrafo isométrico de un hipercubo y puede formarse como una retracción de un hipercubo.
• tiene más de 2 ^{n -2} coincidencias perfectas. (esta es otra consecuencia que se sigue fácilmente de la construcción inductiva).
• es transitiva en arco y simétrica . Las simetrías de los gráficos de hipercubos se pueden representar como permutaciones con signo .
• contiene todos los ciclos de longitud 4, 6, ..., 2 ⁿ y por tanto es un gráfico bipancíclico .
• se puede dibujar como un gráfico de distancia unitaria en el plano euclidiano utilizando la construcción del gráfico de hipercubo a partir de subconjuntos de un conjunto de n elementos, eligiendo un vector unitario distinto para cada elemento del conjunto y colocando el vértice correspondiente al conjunto S en la suma de los vectores en S.
• es un grafo conexo por n vértices , según el teorema de Balinski .
• es planar (se puede dibujar sin cruces) si y solo si n ≤ 3 . Para valores mayores de n , el hipercubo tiene género ( n − 4)2 ^{n − 3} + 1 . ^{[5] [6]}
• tiene árboles de expansión exactamente iguales . ^[6]${\displaystyle 2^{2^{n}-n-1}\prod _{k=2}^{n}k^{n \choose k}}$
• tiene un ancho de banda exactamente . ^[7]${\displaystyle \sum _{i=0}^{n-1}{\binom {i}{\lfloor i/2\rfloor }}}$
• tiene un número acromático proporcional a , pero la constante de proporcionalidad no se conoce con precisión. ^[8]${\displaystyle {\sqrt {n2^{n}}}}$
• tiene como valores propios de su matriz de adyacencia los números (− n , − n + 2, − n + 4, ... , n − 4, n − 2, n ) y como valores propios de su matriz laplaciana los números (0, 2, ..., 2 n ) . El k -ésimo valor propio tiene multiplicidad en ambos casos.${\displaystyle {\binom {n}{k}}}$
• tiene número isoperimétrico h ( G ) = 1 .

La familia Q _n para todo n > 1 es una familia de grafos de Lévy .

El problema de encontrar el camino o ciclo más largo que es un subgrafo inducido de un grafo de 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 las comunicaciones. Establece que, independientemente de cómo se elija una permutación que conecte cada vértice del hipercubo con otro vértice con el que debería estar conectado, siempre hay una manera de conectar estos pares de vértices mediante caminos que no comparten ninguna arista dirigida. ^[9]

• gráfico de de Bruijn
• Ciclos cúbicos conexos
• Cubo de Fibonacci
• Gráfico cúbico plegado
• Gráfico de Frankl-Rödl
• Gráfico cúbico reducido a la mitad
• Topología de interconexión de redes de hipercubos
• Cubo parcial

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