Grafo hipercubo
| Grafo hipercubo Qn | ||
|---|---|---|
 El grafo hipercubo Q4 | ||
| Nombre en honor a | Hipercubo | |
| Vértices | 2n | |
| Aristas | 2n-1n | |
| Diámetro | n | |
| Cintura | 4, si n≥2 | |
| Número cromático | 2 | |
| Propiedades |
Simétrico Distancia regular Distancia unitaria Camino hamiltoniano | |
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
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.
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.
