En teoría de grafos , el grafo hipercubo Q n es el grafo formado a partir de los vértices y las aristas de un hipercubo n -dimensional . Por ejemplo, el grafo cúbico Q 3 es el grafo 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 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 3 .
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 n 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.
Alternativamente, Q n puede construirse 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. 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:
Otra construcción de Q n es el producto cartesiano de n grafos completos de dos vértices K 2 . 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 grafo Q 0 consta de un solo vértice, mientras que Q 1 es el grafo completo en dos vértices.
Q 2 es un ciclo de longitud 4 .
El grafo Q 3 es el 1-esqueleto de un cubo y es un grafo plano con ocho vértices y doce aristas .
El grafo Q 4 es el grafo de Levi de la configuración de Möbius . También es el grafo del caballo para un tablero de ajedrez toroidal . [1]
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 ):
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]
