Supongamos que tenemos una gráfica como esta
y una lista de sus automorfismos. ¿Cómo puedo obtener un conjunto de generadores para este grupo?
Respuesta
¿Demasiados anuncios?
A través de algoritmos, se tienen los elementos uno por uno y usarlos para crecer en un subgrupo. Crear una fuerte generación de sistemas de modo que el tamaño del subgrupo es conocido, y a fin de que la membresía en el subgrupo puede probarse fácilmente. Sólo grabar un nuevo generador cuando se obtiene un elemento no en el actual subgrupo. Usted puede parar temprano si usted nota que el subgrupo y la lista tienen el mismo tamaño (siempre y cuando usted confía en la lista es la correcta).
GAP ofrece un comando AsGroup para convertir una lista de los elementos del grupo en un grupo (que luego pueden ser preguntado por pequeños grupos electrógenos). De hecho, en este ejemplo, es bastante encuentra automáticamente un buen set de generación de energía.
Ya que la lista no es demasiado largo, se puede utilizar:
g := AsGroup( List( myListOfImages, PermList ) );
Esto tiene algunos problemas de rendimiento si la lista había más como 10.000 elementos, pero para los pequeños grupos como este que es instantáneo. El resultado es:
Group([ (3,6)(5,7)(8,10), (2,5)(3,4)(7,10)(8,9), (1,2)(3,5)(6,7)(8,10) ])
Si te gusta la imagen formato de lista de permutaciones:
gap> PrintArray( List( GeneratorsOfGroup(g), ListPerm ) );
[ [ 1, 2, 6, 4, 7, 3, 5, 10, 9, 8 ],
[ 1, 5, 4, 3, 2, 6, 10, 9, 8, 7 ],
[ 2, 1, 5, 4, 3, 7, 6, 10, 9, 8 ] ]
Usted también puede pedir GAP (y uva) directamente:
LoadPackage("grape");
Petersen := Graph( SymmetricGroup(5), [[1,2]], OnSets, function(x,y) return Intersection(x,y)=[]; end );;
AutomorphismGroup(Petersen);
Los vértices están en un orden diferente que el tuyo, pero por lo demás todo está bien.
