En teoría de grafos , el grafo cúbico partido por la mitad o grafo de medio cubo de dimensión n es el grafo del semihipercubo , formado al conectar pares de vértices a una distancia exactamente dos entre sí en el grafo del hipercubo . Es decir, es el medio cuadrado del hipercubo. Este patrón de conectividad produce dos grafos isomorfos , desconectados entre sí, cada uno de los cuales es el grafo cúbico partido por la mitad.
La construcción del grafo cúbico dividido por la mitad se puede reformular en términos de números binarios . Los vértices de un hipercubo se pueden etiquetar con números binarios de tal manera que dos vértices sean adyacentes exactamente cuando difieren en un solo bit. El semicubo se puede construir 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 gráfico cúbico dividido por la mitad a partir de un gráfico hipercubo de dimensión inferior, sin tomar un subconjunto de los vértices:
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 cúbico partido por la mitad de dimensión cuatro se puede formar a partir de un cubo tridimensional ordinario manteniendo las aristas del cubo y agregando aristas que conecten pares de vértices que estén en esquinas opuestas de la misma cara cuadrada.
El grafo cúbico partido por la mitad de dimensión 3 es el grafo completo K 4 , el grafo del tetraedro . El grafo cúbico partido por la mitad de dimensión 4 es K 2,2,2,2 , el grafo del politopo regular de cuatro dimensiones , el de 16 celdas . El grafo cúbico partido por la mitad de dimensión cinco se conoce a veces como grafo de Clebsch y es el complemento del grafo cúbico plegado de dimensión cinco, que es el que se denomina más comúnmente grafo de Clebsch. Existe en el 5- politopo uniforme de cinco dimensiones , el 5-demicubo .
Debido a que es la mitad bipartita de un gráfico regular en cuanto a distancias , el gráfico cúbico dividido por la mitad es en sí mismo regular en cuanto a distancias. [3] Y debido a que contiene un hipercubo como subgráfico generador , hereda del hipercubo todas las propiedades de los gráficos monótonos, como la propiedad de contener un ciclo hamiltoniano .
Al igual que con los gráficos de hipercubos y sus subgráficos isométricos (que preservan la distancia) los cubos parciales , un gráfico cúbico reducido a la mitad puede ser incrustado isométricamente en un espacio vectorial real con la métrica de Manhattan ( función de distancia L 1 ). Lo mismo es cierto para los subgráficos isométricos de los gráficos cúbicos reducidos a la mitad, que pueden reconocerse en tiempo polinomial ; esto forma una subrutina clave para un algoritmo que prueba si un gráfico dado puede ser incrustado isométricamente en una métrica de Manhattan. [4]
Para cada grafo cúbico dividido por la mitad de dimensión cinco o más, es posible colorear (incorrectamente) los vértices con dos colores, de tal 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 que se muestran son proyecciones de polígonos de Petrie simétricos D n y B n ( simetría diedral 2( n − 1) y n ) del politopo relacionado que puede incluir bordes y vértices superpuestos.
