En teoría de grafos , el gráfico de hipercubo Q n es el gráfico formado a partir de los vértices y aristas de un hipercubo de n dimensiones . Por ejemplo, el gráfico cúbico Q 3 es el gráfico formado por los 8 vértices y las 12 aristas de un cubo tridimensional.Q n tiene 2 n vértices , 2 n – 1 n aristas y es un gráfico regular con n aristas que tocan cada vértice.
El gráfico de hipercubo Q n también se puede construir 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 veces del gráfico completo de dos vértices y puede descomponerse en dos copias de Q n – 1 conectadas entre sí mediante una coincidencia perfecta .
Los gráficos de hipercubo no deben confundirse con los gráficos cúbicos , que son gráficos que tienen exactamente tres aristas tocando cada vértice. El único gráfico de hipercubo Q n que es un gráfico cúbico es el gráfico cúbico Q 3 .
El grafo de hipercubo Q n se puede construir 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, se puede construir utilizando 2 n vértices etiquetados con números binarios de n bits y conectando dos vértices mediante 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 ), y dos de esos conjuntos difieren en un solo elemento siempre que los dos números binarios correspondientes tengan una distancia de Hamming uno.
Alternativamente, Q n se puede construir a partir de la unión disjunta de dos hipercubos Q n − 1 , agregando una arista de cada vértice en una copia de Q n − 1 al vértice correspondiente en la otra copia, como se muestra en la figura. Los bordes de unión forman una combinación perfecta .
La construcción anterior proporciona un algoritmo recursivo para construir la matriz de adyacencia de un hipercubo, An . La copia se realiza mediante el producto de Kronecker , de modo que las dos copias de Q n − 1 tienen una matriz de adyacencia , donde está la matriz identidad en dimensiones. Mientras tanto, los bordes de unión tienen una matriz de adyacencia . La suma de estos dos términos da una función recursiva para la matriz de adyacencia de un hipercubo:
Otra construcción de Q n es el producto cartesiano de n gráficos completos de dos vértices K 2 . De manera más general, el producto cartesiano de copias de un gráfico completo se denomina gráfico de Hamming ; los gráficos de hipercubo son ejemplos de gráficos de Hamming.
El gráfico Q 0 consta de un solo vértice, mientras que Q 1 es el gráfico completo en dos vértices.
Q 2 es un ciclo de longitud 4 .
El gráfico Q 3 es el 1-esqueleto de un cubo y es un gráfico plano con ocho vértices y doce aristas .
El gráfico Q 4 es el gráfico de Levi de la configuración de Möbius . También es la gráfica del caballo para un tablero de ajedrez toroidal . [1]
Todo gráfico de hipercubo es bipartito : sólo se puede colorear con dos colores. Los dos colores de esta coloración se pueden encontrar a partir de la construcción de subconjuntos de gráficos de hipercubo, 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 bicolor del gráfico. Ambos hechos son fáciles de probar utilizando el principio de inducción sobre la dimensión del hipercubo y la construcción del gráfico del hipercubo uniendo dos hipercubos más pequeños con una coincidencia.
La hamiltonicidad del hipercubo está estrechamente relacionada con la teoría de los códigos Gray . Más precisamente , existe una correspondencia biyectiva entre el conjunto de códigos Gray cíclicos de n bits y el conjunto de ciclos hamiltonianos en el hipercubo Qn . [2] Una propiedad análoga se cumple para los códigos 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 de hipercubo Q n (para n > 1 ):
La familia Q n para todo n > 1 es una familia de gráficos de Lévy .
El problema de encontrar el camino o ciclo más largo que sea un subgrafo inducido de un gráfico de hipercubo determinado se conoce como 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. Afirma que, no importa 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 ningún borde dirigido. [9]
