Grafo hipercubo

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda
Grafo hipercubo Qn
Hypercubestar.svg
El grafo hipercubo Q4
Nombre en honor a Hipercubo
Vértices 2n
Aristas 2n-1n
Diámetro n
Cintura (girth) 4, si n≥2
Número cromático 2
Propiedades Simétrico
Distancia regular
Distancia unitaria
Camino hamiltoniano
[editar datos en Wikidata]

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.

Ejemplos[editar]

El grafo Q0 consiste en un único vértice, mientras que Q1 es el grafo completo de dos vértices y Q2 un ciclo de largo 4.

El grafo Q3 es el 1-esqueleto de un cubo, un grafo planar con 8 vértices y 12 aristas.

El grafo Q4 es el grafo de Levi de una configuración de Möbius.

Referencias[editar]

  • Harary, F.; Hayes, J. P.; Wu, H.J. (1988) (en inglés), A survey of the theory of hypercube graphs, 15, pp. 277–289, doi:10.1016/0898-1221(88)90213-1