En la teoría de grafos , el gráfico de cubo reducido a la mitad o el gráfico de medio cubo de dimensión n es el gráfico del demihipercubo , formado al conectar pares de vértices a una distancia exactamente dos entre sí en el gráfico de hipercubo . Es decir, es el medio cuadrado del hipercubo. Este patrón de conectividad produce dos gráficos isomórficos, desconectados entre sí, cada uno de los cuales es el gráfico de cubo reducido a la mitad.
Gráfico de cubo reducido a la mitad | |
---|---|
![]() El gráfico de cubo reducido a la mitad 1 2 Q 3 {\ displaystyle {\ tfrac {1} {2}} Q_ {3}} | |
Vértices | 2 n-1 |
Bordes | n ( n -1) 2 n -3 |
Automorfismos | n ! 2 n-1 , para n > 4 n ! 2 n , para n = 4 (2 n -1 ) !, para n <4 [1] |
Propiedades | Distancia simétrica regular |
Notación | |
Tabla de gráficos y parámetros |
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/e/ed/CubeAndStel.svg/220px-CubeAndStel.svg.png)
Construcciones equivalentes
La construcción del gráfico de cubo reducido a la mitad se puede reformular 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 difieran en un solo bit. El semicubo se puede construir a partir del hipercubo como el casco convexo del subconjunto de números binarios con un número par de bits distintos de cero (los números malignos ), y sus bordes conectan pares de números cuya distancia de Hamming es exactamente dos. [2]
También es posible construir el gráfico de cubo reducido a la mitad a partir de un gráfico de hipercubo de menor dimensión, sin tomar un subconjunto de los vértices:
donde el superíndice 2 denota el cuadrado del hipercubo gráfico Q n - 1 , el gráfico formado al conectar pares de vértices cuya distancia es como máximo dos en el gráfico original. Por ejemplo, el gráfico de cubo reducido a la mitad de dimensión cuatro puede formarse a partir de un cubo tridimensional ordinario manteniendo los bordes del cubo y agregando bordes que conectan pares de vértices que están en esquinas opuestas de la misma cara cuadrada.
Ejemplos de
El gráfico de cubo reducido a la mitad de dimensión 3 es el gráfico completo K 4 , el gráfico del tetraedro . El gráfico de cubo reducido a la mitadde dimensión 4 es K 2,2,2,2 , el gráfico del politopo regular de cuatro dimensiones , el de 16 celdas . El gráfico de cubo reducido a la mitadde dimensión cinco a veces se conoce como gráfico de Clebsch , y es el complemento del gráfico de cubo plegado de dimensión cinco, que es el más comúnmente llamado gráfico de Clebsch. Existe en el 5 -politopo uniforme de 5 dimensiones , el 5-demicubo .
Propiedades
Debido a que es la mitad bipartita de un gráfico de distancia regular , el gráfico de cubo reducido a la mitad es en sí mismo una distancia regular. [3] Y debido a que contiene un hipercubo como un subgráfico que se extiende , 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 hipercubo, y sus subgráficos isométricos (que preservan la distancia) subgráficos de los cubos parciales , un gráfico de cubo reducido a la mitad se puede incrustar 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 gráficos de cubo divididos a la mitad, que pueden reconocerse en tiempo polinomial ; esto forma una subrutina clave para un algoritmo que prueba si un gráfico dado se puede incrustar isométricamente en una métrica de Manhattan. [4]
Por cada gráfico de cubo reducido a la mitad de dimensión cinco o más, es posible colorear (incorrectamente) los vértices con dos colores, de tal manera que el gráfico de color resultante no tenga simetrías no triviales. Para los gráficos de dimensión tres y cuatro, se necesitan cuatro colores para eliminar todas las simetrías. [5]
Secuencia
Los dos gráficos que se muestran son proyecciones de polígono de Petrie simétricas D n y B n ( simetría 2 ( n - 1) y n diedro ) del politopo relacionado que puede incluir bordes y vértices superpuestos.
norte | Politopo | Grafico | Vértices | Bordes |
---|---|---|---|---|
2 | Segmento de línea | ![]() | 2 | - |
3 | tetraedro | ![]() ![]() | 4 | 6 |
4 | 16 celdas | ![]() ![]() | 8 | 24 |
5 | 5-demicubo | ![]() ![]() | dieciséis | 80 |
6 | 6-demicubo | ![]() ![]() | 32 | 240 |
7 | 7-demicubo | ![]() ![]() | 64 | 672 |
8 | 8-demicubo | ![]() ![]() | 128 | 1792 |
9 | 9-demicubo | ![]() ![]() | 256 | 4608 |
10 | 10-demicubo | ![]() ![]() | 512 | 11520 |
Referencias
- ^ AE Brouwer , AM Cohen y A. Neumaier (1989), Gráficos regulares de distancia . Berlín, Nueva York: Springer-Verlag, pág. 265. ISBN 3-540-50619-5 , ISBN 0-387-50619-5
- ^ Indyk, Piotr ; Matoušek, Jiří (2010), " Embeddings de baja distorsión de espacios métricos finitos", en Goodman, Jacob E .; O'Rourke, Joseph (eds.), Manual de geometría discreta y computacional (2ª ed.), CRC Press, p. 179, ISBN 9781420035315.
- ^ Chihara, Laura; Stanton, Dennis (1986), "Esquemas de asociación y transformaciones cuadráticas para polinomios ortogonales", Gráficos y combinatorios , 2 (2): 101–112, doi : 10.1007 / BF01788084 , MR 0932118.
- ^ Deza, M .; Shpectorov, S. (1996), "Reconocimiento de los l 1 gráficos con complejidad O ( nm ), o fútbol en un hipercubo", European Journal of Combinatorics , 17 (2-3): 279-289, doi : 10.1006 / eujc.1996.0024 , MR 1379378.
- ^ Bogstad, Bill; Cowen, Lenore J. (2004), "El número distintivo del hipercubo", Matemáticas discretas , 283 (1-3): 29-35, doi : 10.1016 / j.disc.2003.11.018 , MR 2061481.
enlaces externos
- Weisstein, Eric W. "Gráfico de cubo a la mitad" . MathWorld .