algorithm - saber - simetria de una grafica ejemplos

Eliminando la simetría de los gráficos.

Question

Tengo un problema algorítmico en el que he derivado una matriz de transferencia entre muchos estados. El siguiente paso es exponenciarlo, pero es muy grande, así que necesito hacer algunas reducciones al respecto. Concretamente contiene mucha simetría. A continuación se muestran algunos ejemplos de cuántos nodos pueden eliminarse mediante observaciones simples.

Mi pregunta es si existe un algoritmo para eliminar de manera eficiente la simetría en los dígrafos, de manera similar a como lo he hecho manualmente a continuación.

En todos los casos, el vector inicial tiene el mismo valor para todos los nodos.

En el primer ejemplo vemos que b , c , d y e todos reciben valores de a y uno del otro. Por lo tanto, siempre contendrán un valor idéntico, y podemos fusionarlos.

En este ejemplo, detectamos rápidamente que el gráfico es idéntico desde el punto de vista de a , b , c y d . También para sus respectivos sidenodes, no importa a qué nodo interno se adjunta. Por lo tanto, podemos reducir el gráfico a solo dos estados.

Actualización: Algunas personas eran suficientemente razonables y no estaban del todo seguras de lo que se entendía por "matriz de transferencia de estado". La idea aquí es que puede dividir un problema combinatorio en una serie de tipos de estado para cada n en su recurrencia. La matriz luego te dice cómo ir de n-1 a n .

Por lo general, solo le interesa el valor de uno de sus estados, pero también necesita calcular los otros para poder pasar al siguiente nivel. Sin embargo, en algunos casos, varios estados son simétricos, lo que significa que siempre tendrán el mismo valor. Obviamente, es un desperdicio calcular todos estos, por lo que queremos reducir el gráfico hasta que todos los nodos sean "únicos".

A continuación se muestra un ejemplo de la matriz de transferencia para el gráfico reducido en el ejemplo 1.

[S_a(n)]   [1  1  1] [S_a(n-1)]
[S_f(n)] = [1  0  0]*[S_f(n-1)]
[S_B(n)]   [4  0  1] [S_B(n-1)]

Cualquier sugerencia o referencias a los documentos son apreciados.

Answer 1

El trabajo de Brendan McKay ( http://cs.anu.edu.au/~bdm/nauty/ ) es la mejor herramienta que conozco para calcular automorfismos de gráficos. Puede ser demasiado costoso calcular todo el grupo de automorfismos de su gráfica, pero puede reutilizar algunos de los algoritmos descritos en el artículo de McKay "Practical Graph Isomorphism" (enlazado desde la página de nauty).

Answer 2

La computación de las simetrías parece ser un problema de segundo orden. Tomando solo a, b, cyd en su segundo gráfico, la simetría debería expresarse

a(b,c,d) = b(a,d,c)

y todas sus permutaciones, o algo así. Considere un segundo subgrafo a '', b'', c '', d'' agregado. Nuevamente, tenemos las simetrías, pero parametrizadas de manera diferente.

Para las personas informáticas (en lugar de las personas matemáticas), ¿podríamos expresar el problema así?

Cada nodo gráfico contiene un conjunto de letras. En cada iteración, todas las letras de cada nodo se copian a sus vecinos mediante las flechas (algunas flechas toman más de una iteración y pueden tratarse como una tubería de nodos anónimos).

Estamos tratando de encontrar formas eficientes de determinar cosas como * qué letras contiene cada conjunto / nodo después de N iteraciones. * para cada nodo, la N después de la cual su conjunto ya no cambia. * qué conjuntos de nodos terminan conteniendo los mismos conjuntos de letras (clase de equivalencia)

?

Answer 3

Solo agregaré una respuesta adicional a partir de lo que sugirió userOVER9000, si alguien más está interesado. El siguiente es un ejemplo del uso de nauty en el Ejemplo 2, a través de la herramienta dreadnaut .

$ ./dreadnaut 
Dreadnaut version 2.4 (64 bits).
> n=8 d g                                     -- Starting a new 8-node digraph
 0 : 1 3 4;                                   -- Entering edge data
 1 : 0 2 5;
 2 : 3 1 6;
 3 : 0 2 7;
 4 : 0;
 5 : 1;
 6 : 2;
 7 : 3;
> cx                                          -- Calling nauty
(1 3)(5 7)
level 2:  6 orbits; 5 fixed; index 2
(0 1)(2 3)(4 5)(6 7)
level 1:  2 orbits; 4 fixed; index 4
2 orbits; grpsize=8; 2 gens; 6 nodes; maxlev=3
tctotal=8; canupdates=1; cpu time = 0.00 seconds
> o                                           -- Output "orbits"
 0:3; 4:7;

Note que sugiere unir nodos 0:3 que son a:d en el Ejemplo 2 y 4:7 que son e:h .

El algoritmo de trabajo no está bien documentado, pero los autores lo describen como el peor caso exponencial, n^2 promedio.