La enumeración de los Gráficos con la Auto-Loops

Question

Brendan McKay ya ha hecho el trabajo para encontrar todos los no-isomorfo gráficos de n variables que se pueden encontrar aquí (en Gráficas Simples): http://cs.anu.edu.au/~bdm/data/graphs.html

Creo que esto era de hecho el uso de polya enumeración, que tengo entendido los conceptos básicos de. Me gustaría ampliar en esto, y permitir la auto bucles en estos gráficos. Así que, me gustaría encontrar todos los no-ismorphic gráficos de n variables, incluyendo el auto de bucles. Este se utiliza directamente para la otra parte de mi código y proporcionar una enorme optimización. No estoy muy seguro de cómo ir sobre ella.

Para ser claros, Brendan Mckay los archivos de dar a todos los que no ismorphic gráficos, es decir, en el borde de la notación,

1-2 1-3

es un gráfico con una arista entre los vértices 1 y 2, y 1 y 3. Quiero que esta lista para incluir también la auto bucles, es decir:

1-1 1-2 1-3

o

1-2 1-3 1-1 2-2

Quiero el número mínimo de gráficos, por lo que todos los no-ismorphic. Cómo se puede ir sobre la búsqueda de ellos, esperemos que el uso de los datos Brendan McKay tiene disponibles para gráficas simples?

Answer 1

Este hecho puede ser hecho con el Polya Enumeración Teorema. Hay una manera muy simple pero potente observación que se puede hacer aquí: si tenemos el ciclo de índice del borde de permutación grupo inducidos por la acción del grupo simétrico en los vértices, el ciclo del índice del borde de permutación grupo incluyendo la auto-bucles pueden obtenerse multiplicando el factorizations en ciclos disjuntos del borde de la permutación y la original vértice de permutación y la suma de estas contribuciones para todos los vértices de permutaciones. (Por supuesto, trabajamos directamente con el ciclo de índice del grupo simétrico que es mucho más eficiente que itera sobre todas las permutaciones.) Pero el ciclo del índice del borde de permutación grupo no es difícil de calcular, el código se puede encontrar en este MSE Enlace.

Esto da el siguiente ciclo de índices para la enumeración de gráficos que puede tener la auto-bucles: for $n=2$ hemos $$1/2\,{a_{{1}}}^{3}+1/2\,a_{{1}}a_{{2}},$$ para $n=3$ tenemos $$1/6\,{a_{{1}}}^{6}+1/2\,{a_{{1}}}^{2}{a_{{2}}}^{2}+1/3\,{a_{{3}}}^{2},$$ y finalmente, para $n=4$ obtenemos $$1/24\,{a_{{1}}}^{10}+1/4\,{a_{{1}}}^{4}{a_{{2}}}^{3}+1/3\,{a_{{3}}}^{3}a_{{1}}+1 /8\,{a_{{1}}}^{2}{a_{{2}}}^{4}+1/4\,a_{{2}}{a_{{4}}}^{2}.$$

Como ejemplo, podemos sustituir $1+z$ en el ciclo índice de $n=3$ para obtener $${z}^{6}+2\,{z}^{5}+4\,{z}^{4}+6\,{z}^{3}+4\,{z}^{2}+2\,z+1.$$ De hecho hay dos gráficos en tres vértices con $1$ borde incluidos los bucles, es decir, de un solo filo o un solo bucle. De la misma manera hay cuatro gráficos con $2$ bordes, es decir, dos bucles, de dos filos, de un borde con un bucle en un extremo y un borde que se opone a un vértice con un bucle. Además de los seis gráficos con tres aristas son: un triángulo sin bucles, un tenedor con un lazo en el mango de un tenedor con un lazo en uno de sus extremos, un segmento de línea con dos bucles en los extremos de un segmento de línea con un bucle en un extremo y un bucle que no incide sobre el segmento de línea, y por último, tres bucles. Se va como esta.

Estos ciclo de índices de producir los siguientes recuentos totales de la no-grafo isomorfo gráficos con la posible auto-bucles presente:

