Etiquetado los nodos de un hipercubo

Question

Estoy tratando de averiguar de cuántas maneras puedo etiquetar los nodos de un hipercubo de dimensión n. Los nodos de un hipercubo de dimensión n pueden etiquetarse de 0 a (2 ^ n - 1) de tal manera que existe una arista entre cualquier dos vértices si y sólo si las representaciones binarias de sus etiquetas difieren en uno y sólo un poco.

Parece que hay muchas maneras de etiquetar tal un hipercubo, pero estoy teniendo un momento difícil formularlo.

Le agradeceria su ayuda.

Answer 1

Considere la posibilidad de un hipercubo canónicamente incrustado en $\mathbb R^n$, de tal manera que, en particular, los vértices tienen coordenadas en $\{0,1\}^n$ y que los bordes estén alineados con los ejes de coordenadas. Cada una de las coordenadas de cada vértice puede ser entonces, naturalmente, representado por un solo bit, y dos vértices están conectados por una arista si y sólo si sus coordenadas diferentes a lo largo de un solo eje.

Hay $n!$ formas de asignar el $n$ ejes de coordenadas para los bits de un $n$-cadena de bits. Además, para cada uno de los bits, no hay una opción de dos complementarios de representaciones (correspondiente a la creación de reflejo de la hipercubo a lo largo del eje), para un total de $2^n$ opciones. Por lo tanto, tenemos (al menos) $n! \cdot 2^n$ distintas formas de asignar los vértices de un $n$-hipercubo en $n$-bit bitstrings tal que los vértices adyacentes mapa de cadenas que difieren en un bit.

Mostrando que estos, de hecho, constituyen todas esas asignaciones es un poco más difícil, pero en realidad, yo sólo quería señalar que este método de la enumeración de las asignaciones por causa de su buena interpretación geométrica.

Un enfoque es integrar el hipercubo en $\mathbb R^n$ de manera tal que los vértices de la mentira en $\{-1,1\}^n$, y tenga en cuenta que las simetrías de la hipercubo puede ser representado por $n \times n$ firmado permutación de matrices, que forman el hyperoctahedral grupo de orden $n! \cdot 2^n$.

Answer 2

En un hipercubo n-dimensional hay 2 ^ números nodos con números vecinos. Para los primeros 2 ^ n cadenas de bits, cada nodo tiene números vecinos. Por lo que necesitará mostrar que determinan los mismos gráficos, de lo contrario la respuesta es 0.

Después de eso, puede etiquetar el primer vertice en 2 ^ formas números que tiene n-doble la simetría alrededor de cada punto, tan total $n!2^n$ marcajes.

Mira aquí las referencias: http://oeis.org/A000165