Contando gráficos distintos no dirigidos y parcialmente etiquetados

Question

Supongamos que tengo un azulejo hexagonal. Cada borde puede ser conectado a cualquier subconjunto de los otros bordes (incluso ninguno). Las conexiones son espontáneos, por lo que a->b implica b->a, pero no son necesariamente transitivo - por ejemplo, a->b b->c no implica que a->c. El gráfico resultante de los bordes conectados no necesita estar conectado - no puede ser de varios distintos subdiagramas.

Por lo que puedo decir, este es un caso especial de contar grafo, etiquetados 6 vértice gráficos. Esto sería simple - hay $5+...+1=15$ posible de los bordes, de cada uno de los cuales puede estar presente o ausente, que conduce a $2^{15}$ posible gráficas.

Sin embargo, los azulejos son isomorfos con respecto a la rotación, y por encima de la fórmula de generar todos los diferentes rotación. El número de isomorfo gráficos varía con la simetría de la gráfica, así que no podemos simplemente divida el total por 6.

¿Cómo puedo calcular el número de los distintos gráficos para este problema?

Answer 1

No una inclusión-exclusión especie de método de trabajo aquí? Primero recuento de todos los etiquetados de los gráficos. Usted, a continuación, observe que tiene overcounted: por ejemplo, cada gráfico con simetría rotacional de orden 3 que se ha contado tres veces, cuando debería haber sido contada una vez, por lo que restar dos veces el número de gráficos con simetría rotacional 3 (que es fácil de calcular porque puede partición de los bordes en triples y cada triple o va completamente o no en todos). Pero al hacer esto, usted encuentra que usted ha restado demasiado. Por ejemplo, si una gráfica tiene simetría rotacional de orden 6, a continuación, también tiene simetría de rotación de orden 2 y 3, por lo que han restado un total de 1+2+5=8 en lugar de sólo 5. Por lo tanto, busque en pares de las propiedades de simetría y agregar de nuevo, y así sucesivamente.

No he comprobado que esto realmente hace el trabajo, pero se siente como la ordenación del territorio, donde la inclusión-exclusión.

Answer 2

Este es un trabajo para Burnside del lexema. Lo que estamos tratando de contar es órbitas de 6 vértices gráficos en virtud de una determinada acción de la 6-elemento cíclico grupo, que voy a denotar $Z_{6}$. Por Burnside del lema, este es igual al número promedio de puntos fijos de elementos de $Z_{6}$, así que en realidad sólo necesitamos contar los puntos fijos y, a continuación, hacer algo de aritmética.

Resulta que estos números de puntos fijos son en realidad bastante fácil de describir. $Z_{6}$ tiene un elemento de orden $1$, dos de orden $3$, dos de orden $6$, y uno de orden $2$. Consideramos orden por orden.

• Orden de 1: Todos los $2^{15}$ gráficos son fijados por la identidad.
• Orden de 2: Hay tres "diámetro" a los bordes, que se envían a sí mismos por la rotación de orden 2; los otros doce bordes son intercambiados en pares. Por lo tanto, hay nueve órbitas de los bordes bajo la acción de este elemento, y por lo tanto $2^{9}$ gráficos, que son fijados por éste.
• Orden de 3: Cada borde es parte de un triple de bordes definidos que son enviados a cada uno de los otros cíclicamente por cualquier rotación de orden tres. Por lo tanto, hay cinco de estas órbitas, por lo que hay $2^{5}$ gráficos fijado por dicho elemento.
• Orden de 6: Los diámetros mencionados anteriormente forman una órbita de longitud 3 bajo la acción de una rotación de orden 6; los bordes restantes forman dos órbitas de longitud 6. Por lo tanto, hay tres en total órbitas, y por lo tanto no se $2^{3}$ gráficos fijos por cada uno de estos elementos.

Ahora nos topamos con Burnside del lexema. Deje $N$ el número total de gráficos de hasta el $Z_{6}$-equivalencia; por el lema, tenemos

\[ N = \frac{1}{6} (2^{15} + 2^{9} + 2 \cdot 2^{5} + 2 \cdot 2^{3}) = 5560. \]

(Para hacer esto en más generalidad, te gustaría llevar en algunos algebraica de maquinaria pesada; una combinación de Pólya la teoría y la generación de funciones de la forma habitual ir).