1
6
20
90
544
5096
79264
2208612
113743760
10926227136
1956363435360
652335084592096
405402273420996800
470568642161119963904
1023063423471189431054720
4178849203082023236058229792
32168008290073542372004082199424
468053896898117580623237189908861696
12908865186281154904787051023018388368640
676599895346467962508983189158040730734206464
67557268911383303274368343026941404659790140175872
12878644470123443279570180725329554086442149175832124416
4696891990987444795146988875290693218960182452250871238964224
3283275444870880220030739747435965751837707129958501790119044590592
4406671511641658245922265014648856899986657018190959680004287879813376000
11374011362523188765310166602160674880959112891073505609667787021125321629659136

Esta secuencia de valores de puntos que nos OEIS A000666 donde una gran cantidad de material adicional se puede encontrar.

Para aquellos que son curiosos para ver los detalles, aquí está el Arce código para calcular estos valores:

con(numtheory);
con(grupo):
con(planta):

pet_cycleind_vrec := 
proc(n)
 local p, s;
 opción de recordar;

 si n=0 entonces devolver 1; fi;

 ampliar(1/n*añadir(a[l]*pet_cycleind_vrec(n-l), l=1..n));
end;

pet_flatten_term :=
proc(varp)
 local terml, d, cf, v;

 terml := [];

 cf := varp;
 para v en indets(varp) ¿
 d := grado(varp, v);
 terml := [op(terml), seq(v, k=1..d)];
 cf := cf/v^d;
od;

 [cf, terml];
end;


pet_cycleind_edg := 
proc(n)
 opción de recordar;
 local de s, t, res, cycs, l1, l2, planos, u, v;

 si n=0 entonces devolver 1; fi;

 s := 0:
 para t en pet_cycleind_vrec(n) hacer
 plano := pet_flatten_term(t);

 cycs := plano[2]; res := 1;

 para u nops(cycs) ¿
 para v de u+1 a nops(cycs) ¿
 l1 := op(1, cycs[u]); l2 := op(1, cycs[v]);
 res := res * [lcm(l1, l2)]^(l1*l2/lcm(l1, l2));
od;
od;

 para u nops(cycs) ¿
 l1 := op(1, cycs[u]);
 si el tipo(l1, impar), entonces
 # [l1]^(1/2*l1*(l1-1)/l1);
 res := res*[l1]^(1/2*(l1-1));
otra cosa
 # [l1/2]^(l1/2/(l1/2))*[l1]^(1/2*l1*(l1-2)/l1)
 res := res*[l1/2]*[l1]^(1/2*(l1-2)); 
fi;
od;

 s := s + res*t;
od;

s;
end;

pet_varinto_cind :=
proc(poli, ind)
 local subs1, subs2, polyvars, indvars, v, bote, res;

 res := ind;

 polyvars := indets(poli);
 indvars := indets(ind);

 para v en indvars ¿
 bote := op(1, v);

 subs1 := 
 [seq(polyvars[k]=polyvars[k]^olla, 
k=1..nops(polyvars))];

 subs2 := [v=subs(subs1, poli)];

 res := subs(subs2, res);
od;

res;
end;

v :=
proc(n)
 opción de recordar;
 local p, k, gf;

 p := q1+q2;
 gf := expand(pet_varinto_cind(p, pet_cycleind_edg(n)));

 subs({t1=1, t2=1}, gf);
end;

Answer 2

La rápida y desordenada método sería añadir la auto-bucles en todas las formas posibles para cada gráfico, y comprobar cuáles de ellos son isomorfos.

Una forma más sofisticada primero calcular el automorphism grupo de la gráfica, y usar esa información para resolver su problema. Que puede ahorrar un montón de tiempo, ya que para la mayoría de los gráficos, la automorphism grupo es trivial.

McKay de la biblioteca puede comprobar si dos grafos son isomorfos, y creo que también calcula el automorphism grupo (al menos en algún sentido). Al menos, usted debería ser capaz de usar la rápida y desordenada método sólo para los gráficos no triviales automorphism grupo.