grafo hipercubo

En teoría de grafos, el grafo hipercubo Qn es un grafo regular con 2n vértices, que corresponden a los subconjuntos de un conjunto de n elementos. Dos vértices etiquetados por subconjuntos W y B están unidos por una arista si y sólo si W puede ser obtenido desde B añadiéndosele o quitándosele a este último un único elemento. Cada vértice de Qn es incidente a exactamente n aristas (por lo tanto, el grafo es n-regular) y por eso el número total de aristas es 2n-1n. El nombre proviene del hecho de que un grafo hipercubo es un esqueleto unidimensional de un hipercubo geométrico. Estos grafos no deberían confundirse con los grafos cúbicos, que son grafos 3-regulares. El único hipercubo que es cúbico es Q3.