Gráfico de cubo dividido por la mitad

En teoría de grafos , el grafo de cubo dividido o medio cubo de dimensión n es el grafo de vértices y aristas del demihipercubo , formado al conectar pares de vértices a una distancia exacta de dos entre sí en el grafo del hipercubo . Es decir, es la mitad del cuadrado del hipercubo. Este patrón de conectividad produce dos grafos isomorfos , desconectados entre sí, cada uno de los cuales es el grafo de cubo dividido.

La construcción del grafo del cubo dividido por la mitad puede reformularse en términos de números binarios . Los vértices de un hipercubo pueden etiquetarse con números binarios de tal manera que dos vértices sean adyacentes exactamente cuando difieren en un solo bit. El demicubo puede construirse a partir del hipercubo como la envoltura convexa del subconjunto de números binarios con un número par de bits distintos de cero (los números malvados ), y sus aristas conectan pares de números cuya distancia de Hamming es exactamente dos. ^{[ 2 ]}

También es posible construir el grafo del cubo dividido por la mitad a partir de un grafo de hipercubo de menor dimensión, sin tomar un subconjunto de los vértices:

${\displaystyle {\frac {1}{2}}Q_{n}=Q_{n-1}^{2}}$

donde el superíndice 2 denota el cuadrado del grafo hipercubo Q _{n  − 1} , el grafo formado al conectar pares de vértices cuya distancia es como máximo dos en el grafo original. Por ejemplo, el grafo de cubo dividido por la mitad de dimensión cuatro puede formarse a partir de un cubo tridimensional ordinario conservando las aristas del cubo y añadiendo aristas que conectan pares de vértices que se encuentran en esquinas opuestas de la misma cara cuadrada.

El grafo del cubo dividido de dimensión 3 es el grafo completo K ₄ , el grafo del tetraedro . El grafo del cubo dividido de dimensión 4 es K _2,2,2,2 , el grafo del politopo regular de cuatro dimensiones , el 16-celda . El grafo del cubo dividido de dimensión cinco se conoce a veces como el grafo de Clebsch , y es el complemento del grafo del cubo plegado de dimensión cinco, que es el que más comúnmente se llama grafo de Clebsch. Existe en el 5-politopo uniforme de 5 dimensiones , el 5-demicube . ${\displaystyle {\tfrac {1}{2}}Q_{3}}$${\displaystyle {\tfrac {1}{2}}Q_{4}}$${\displaystyle {\tfrac {1}{2}}Q_{5}}$

Debido a que es la mitad bipartita de un grafo distancia-regular , el grafo del cubo dividido por la mitad es en sí mismo distancia-regular. ^{[ 3 ]} Y debido a que contiene un hipercubo como subgrafo generador , hereda del hipercubo todas las propiedades monótonas de los grafos, como la propiedad de contener un ciclo hamiltoniano .

Al igual que con los grafos hipercubos y sus subgrafos isométricos (que preservan la distancia), los _cubos parciales , un grafo de cubo dividido por la mitad puede incrustarse isométricamente en un espacio vectorial real con la métrica de Manhattan ( función de distancia L1 ). Lo mismo ocurre con los subgrafos isométricos de los grafos de cubo dividido por la mitad, que pueden reconocerse en tiempo polinomial ; esto constituye una subrutina clave para un algoritmo que comprueba si un grafo dado puede incrustarse isométricamente en una métrica de Manhattan. ^{[ 4 ]}

Para cada grafo de cubo dividido por la mitad de dimensión cinco o más, es posible colorear (de forma incorrecta) los vértices con dos colores, de manera que el grafo coloreado resultante no tenga simetrías no triviales. Para los grafos de dimensión tres y cuatro, se necesitan cuatro colores para eliminar todas las simetrías. ^{[ 5 ]}

Los dos gráficos mostrados son proyecciones simétricas de polígonos de Petrie D _n y B _n ( simetría diedral 2( n  − 1) y n ) del politopo relacionado que puede incluir aristas y vértices superpuestos.

• Weisstein, Eric W. "Grafo de cubo dividido por la mitad" . MathWorld .