31 mar 2026

Isomorfismos: tests

Introducción a las pruebas con grafos

*Figura*. Grafo MZ de 40 nodos y su comportamiento polinómico para distintos tamaños

Ya había comentado en temas anteriores que mi implementación del algoritmo getPartitionTree() para obtener el árbol de particiones y el etiquetado canónico se basa en los conceptos del algoritmo de McKay y ejemplos consultados en varios documentos de referencia. Pero la mejor forma de ir comprobando que la corrección de la implementación es disponer del algoritmo testIsomorphisms(), donde se trata de obtener el etiquetado canónico del grafo inicial y luego de un conjunto de permutaciones aleatorias verificando que en todas se obtiene el mismo etiquetado.

En este tema veremos como se comporta el algoritmo para algunas familias de grafos que se pueden obtener en la web nauty and Traces de McKay y Piperno, en la sección de Libraries of benchmark graphs. Y al mismo tiempo comprobar que su test de isomorfismos es correcto. En la Figura vemos el grafo Miyazaki MZ de 40 nodos, primero de la serie de tamaños hasta 1000 nodos, observando en la gráfica como evolucionan los los tiempos de ejecución. Pero antes veamos algunos conceptos preliminares.

Los grafos de ejemplo se descargan en archivo de texto en el formato DIMACS, que viene a ser una lista de aristas que podemos importar en la aplicación como se observa en la Figura.

p edge 40 60
e 1 3
e 1 8
e 1 9
e 2 4
e 2 7
e 2 10
e 3 8
e 3 10
e 4 7
e 4 9
e 5 9
e 5 10
e 5 15
e 6 7
e 6 8
e 6 16
e 11 18
e 11 19
e 11 21
e 12 17
e 12 20
e 12 22
e 13 18
e 13 20
e 13 23
e 14 17
e 14 19
e 14 24
e 15 19
e 15 20
e 16 17
e 16 18
e 21 28
e 21 29
e 22 27
e 22 30
e 23 28
e 23 30
e 24 27
e 24 29
e 25 29
e 25 30
e 25 35
e 26 27
e 26 28
e 26 36
e 31 33
e 31 38
e 31 39
e 32 34
e 32 37
e 32 40
e 33 38
e 33 40
e 34 37
e 34 39
e 35 39
e 35 40
e 36 37
e 36 38

Después de aplicar o aceptar esa lista de aristas usaremos el botón para importar el nuevo grafo cuyo aspecto visual podemos ver en la Figura, un grafo Miyazaki de 40 nodos y 60 aristas.

Una vez importado el grafo podemos ejecutar el algoritmo getPartitionTree() con las opciones que vemos en la Figura y que ya hemos explicado en temas anteriores. Según el tamaño y complejidad del grafo habrá que incremantar las máximas iteraciones así como el máximo tiempo de ejecución, pues por defecto se establece en 300 segundos momento en el que se abortará la ejecución.

A continuación vemos el resultado obtenido, observando que el tiempo de ejecución fue de 4 ms.

Time: 4 ms

Obtener árbol particiones (McKay): {
"useRefine":true,"orderRefine":"neighbors-desc-lengths-desc","targetCell":"max-length-first","typeCanon":"edges","useMcr":true,"useMcrPlus":false,"useMcrBreak":true,"typeIndicator":"lengths",
"timeTotal":4,"timeIni":0,"timeRef":3,
"iter":137,"refine":60,"indexTree":59,
"leaves":16,
"prunningMcr":44,"prunningMcrBreak":16,
"prunningIndicators":0,"prunningIndicators2":10,
"firstCanonicalPartition":[[0],[36],[38],[39],[37],[33],[31],[30],[32],[35],[34],[24],[25],[27],[26],[28],[29],[14],[20],[23],[21],[22],[18],[19],[11],[13],[12],[10],[17],[16],[1],[6],[15],[4],[3],[5],[9],[2],[7],[8]],
"firstCanon":false,
"canonicalPartition":[[16],[8],[9],[4],[27],[25],[35],[37],[36],[30],[31],[33],[32],[38],[39],[34],[0],[1],[3],[2],[20],[22],[24],[10],[12],[26],[14],[7],[6],[28],[29],[19],[18],[17],[21],[23],[5],[13],[11],[15]],
"firstCanonicalLabel":[[0,37],[0,38],[0,39],[1,5],[1,6],[1,9],[2,5],[2,7],[2,10],[3,6],[3,8],[3,10],[4,7],[4,8],[4,9],[5,6],[7,8],[9,12],[10,11],[11,15],[11,16],[12,13],[12,14],[13,18],[13,21],[14,19],[14,20],[15,18],[15,19],[16,20],[16,21],[17,22],[17,23],[17,33],[18,27],[19,25],[20,24],[21,26],[22,25],[22,27],[23,24],[23,26],[24,29],[25,29],[26,28],[27,28],[28,32],[29,32],[30,31],[30,34],[30,36],[31,34],[31,35],[32,35],[33,36],[33,39],[34,39],[35,38],[36,37],[37,38]],
"canonicalLabel":[[0,37],[0,38],[0,39],[1,3],[1,16],[1,18],[2,3],[2,17],[2,19],[3,26],[4,5],[4,20],[4,21],[5,6],[5,25],[6,7],[6,8],[7,9],[7,12],[8,10],[8,11],[9,12],[9,13],[10,11],[10,14],[11,13],[12,14],[13,15],[14,15],[15,22],[16,19],[16,27],[17,18],[17,28],[18,28],[19,27],[20,23],[20,29],[21,24],[21,30],[22,29],[22,30],[23,32],[23,33],[24,31],[24,33],[25,34],[25,35],[26,31],[26,32],[27,36],[28,36],[29,35],[30,34],[31,38],[32,37],[33,39],[34,38],[35,37],[36,39]],
"canonicalIndicator":[1,24,29,34,0],
"nodes":
[[[-1,[],[1]]],
[[0,[0],[1,21]],[0,[1],[1,21]],[0,[2],[1,21]],[0,[4],[1,16]],[0,[5],[1,16]],[0,[6],[1,18]],[0,[8],[1,18]],[0,[10],[1,18]],[0,[14],[1,16]],[0,[15],[1,16]],[0,[16],[1,24]],[0,[17],[1,24]],[0,[18],[1,24]],[0,[20],[1,18]],[0,[24],[1,16]],[0,[25],[1,16]],[0,[26],[1,24]]],
[[0,[0,36],[1,21,27]],[0,[0,37],[1,21,27]],[0,[0,38],[1,21,27]],[1,[1,36],[1,21,27]],[1,[1,38],[1,21,27]],[2,[2,36],[1,21,27]],[2,[2,38],[1,21,27]],[10,[16,30],[1,24,29]],[10,[16,31],[1,24,29]],[11,[17,30],[1,24,29]],[12,[18,30],[1,24,29]],[16,[26,0],[1,24,29]]],
[[0,[0,36,20],[1,21,27,37]],[0,[0,36,21],[1,21,27,37]],[0,[0,36,22],[1,21,27,37]],[1,[0,37,20],[1,21,27,37]],[2,[0,38,20],[1,21,27,37]],[3,[1,36,20],[1,21,27,37]],[4,[1,38,20],[1,21,27,37]],[5,[2,36,20],[1,21,27,37]],[6,[2,38,20],[1,21,27,37]],[7,[16,30,0],[1,24,29,34]],[8,[16,31,0],[1,24,29,34]],[9,[17,30,0],[1,24,29,34]],[10,[18,30,0],[1,24,29,34]],[11,[26,0,30],[1,24,29,34]]],
[[0,[0,36,20,38],[1,21,27,37,0]],[0,[0,36,20,39],[1,21,27,37,0]],[1,[0,36,21,38],[1,21,27,37,0]],[2,[0,36,22,38],[1,21,27,37,0]],[3,[0,37,20,38],[1,21,27,37,0]],[4,[0,38,20,36],[1,21,27,37,0]],[5,[1,36,20,38],[1,21,27,37,0]],[6,[1,38,20,36],[1,21,27,37,0]],[7,[2,36,20,38],[1,21,27,37,0]],[8,[2,38,20,36],[1,21,27,37,0]],[9,[16,30,0,20],[1,24,29,34,0]],[10,[16,31,0,20],[1,24,29,34,0]],[11,[17,30,0,21],[1,24,29,34,0]],[12,[18,30,0,21],[1,24,29,34,0]],[12,[18,30,0,22],[1,24,29,34,0]],[13,[26,0,30,10],[1,24,29,34,0]]]],
"nodeBest":[4,10],
"mcr":[0,4,5,6,8,10,14,15,16,18],
"fixMcr":
[[[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,34,35,36,37],[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,34,35,36,37,38]],
[[0,1,2,3,4,5,6,7,8,9,14,15,24,25,30,31,32,33,34,35,36,37,38,39],[0,1,2,3,4,5,6,7,8,9,10,12,14,15,16,18,20,22,24,25,26,28,30,31,32,33,34,35,36,37,38,39]],
[[0,1,2,3,4,5,6,7,8,9,14,15,16,17,24,25,26,27,30,31,32,33,34,35,36,37,38,39],[0,1,2,3,4,5,6,7,8,9,10,11,14,15,16,17,18,20,21,24,25,26,27,28,30,31,32,33,34,35,36,37,38,39]],
[[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,34,35,38,39],[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,34,35,36,38,39]],
[[4,5,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39],[0,2,4,5,6,8,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39]],
[[4,5,6,7,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39],[0,1,4,5,6,7,8,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39]],
[[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,34,35],[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,32,34,35,36,38]],
[[0,1,2,3,4,5,6,7,8,9,14,15,24,25,30,31,32,33,34,35,36,37,38,39],[0,1,2,3,4,5,6,7,8,9,10,12,14,15,16,18,20,22,24,25,26,28,30,31,32,33,34,35,36,37,38,39]],
[[],[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19]]],
"lastEqual":true,"rebuiltMcr":39,"nonRebuiltMcr":29,
"tree":null,
"automorphisms":9,
"automorphismsPlus":0}

Podemos ejecutar el test de isomorfismos con la mismas opciones como se observa en la Figura. Si ponemos 100 tests y tiempo total de 30 segundos entonces se construirán 100 permutaciones aleatorias del grafo inicial ejecutándose esos 100 tests o menos si se alcanzan los 30 segundos, llevándose a cabo en cualquier caso al menos 1 test siempre y cuando el algoritmo getPartitionTree() finalice antes del tiempo límite que por defecto se establece en 300 segundos.

Para el ejemplo anterior se obtienen los 100 isomórficos con 0 no isomórficos. Todos los tests de ejemplos de grafos que hemos visto en temas anteriores y los que veremos después resultaron satisfactoriamente isomórficos, no apareciendo ninguno no isomórfico. Esta utilidad me ha servido para revisar la corrección del algoritmo.

Observe que ahora el tiempo de ejecución es de "firstTime":3 ms cuando antes era de 4 ms. Hay que entender que los tiempos pueden variar entre ejecuciones, pero el resto de valores resultan invariables, como iteraciones ("iter1":137) o tamaño del árbol ("indexTree1":59) por ejemplo. Vea que se muestran también para la última permutación ("iter2":150, "indexTree2":60) así como para algunos valores el mínimo, máximo y promedio.

Time: 271 ms

Test isomorfismos (McKay): {"useRefine":true,"orderRefine":"neighbors-desc-lengths-desc","typeCanon":"edges","targetCell":"max-length-first","useMcr":true,"useMcrPlus":false,"useMcrBreak":true,"typeIndicator":"lengths",
"isomorphic":100,"nonIsomorphic":0,
"firstTime":3,"minTime":1,"averageTime":2,"maxTime":5,
"iter1":137,"iter2":150,
"indexTree1":59,"indexTree2":60,
"minIndexTree":37,"maxIndexTree":124,
"refine1":60,"refine2":61,
"numAut1":9,"numAut2":8,"numAutPlus1":0,"numAutPlus2":0,
"prunningMcr1":44,"prunningMcr2":52,"prunningMcrBreak1":16,"prunningMcrBreak2":19,
"rebuiltMcr1":39,"rebuiltMcr2":49,
"prunningIndicators1":0,"prunningIndicators2":0,
"prunningIndicators1b":10,"prunningIndicators2b":8,
"canonical":[[0,37],[0,38],[0,39],[1,3],[1,16],[1,18],[2,3],[2,17],[2,19],[3,26],[4,5],[4,20],[4,21],[5,6],[5,25],[6,7],[6,8],[7,9],[7,12],[8,10],[8,11],[9,12],[9,13],[10,11],[10,14],[11,13],[12,14],[13,15],[14,15],[15,22],[16,19],[16,27],[17,18],[17,28],[18,28],[19,27],[20,23],[20,29],[21,24],[21,30],[22,29],[22,30],[23,32],[23,33],[24,31],[24,33],[25,34],[25,35],[26,31],[26,32],[27,36],[28,36],[29,35],[30,34],[31,38],[32,37],[33,39],[34,38],[35,37],[36,39]]}

Pruebas con grafos con comportamiento polinómico y evolución uniforme

Tomamos los siguientes grafos de la web nauty and Traces en la sección de Libraries of benchmark graphs como hemos comentado. Ejecutaremos el árbol de particiones y test isomorfismos para obtener el tiempo de ejecución y comprobar que 100 tests aleatorios resultan satisfactorios (o los que puedan ejecutarse en 30 segundos). Como dijimos antes, resultan todos isomórficos.

Las ejecuciones se llevan a cabo con el navegador Chrome 146 bajo Windows 10 con Intel(R) Core(TM) i7-4770 CPU 3.40GHz y 8.00 GB RAM.

En la Figura vemos la familia de grafos Miyazaki (MZ) para ejemplares desde 40 nodos y 60 aristas hasta 1000 nodos y 1500 aristas, gráfica que puede importar en la aplicación Gráficas matemáticas usando la configuración del archivo graphic-mz.txt

Los valores en el eje vertical son los tiempos de ejecución en milisegundos en escala logarítmica, así que los valores 1, 2, 3, 4, ... se corresponde con 10 ms, 100 ms, 1000 ms, 10000 ms, ...

La gráfica en color gris es una estimación de la tendencia polinómica, donde ajustamos con unas constantes y = x³/70000 + x²/700 para valores en milisegundos, con el valor logarítmico en el eje vertical log₁₀ y. Agrupamos en este apartado los grafos cuyos resultados más se ajustan a esta línea de tendencia polinómica y que denominamos con evolución uniforme.

Observe que el algoritmo trata de evitar un comportamiento exponencial para obtener el etiquetado canónico, algo que ya habíamos comentado en el tema sobre refinamiento. Los comportamientos exponenciales en gráficas logarítmicas se corresponden con líneas rectas con valores por encima de las polinómicas. Por ejemplo, en la Figura vemos las funciones y = x², y = x³, y = 2^x e y = 10^x en representación logarítmica, observando que las dos últimas exponenciales vienen a ser rectas en esa representación, muy por encima de las polinómicas.

A excepción de algunos con comportamiento exponencial que veremos en otro apartado, la mayoría tienen tendencia polinómica. Aunque en cuanto a rendimiento están por debajo de las últimas versiones de aplicaciones mucho más eficientes como Nauty, Bliss o Conauto. Supongo que la ejecución de mi algoritmo con JavaScript en un navegador es una de las causas. Pero también es seguro que esa implementación puede mejorarse.

En cada prueba usamos las mismas opciones para todos los ejemplares desde cada familia de grafos. Así para este MZ estas son las opciones de ejecución, observando que se aplican podas con automorfismos ("useMcr":true) y con indicadores ("typeIndicator":"lengths).

"useRefine":true,
"orderRefine":"neighbors-desc-lengths-desc",
"targetCell":"max-length-first",
"typeCanon":"edges",
"useMcr":true,
"useMcrPlus":false,
"useMcrBreak":true,
"typeIndicator":"lengths"

En la Figura vemos la familia de grafos Miyazaki augmented (MZ-AUG) para ejemplares desde 40 nodos y 92 aristas hasta 1000 nodos y 2300 aristas, gráfica que puede importar en la aplicación Gráficas matemáticas usando la configuración del archivo graphic-mz-aug.txt

Se aplican podas con automorfismos ("useMcr":true) y con indicadores ("typeIndicator":"lengths).

"useRefine":true,
"orderRefine":"neighbors-desc-lengths-desc",
"targetCell":"min-length-first",
"typeCanon":"edges",
"useMcr":true,
"useMcrPlus":false,
"useMcrBreak":true,
"typeIndicator":"lengths"

En la Figura vemos la familia de grafos Miyazaki augmented 2 (MZ-AUG-2) para ejemplares desde 96 nodos y 152 aristas hasta 1200 nodos y 1900 aristas, gráfica que puede importar en la aplicación Gráficas matemáticas usando la configuración del archivo graphic-mz-aug-2.txt

Se aplican podas con automorfismos ("useMcr":true) pero no con indicadores ("typeIndicator":"none") pues no se producen con este grafo.

"useRefine":true,
"orderRefine":"neighbors-desc-lengths-desc",
"targetCell":"max-length-first",
"typeCanon":"edges",
"useMcr":true,
"useMcrPlus":false,
"useMcrBreak":true,
"typeIndicator":"none"

En la Figura vemos la familia de grafos Miyazaki (CMZ) para ejemplares desde 120 nodos y 190 aristas hasta 1008 nodos y 1596 aristas, gráfica que puede importar en la aplicación Gráficas matemáticas usando la configuración del archivo graphic-cmz.txt

Se aplican podas con automorfismos ("useMcr":true) pero no con indicadores ("typeIndicator":"none") pues no se producen con este grafo.

"useRefine":true,
"orderRefine":"neighbors-desc-lengths-desc",
"targetCell":"max-length-first",
"typeCanon":"edges",
"useMcr":true,
"useMcrPlus":false,
"useMcrBreak":true,
"typeIndicator":"none"

En la Figura vemos la familia de grafos Lattice para ejemplares desde 100 nodos y 900 aristas hasta 900 nodos y 26100 aristas, gráfica que puede importar en la aplicación Gráficas matemáticas usando la configuración del archivo graphic-lattice.txt

Se aplican podas con automorfismos ("useMcr":true) pero no con indicadores ("typeIndicator":"none") pues no se producen con este grafo.

"useRefine":true,
"orderRefine":"neighbors-desc-lengths-desc",
"targetCell":"max-length-first",
"typeCanon":"edges",
"useMcr":true,
"useMcrPlus":false,
"useMcrBreak":true,
"typeIndicator":"none"

En la Figura vemos la familia de grafos Grid 2 para ejemplares desde 25 nodos y 40 aristas hasta 4900 nodos y 9600 aristas, gráfica que puede importar en la aplicación Gráficas matemáticas usando la configuración del archivo graphic-grid-2.txt

Se aplican podas con automorfismos ("useMcr":true) pero no con indicadores ("typeIndicator":"none") pues no se producen con este grafo.

"useRefine":true,
"orderRefine":"neighbors-desc-lengths-desc",
"targetCell":"max-length-first",
"typeCanon":"edges",
"useMcr":true,
"useMcrPlus":false,
"useMcrBreak":true,
"typeIndicator":"none"

En la Figura vemos la familia de grafos Grid with switched 2 para ejemplares desde 25 nodos y 50 aristas hasta 3600 nodos y 7200 aristas, gráfica que puede importar en la aplicación Gráficas matemáticas usando la configuración del archivo graphic-grid-w-2.txt

Se aplican podas con automorfismos ("useMcr":true) pero no con indicadores ("typeIndicator":"none") pues no se producen con este grafo.

"useRefine":true,
"orderRefine":"neighbors-desc-lengths-desc",
"targetCell":"max-length-first",
"typeCanon":"edges",
"useMcr":true,
"useMcrPlus":false,
"useMcrBreak":true,
"typeIndicator":"none"

En la Figura vemos la familia de grafos completos (K) para ejemplares desde 10 nodos y 45 aristas hasta 500 nodos y 124750 aristas, gráfica que puede importar en la aplicación Gráficas matemáticas usando la configuración del archivo graphic-k.txt

Se aplican podas con automorfismos ("useMcr":true) pero no con indicadores ("typeIndicator":"none") pues no se producen con este grafo.

"useRefine":true,
"orderRefine":"neighbors-desc-lengths-desc",
"typeCanon":"edges",
"targetCell":"max-length-first",
"useMcr":true,
"useMcrPlus":false,
"useMcrBreak":true,
"typeIndicator":"none"

En la Figura vemos la familia de grafos triangulares para ejemplares desde 21 nodos y 105 aristas hasta 435 nodos y 12180 aristas, gráfica que puede importar en la aplicación Gráficas matemáticas usando la configuración del archivo graphic-triang.txt

Se aplican podas con automorfismos ("useMcr":true) pero no con indicadores ("typeIndicator":"none") pues no se producen con este grafo.

"useRefine":true,
"orderRefine":"neighbors-desc-lengths-desc",
"targetCell":"max-length-first",
"typeCanon":"edges",
"useMcr":true,
"useMcrPlus":false,
"useMcrBreak":true,
"typeIndicator":"none"

En la Figura vemos la familia de grafos hypercubes para ejemplares desde 8 nodos y 12 aristas hasta 4096 nodos y 24576 aristas, gráfica que puede importar en la aplicación Gráficas matemáticas usando la configuración del archivo graphic-hypercubes.txt

Quedan 9 tamaños desde 8192 nodos y 53248 aristas hasta 2097152 nodos y 22020096 aristas que son demasiado grandes para importar en la aplicación y no se pudieron probar.

Se aplican podas con automorfismos ("useMcr":true) pero no con indicadores ("typeIndicator":"none") pues no se producen con este grafo.

"useRefine":true,
"orderRefine":"neighbors-desc-lengths-desc",
"targetCell":"max-length-first",
"typeCanon":"edges",
"useMcr":true,
"useMcrPlus":false,
"useMcrBreak":true,
"typeIndicator":"none"

En la Figura vemos la familia de grafos Random Graph Edge Probability 1/10 para ejemplares desde 100 nodos y 502 aristas hasta 1000 nodos y 49840 aristas, gráfica que puede importar en la aplicación Gráficas matemáticas usando la configuración del archivo graphic-ran-10-a.txt

Hay 5 familias desde la "a" hasta la "e". Aquí sólo probamos la primera "a". Hay ejemplares con menos de 100 nodos pero no se prueban pues su ejecución ocupan tiempos insignificantes. A partir de 1000 nodos hay más ejemplares desde 2000 hasta 10000 en tramos de 1000, que no se prueban pues empiezan a tener muchas aristas que impiden que se puedan importar en la aplicación.

No se aplican podas de ningún tipo pues estos grafos tienen un árbol de particiones con solo 2 nodos, pues tras refinar la partición inicial se obtiene una partición discreta.

"useRefine":true,
"orderRefine":"neighbors-desc-lengths-desc",
"targetCell":"max-length-first"
"typeCanon":"edges",
"useMcr":false,
"useMcrPlus":false,
"useMcrBreak":false,
"typeIndicator":"none"

En la Figura vemos la familia de grafos Random Regular para ejemplares desde 32 nodos y 96 aristas hasta 2048 nodos y 6144 aristas, gráfica que puede importar en la aplicación Gráficas matemáticas usando la configuración del archivo graphic-ranreg.txt

Hay más ejemplares de 4096, 8192, 16384, 32768, 65536, 131072 nodos que no se prueban.

No se aplican podas de ningún tipo pues no tienen automorfismos y no aplican podas por los indicadores implementados. El árbol de particiones que se obtiene para cada ejemplar tiene un tamaño del mismo número de nodos más 1.

"useRefine":true,
"orderRefine":"neighbors-desc-lengths-desc",
"targetCell":"max-length-first"
"typeCanon":"edges",
"useMcr":false,
"useMcrPlus":false,
"useMcrBreak":false,
"typeIndicator":"none"

En la Figura vemos la familia de grafos Vertex Transitive (TRAN) para ejemplares desde 182 nodos y 728 aristas hasta 3016 nodos y 13572 aristas, gráfica que puede importar en la aplicación Gráficas matemáticas usando la configuración del archivo graphic-ranreg.txt

Elegimos ejemplares cuyos números de nodos y aristas sean incrementales.

Se aplican podas automorfismos pero no tiene poda con indicadores.

"useRefine":true,
"orderRefine":"neighbors-desc-lengths-desc",
"targetCell":"max-length-first",
"typeCanon":"edges",
"useMcr":true,
"useMcrPlus":false,
"useMcrBreak":true,
"typeIndicator":"none"

En la Figura vemos la familia de grafos Random Cubic (RND-3-REG) para 3 ejemplares de 1000 nodos y 1500 aristas, 2000 nodos y 3000 aristas y 3000 nodos y 4500 aristas, gráfica que puede importar en la aplicación Gráficas matemáticas usando la configuración del archivo graphic-rnd-3-reg.txt

Son pocos datos para ver si el comportamiento es polinómico. Con el menor ejemplar de 1000 nodos tarda casi 40 segundos y el tercero 1089 segundos, tiempos muy grandes debido a que sólo se aplica refinamiento, pues no tienen automorfismos y por tanto no hay poda por ello. Ni tampoco responden a los indicadores implementados. Quedan 7 ejemplares más desde 4000 (6000 aristas) hasta 10000 (15000 aristas). Hay 11 subfamilias rnd-3-reg-N-1 a rnd-3-reg-N-11 de la que se prueba solo la primera.

"useRefine":true,
"orderRefine":"neighbors-desc-lengths-desc",
"targetCell":"max-length-first",
"typeCanon":"edges",
"useMcr":false,
"useMcrPlus":false,
"useMcrBreak":false,
"typeIndicator":"none"

Pruebas con grafos con comportamiento polinómico y evolución no uniforme

Las familias de grafos que hemos visto en el apartado anterior tenían un comportamiento uniforme, observando que la línea de tendencia polinómica se podía ajustar bastante a los resultados. Pero no todos se comportan así, como veremos en los siguientes.

En la Figura vemos la familia de grafos Paley para ejemplares desde 25 nodos y 150 aristas hasta 435 nodos y 53015 aristas, gráfica que puede importar en la aplicación Gráficas matemáticas usando la configuración del archivo graphic-paley.txt. Se observan algunos ejemplares que tienen un leve incremento de tiempo sobre el resto.

Se aplican podas con automorfismos ("useMcr":true) pero no con indicadores ("typeIndicator":"none") pues no se producen con este grafo.

"useRefine":true,
"orderRefine":"neighbors-desc-lengths-desc",
"targetCell":"max-length-first",
"typeCanon":"edges",
"useMcr":true,
"useMcrPlus":false,
"useMcrBreak":true,
"typeIndicator":"none"

En la Figura vemos la familia de grafos Latin para ejemplares desde 40 nodos y 62 aristas hasta 1000 nodos y 2300 aristas, gráfica que puede importar en la aplicación Gráficas matemáticas usando la configuración del archivo graphic-latin.txt. Los ejemplares de 144 y 576 nodos tienen tiempo de ejecución superior a la línea de tendencia.

Se aplican podas con automorfismos ("useMcr":true) y con indicadores ("typeIndicator":"lengths").

"useRefine":true,
"orderRefine":"neighbors-desc-lengths-desc",
"targetCell":"max-length-first",
"typeCanon":"edges",
"useMcr":true,
"useMcrPlus":false,
"useMcrBreak":true,
"typeIndicator":"lengths"

En la Figura vemos la familia de grafos Latin switched para ejemplares desde 100 nodos y 1350 aristas hasta 400 nodos y 11400 aristas, gráfica que puede importar en la aplicación Gráficas matemáticas usando la configuración del archivo graphic-latin-sw-1.txt.

El último ejemplar de 400 nodos no pudo ser obtenido en el tiempo límite de 600 segundos que imponemos en el algoritmo getPartitionTree() en esta prueba para obtener el árbol de particiones. En estos casos se les incluye con ese tiempo de 600 segundos resaltándose con el marcador en color rojo. En esta familia encontramos 10 ejemplares más desde 441 hasta 900 nodos que no presentamos pues no obtendremos resultado dentro de ese máximo de 600 segundos.

No se aplican podas con automorfismos ("useMcr":true) pues este grafo no los tiene, aunque si con indicadores ("typeIndicator":"lengths").

"useRefine":true,
"orderRefine":"neighbors-desc-lengths-desc",
"targetCell":"min-length-first",
"typeCanon":"edges",
"useMcr":false,
"useMcrPlus":false,
"useMcrBreak":false,
"typeIndicator":"lengths"

En la Figura vemos la familia de grafos Cai, Fürer and Immerman Graphs (CFI) para ejemplares desde 200 nodos y 300 aristas hasta 1100 nodos y 1650 aristas, gráfica que puede importar en la aplicación Gráficas matemáticas usando la configuración del archivo graphic-cfi.txt.

Imponemos un límite máximo de 300 segundos y vemos que 4 ejemplares superan ese tiempo. Además hay dos de ellos que se desvían más significativamente de la línea de tendencia. En esta familia hay más grafos, desde 1120 hasta 2000 nodos pero no los he probado, pues supuestamente viendo el comportamiento anterior empezaran a necesitar más de 300 segundos para finalizar.

Se aplican podas con automorfismos ("useMcr":true) y con indicadores ("typeIndicator":"lengths").

"useRefine":true,
"orderRefine":"neighbors-asc",
"targetCell":"min-length-first",
"typeCanon":"edges",
"useMcr":true,
"useMcrPlus":false,
"useMcrBreak":true,
"typeIndicator":"lengths"

En la Figura vemos la familia de grafos Affine Geometry Graphs (AG) para ejemplares desde 55 nodos y 150 aristas hasta 2775 nodos y 52022 aristas, gráfica que puede importar en la aplicación Gráficas matemáticas usando la configuración del archivo graphic-ag2.txt.

Dos ejemplares superan el tiempo máximo de 300 segundos y otros se alejan significativamente de la línea de tendencia. En esta familia hay 4 ejemplares más, desde 3403 nodos y 70602 aristas hasta 4851 nodos y 120050 aristas, pero estos grafos son tan grandes que no se pueden importar en la aplicación y ni, por tanto, ejecutar el algoritmo.

Se aplican podas con automorfismos ("useMcr":true) pero no con indicadores ("typeIndicator":"none") pues no se producen con este grafo.

"useRefine":true,
"orderRefine":"neighbors-desc-lengths-desc",
"targetCell":"max-length-first",
"typeCanon":"edges",
"useMcr":true,
"useMcrPlus":false,
"useMcrBreak":true,
"typeIndicator":"none"

En la Figura vemos la familia de grafos Steiner Triple System (STS) para ejemplares desde 12 nodos y 54 aristas hasta 1027 nodos y 58539 aristas, gráfica que puede importar en la aplicación Gráficas matemáticas usando la configuración del archivo graphic-sts.txt.

Hemos ubicado la línea de tendencia centrada entre lo que aparenta dos comportamientos. En este caso se presentan todos los ejemplares disponibles de esa familia, observando que tres de ellos al final superan el límite de 900 segundos de tiempo máximo que en este caso hemos impuesto al algoritmo.

Se aplican podas con automorfismos ("useMcr":true) pero no con indicadores ("typeIndicator":"none") pues no se producen con este grafo.

"useRefine":true,
"orderRefine":"neighbors-desc-lengths-desc",
"targetCell":"min-length-first",
"typeCanon":"edges",
"useMcr":true,
"useMcrPlus":false,
"useMcrBreak":true,
"typeIndicator":"none"

En la Figura vemos la familia de grafos Steiner Triple System with switched edges (STS-SW) para ejemplares desde 57 nodos y 684 aristas hasta 330 nodos y 10395 aristas, gráfica que puede importar en la aplicación Gráficas matemáticas usando la configuración del archivo graphic-sts-sw.txt.

Vemos que es uniforme en todos esos tamaños y lo ponemos en este apartado para que esté junto al STS que vimos antes. En esta familia hay varias subfamilias, testeando solo los de la subfamilia sts-sw-N-1, habiéndo 10 subfamilias más, desde N-2 hasta N-11. Y aún quedan 11 ejemplares de esta subfamilia N-1 por ejecutar, desde 392 hasta 1027 nodos que omitimos pues ya empezarán a superar los 300 segundos, pues los que se han probado están por debajo pero el último se acerca a ese límite (300000 ≃ 10^5.48)

No se aplican podas con automorfismos ("useMcr":true) pues este grafo no los tiene, ni con indicadores ("typeIndicator":"lengths") pues no responde a ellos.

"useRefine":true,
"orderRefine":"neighbors-desc-lengths-asc",
"targetCell":"min-length-first",
"typeCanon":"edges",
"useMcr":false,
"useMcrPlus":false,
"useMcrBreak":false,
"typeIndicator":"none"

En la Figura vemos la familia de grafos Hadamard Matrix (HAD) para ejemplares desde 16 nodos y 40 aristas hasta 688 nodos y 59512 aristas, gráfica que puede importar en la aplicación Gráficas matemáticas usando la configuración del archivo graphic-had.txt.

Este grafo es el que menos uniformidad tiene. Desde 225 nodos hay muchos que superan el máximo de 300 segundos que imponemos para esta prueba. Quedan aún 21 ejemplares por ejecutar, desde 704 a 1024 nodos, que omitimos pues la mayoría ya superarán el límite de 300 segundos.

Se aplican podas con automorfismos ("useMcr":true) pero no con indicadores ("typeIndicator":"none") pues no se producen con este grafo.

"useRefine":true,
"orderRefine":"neighbors-desc-lengths-desc",
"targetCell":"max-length-first",
"typeCanon":"edges",
"useMcr":true,
"useMcrPlus":false,
"useMcrBreak":true,
"typeIndicator":"none"

En la Figura vemos la familia de grafos Hadamard Matrix with switched edges (HAD-SW) para 4 ejemplares desde 80 nodos y 840 aristas hasta 160 nodos y 3280 aristas, gráfica que puede importar en la aplicación Gráficas matemáticas usando la configuración del archivo graphic-had-sw.txt.

A pesar de que no son grafos excesivamente grandes, sólo hemos podido finalizar dos ejemplares de los cuatro intentados, pues los otros dos alcanzaron el límite de 600 segundos que impusimos al algoritmo. Con estos datos no parece acertado proponer alguna línea de tendencia, pero es probable que se comporte como el anterior HAD. Quedan por probar 6 ejemplares desde 176 nodos (3960 aristas) hasta 448 nodos (25312 aristas). Algunos ejemplares tienen 11 subfamilias de las que se prueba sólo la primera.

Se aplican podas con automorfismos ("useMcr":true) pero no con indicadores ("typeIndicator":"none") pues no se producen con este grafo.

"useRefine":true,
"orderRefine":"neighbors-desc-lengths-desc",
"targetCell":"max-length-first",
"typeCanon":"edges",
"useMcr":true,
"useMcrPlus":false,
"useMcrBreak":true,
"typeIndicator":"none"

En la Figura vemos la familia de grafos Desarguesian Projective Plane (PG-2) para ejemplares desde 26 nodos y 52 aristas hasta 2814 nodos y 53466 aristas, gráfica que puede importar en la aplicación Gráficas matemáticas usando la configuración del archivo graphic-pg.txt.

Dos ejemplares syuperan el máximo de 300 segundos y otros se desvían significativamente de la supuesta línea de tendencia. Quedan 4 ejemplares más en esta familia desde 3446 hasta 4902 nodos (72366 a 122250 aristas), que son muy grandes para importarlos en la aplicación.

Se aplican podas con automorfismos ("useMcr":true) pero no con indicadores ("typeIndicator":"none") pues no se producen con este grafo.

"useRefine":true,
"orderRefine":"neighbors-asc",
"targetCell":"first",
"typeCanon":"edges",
"useMcr":true,
"useMcrPlus":false,
"useMcrBreak":true,
"typeIndicator":"none"

En la Figura vemos la familia de grafos Projective Plane Graphs (PP) para ejemplares desde 14 nodos y 21 aristas hasta 1514 nodos y 21196 aristas, gráfica que puede importar en la aplicación Gráficas matemáticas usando la configuración del archivo graphic-pp.txt.

Tres ejemplares superan el máximo de 300 segundos y dos de ellos se desvían de la línea de tendencia estimada, que en este caso es poco fiable dado que no hay muchos datos. De esta familia solo probamos los de la subfamilia pp-N-1, habiendo otras por cada número de nodos N. Así el ejemplar pp-25-1 con 1302 nodos y 16926 aristas (el penúltimo de la gráfica) es el primero de la subfamilia hasta 193 ejemplares con el mismo número de nodos y aristas pero conectados de otra forma, supongo. Del último de la gráfica hay 13 ejemplares.

Se aplican podas con automorfismos ("useMcr":true) pero no con indicadores ("typeIndicator":"none") pues no se producen con este grafo.

"useRefine":true,
"orderRefine":"neighbors-desc-lengths-desc",
"targetCell":"max-length-first",
"typeCanon":"edges",
"useMcr":true,
"useMcrPlus":false,
"useMcrBreak":true,
"typeIndicator":"none"

Pruebas con grafos con comportamiento exponencial

Las pruebas anteriores evidenciaban un comportamiento polinómico más o menos uniforme. Pero esto no siempre sucede para todos los grafos, como los que veremos a continuación. Incluso con podas automorfismos e indicadores en algún caso no bajan de un comportamiento exponencial.

En la Figura vemos la familia de grafos Cubic Hypohamiltonian Graphs (CHH) para ejemplares desde 22 nodos y 33 aristas hasta 352 nodos y 840 aristas, gráfica que puede importar en la aplicación Gráficas matemáticas usando la configuración del archivo graphic-chh.txt. Se observa un comportamiento no polinómico, pues la línea de tendencia es exponencial y = 1.032^x

Esta familia tiene dos subfamilias, de las cuales se prueban solo la primera. Como el último de 352 nodos excede los 300 segundos, no se intentan el resto que quedan de 550, 660, 792, 924 y 1078 nodos.

Se aplican podas con automorfismos ("useMcr":true) pero no con indicadores ("typeIndicator":"none") pues no se producen con este grafo. Aún con podas automorfismos tiene comportamiento exponencial.

"useRefine":true,
"orderRefine":"neighbors-desc-lengths-desc",
"targetCell":"max-length-first",
"typeCanon":"edges",
"useMcr":true,
"useMcrPlus":false,
"useMcrBreak":true,
"typeIndicator":"none"

En la Figura vemos la familia de grafos Non-Disjoint Union of Tripartite (TNN) para ejemplares desde 26 nodos y 72 aristas hasta 182 nodos y 2520 aristas, gráfica que puede importar en la aplicación Gráficas matemáticas usando la configuración del archivo graphic-tnn.txt. Aunque no son muchos ejemplares, con esos se podría estimar un comportamiento exponencial con línea de tendencia y = 1.08^n-16

Esta familia tiene dos subfamilias, de las cuales se prueban solo la primera. El último de 182 nodos tarda 325 segundos y no se intentan el resto que quedan de 286, 416, 598, 806, 1014 nodos pues superarán ampliamente los 300 segundos.

Se aplican podas con automorfismos ("useMcr":true) e indicadores ("typeIndicator":"lengths") y aún así tiene comportamiento exponencial.

"useRefine":true,
"orderRefine":"neighbors-desc-lengths-desc",
"targetCell":"max-length-first",
"typeCanon":"edges",
"useMcr":true,
"useMcrPlus":false,
"useMcrBreak":true,
"typeIndicator":"lengths"

En la Figura vemos la familia de grafos Union of Strongly Regular Graphs (USR) para 3 ejemplares desde 29 nodos y 203 aristas hasta 87 nodos y 3132 aristas, gráfica que puede importar en la aplicación Gráficas matemáticas usando la configuración del archivo graphic-usr.txt. Solo pudimos ejecutar los dos primeros ejemplares pues el tercero no finaliza en 1200 segundos. Con esos se observa un comportamiento exponencial con línea de tendencia y = 1.25^x-13.5

No se prueba el resto de ejemplares de 116, 203, 406, 609, 812, 986 nodos.

Se aplican podas con automorfismos ("useMcr":true) e indicadores ("typeIndicator":"lengths") y aún así tiene comportamiento exponencial.

"useRefine":true,
"orderRefine":"neighbors-desc-lengths-desc",
"targetCell":"max-length-first",
"typeCanon":"edges",
"useMcr":true,
"useMcrPlus":false,
"useMcrBreak":true,
"typeIndicator":"lengths"

En la Figura vemos la familia de grafos Kronecker Eye Flip (KEF) para 2 ejemplares de 200 nodos con 1000 aristas y 242 nodos con 1331 aristas, gráfica que puede importar en la aplicación Gráficas matemáticas usando la configuración del archivo graphic-usr.txt. A pesar de ser grafos no muy grandes en tamaño, solo pudimos ejecutar el primer ejemplar pues el segundo no finaliza en 1200 segundos. Con esos dos puntos se evidencia un comportamiento exponencial superior a la línea de tendencia y = 1.127^x-125

Quedan 9 ejemplares desde 288 nodos y 1728 aristas Hasta 800 nodos y 8000 aristas que no se prueban pues superarán los 1200 segundos.

Se aplican podas con automorfismos ("useMcr":true) e indicadores ("typeIndicator":"lengths") y aún así tiene comportamiento fuertemente exponencial.

"useRefine":true,
"orderRefine":"neighbors-desc-lengths-desc",
"targetCell":"max-length-last",
"typeCanon":"edges",
"useMcr":true,
"useMcrPlus":false,
"useMcrBreak":true,
"typeIndicator":"lengths"

En la Figura vemos la familia de grafos Random Tree (RANTREE) para ejemplares desde 50 nodos con 49 aristas hasta 2000 nodos con 1999 aristas, gráfica que puede importar en la aplicación Gráficas matemáticas usando la configuración del archivo graphic-rantree.txt. Tiene un comportamiento errático y aunque no se obtuvieron los últimos puntos en el tiempo máximo de 300 segundos es posible que tenga un comportamiento exponencial. Es resaltable ver que el ejemplar de 700 nodos tiene un tiempo significativamente inferior. Y a partir de ahí ya no se obtienen más en el máximo tiempo de 300 segundos.

Quedan 5 ejemplares de 5000, 10000, 20000, 50000, 100000 nodos que no se prueban.

Se aplican podas con automorfismos ("useMcr":true) pero no con indicadores.

"useRefine":true,
"orderRefine":"neighbors-desc-lengths-desc",
"targetCell":"max-length-first",
"typeCanon":"edges",
"useMcr":true,
"useMcrPlus":false,
"useMcrBreak":true,
"typeIndicator":"none"

Pruebas de isomorfismos

Para este apartado tenemos el Grafo de Miyazaki de la Figura y otro en la Figura. El primero puede verse en la página 44 del documento de referencia [D11], al que intercambiamos las aristas centrales lo que lo hace no isomorfo con el anterior. Puede importarlos en la aplicación con test-non-isomorphic.txt y con non-miyazaki-graph.txt respectivamente. Le pasamos un test de isomorfismos al primer grafo con 60000 permutaciones aleatorias resultando todas isomórficas (ver resultado en el archivo verify miyazaki.txt)

Si en el grafo de la Figura reposicionamos los nodos del subárbol de la parte izquierda, reposición que sólo afecta al aspecto visual no modificándose la estructura, entonces los dos enlaces centrales aparecen paralelos como vemos en la Figura (importar con non-miyazaki-graph-b.txt). Visualmente no es fácil ver que NO es una permutación del primer grafo de la Figura.

Aunque se podría intuir si nos fijamos en las aristas oblicuas de la parte izquierda del primer grafo y de este grafo. Puede probar en la aplicación con los JSON en el archivo cambiar-oblicuas.txt, donde cambiamos las oblicuas del grafo de la Figura y comprobamos que si es isomórfico con el primer grafo de la Figura.

En uno de los primeros temas de esta parte de isomorfismos expusimos el algoritmo isGraphIsomorphic() para saber si dos grafos resultan isomórficos. Como se observa en la Figura, en aquel tema aplicábamos en la opción método isomorfismo los de fuerza bruta, pues aún no habíamos explicado el algoritmo de McKay. Allí pusimos algunos ejemplos y ahora vamos a hacerlo nuevamente pero usando el algoritmo de McKay que genera el árbol de particiones, única forma de resolverlo pues el grafo tiene 20! permutaciones y se hace intratable usando fuerza bruta.

Usaremos el grafo de la Figura pasándole la matriz de adyacencia del grafo de la Figura con estas opciones que ya contemplan refinamiento, poda automorfismos y poda indicadores "useRefine":true, "orderRefine":"neighbors-desc-lengths-desc", "targetCell":"max-length-first", "typeCanon":"edges", "useMcr":true, "useMcrPlus":false, "useMcrBreak":true, "typeIndicator":"lengths". El resultado obtenido en tan sólo 13 ms es que no son isomórficos, resaltándose donde se observa la primera diferencia en el grafo canónico:

Time: 13 ms

Es el grafo isomórfico: [false,
"Canonical graph 
0,17,0,18,0,19,1,4,1,5,1,8,2,3,2,6,2,9,3,5,3,9,4,6,4,8,5,7,6,7,7,13,8,12,9,12,10,11,10,14,10,16,11,14,11,15,12,15,13,16,13,19,14,19,15,18,16,17,17,18
is not the same as 
0,17,0,18,0,19,1,4,1,5,1,8,2,3,2,6,2,9,3,6,3,8,4,5,4,9,5,7,6,7,7,13,8,12,9,12,10,11,10,14,10,16,11,14,11,15,12,15,13,16,13,19,14,19,15,18,16,17,17,18"]

Estos son los resultados del árbol de particiones getPartitionTree() resaltando las primeras diferencias:

Time: 3 ms

Obtener árbol particiones (McKay): {
"useRefine":true,"orderRefine":"neighbors-desc-lengths-desc","targetCell":"max-length-first","typeCanon":"edges","useMcr":true,"useMcrPlus":false,"useMcrBreak":true,"typeIndicator":"lengths",
"timeTotal":3,"timeIni":0,"timeRef":2,
"iter":22,"refine":13,"indexTree":12,
"leaves":5,
"prunningMcr":7,"prunningMcrBreak":2,
"prunningIndicators":0,"prunningIndicators2":5,
"firstCanonicalPartition":[[0],[1],[2],[17],[9],[6],[13],[3],[16],[18],[15],[4],[10],[11],[12],[19],[5],[7],[8],[14]],
"firstCanon":true,
"canonicalPartition":[[0],[1],[2],[17],[9],[6],[13],[3],[16],[18],[15],[4],[10],[11],[12],[19],[5],[7],[8],[14]],
"firstCanonicalLabel":[[0,17],[0,18],[0,19],[1,4],[1,5],[1,8],[2,3],[2,6],[2,9],[3,5],[3,9],[4,6],[4,8],[5,7],[6,7],[7,13],[8,12],[9,12],[10,11],[10,14],[10,16],[11,14],[11,15],[12,15],[13,16],[13,19],[14,19],[15,18],[16,17],[17,18]],
"canonicalLabel":[[0,17],[0,18],[0,19],[1,4],[1,5],[1,8],[2,3],[2,6],[2,9],[3,5],[3,9],[4,6],[4,8],[5,7],[6,7],[7,13],[8,12],[9,12],[10,11],[10,14],[10,16],[11,14],[11,15],[12,15],[13,16],[13,19],[14,19],[15,18],[16,17],[17,18]],
"canonicalIndicator":[1,15,0],
"nodes":
[[[-1,[],[1]]],
[[0,[0],[1,15]],[0,[1],[1,15]],[0,[3],[1,10]],[0,[4],[1,12]],[0,[5],[1,12]],[0,[8],[1,12]],[0,[10],[1,10]]],
[[0,[0,1],[1,15,0]],[0,[0,2],[1,15,0]],[0,[0,9],[1,15,0]],[1,[1,0],[1,15,0]],[1,[1,7],[1,15,0]]]],
"nodeBest":[2,0],
"mcr":[0,3,4,5,8,10],
"fixMcr":
[[[0,3,4,5,7,8,10,11,12,14,15,19],[0,1,3,4,5,6,7,8,9,10,11,12,14,15,16,19]],
[[0,3,4,5,7,8,10,11,12,14,15,16,18,19],[0,1,2,3,4,5,6,7,8,10,11,12,14,15,16,18,19]],
[[],[0,2,3,4,5,6,7,8,10,12]],
[[],[0,2,3,4,5,8,10]]],
"lastEqual":true,"rebuiltMcr":0,"nonRebuiltMcr":15,
"tree":null,
"automorphisms":4,
"automorphismsPlus":0}

Time: 2 ms

Obtener árbol particiones (McKay): {
"useRefine":true,"orderRefine":"neighbors-desc-lengths-desc","targetCell":"max-length-first","typeCanon":"edges","useMcr":true,"useMcrPlus":false,"useMcrBreak":true,"typeIndicator":"lengths",
"timeTotal":2,"timeIni":0,"timeRef":2,
"iter":22,"refine":13,"indexTree":12,
"leaves":5,
"prunningMcr":7,"prunningMcrBreak":2,
"prunningIndicators":0,"prunningIndicators2":5,
"firstCanonicalPartition":[[0],[1],[2],[17],[9],[16],[18],[10],[6],[13],[15],[4],[3],[11],[12],[19],[5],[7],[8],[14]],
"firstCanon":true,
"canonicalPartition":[[0],[1],[2],[17],[9],[16],[18],[10],[6],[13],[15],[4],[3],[11],[12],[19],[5],[7],[8],[14]],
"firstCanonicalLabel":[[0,17],[0,18],[0,19],[1,4],[1,5],[1,8],[2,3],[2,6],[2,9],[3,6],[3,8],[4,5],[4,9],[5,7],[6,7],[7,13],[8,12],[9,12],[10,11],[10,14],[10,16],[11,14],[11,15],[12,15],[13,16],[13,19],[14,19],[15,18],[16,17],[17,18]],
"canonicalLabel":[[0,17],[0,18],[0,19],[1,4],[1,5],[1,8],[2,3],[2,6],[2,9],[3,6],[3,8],[4,5],[4,9],[5,7],[6,7],[7,13],[8,12],[9,12],[10,11],[10,14],[10,16],[11,14],[11,15],[12,15],[13,16],[13,19],[14,19],[15,18],[16,17],[17,18]],
"canonicalIndicator":[1,15,0],
"nodes":
[[[-1,[],[1],"PA","PA","PA","PA","PA","PA8"]],
[[0,[0],[1,15],"PA"],[0,[1],[1,15],"PA","PA1"],[0,[3],[1,10],"PI"],[0,[4],[1,12],"PI"],[0,[5],[1,12],"PI"],[0,[8],[1,12],"PI"],[0,[10],[1,10],"PI"]],
[[0,[0,1],[1,15,0],"f*"],[0,[0,2],[1,15,0],"==(1 2)(6 13)(9 17)(16 18)"],[0,[0,9],[1,15,0],"==(1 9)(2 17)(6 13)"],[1,[1,0],[1,15,0],"==(0 1)(2 15)(3 11)(4 18)(5 13)(6 14)(7 9)(8 16)(10 19)(12 17)"],[1,[1,7],[1,15,0],"==(0 1 7 9)(2 12 17 15)(3 11)(4 18)(5 13 14 6)(8 16)(10 19)"]]],
"nodeBest":[2,0],
"mcr":[0,3,4,5,8,10],
"fixMcr":
[[[0,3,4,5,7,8,10,11,12,14,15,19],[0,1,3,4,5,6,7,8,9,10,11,12,14,15,16,19]],
[[0,3,4,5,7,8,10,11,12,14,15,16,18,19],[0,1,2,3,4,5,6,7,8,10,11,12,14,15,16,18,19]],
[[],[0,2,3,4,5,6,7,8,10,12]],
[[],[0,2,3,4,5,8,10]]],
"lastEqual":true,"rebuiltMcr":0,"nonRebuiltMcr":15,
"tree":[{"index":0,"value":"(0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19)","parent":-1},
{"index":1,"value":"(0)(1 2 9 17)(16 18)(10)(6 13)(15)(4)(3)(11)(12)(19)(5)(7)(8)(14)","parent":[{"index":0,"value":"０"}]},
{"index":2,"value":"(0)(1)(2)(17)(9)(16)(18)(10)(6)(13)(15)(4)(3)(11)(12)(19)(5)(7)(8)(14)","parent":[{"index":1,"value":"１"}]},
{"index":3,"value":"(0)(2)(1)(9)(17)(18)(16)(10)(13)(6)(15)(4)(3)(11)(12)(19)(5)(7)(8)(14)","parent":[{"index":1,"value":"２"}]},
{"index":4,"value":"(0)(9)(17)(2)(1)(16)(18)(10)(13)(6)(15)(4)(3)(11)(12)(19)(5)(7)(8)(14)","parent":[{"index":1,"value":"９"}]},
{"index":5,"value":"(1)(0 7 12 15)(4 8)(19)(5 14)(2)(18)(11)(3)(17)(10)(13)(9)(16)(6)","parent":[{"index":0,"value":"１"}]},
{"index":6,"value":"(1)(0)(15)(12)(7)(8)(4)(19)(14)(5)(2)(18)(11)(3)(17)(10)(13)(9)(16)(6)","parent":[{"index":5,"value":"０"}]},
{"index":7,"value":"(1)(7)(12)(15)(0)(8)(4)(19)(5)(14)(2)(18)(11)(3)(17)(10)(13)(9)(16)(6)","parent":[{"index":5,"value":"７"}]},
{"index":8,"value":"(3)(0 7 12 15)(5 14)(11)(10)(16 18)(1 2 9 17)(4 8)(6 13)(19)","parent":[{"index":0,"value":"３"}]},
{"index":9,"value":"(4)(1 2 9 17)(6 13)(16 18)(10)(0 7)(11)(3)(8)(5 14)(12 15)(19)","parent":[{"index":0,"value":"４"}]},
{"index":10,"value":"(5)(1 2 9 17)(6 13)(3)(16 18)(19)(0 12)(14)(4 8)(10)(7 15)(11)","parent":[{"index":0,"value":"５"}]},
{"index":11,"value":"(8)(1 2 9 17)(6 13)(16 18)(10)(12 15)(11)(3)(4)(5 14)(0 7)(19)","parent":[{"index":0,"value":"８"}]},
{"index":12,"value":"(10)(0 7 12 15)(4 8)(19)(3)(6 13)(1 2 9 17)(5 14)(16 18)(11)","parent":[{"index":0,"value":"１０"}]}],
"automorphisms":
[[[0],[1,2],[3],[4],[5],[6,13],[7],[8],[9,17],[10],[11],[12],[14],[15],[16,18],[19]],
[[0],[1,9],[2,17],[3],[4],[5],[6,13],[7],[8],[10],[11],[12],[14],[15],[16],[18],[19]],
[[0,1],[2,15],[3,11],[4,18],[5,13],[6,14],[7,9],[8,16],[10,19],[12,17]],
[[0,1,7,9],[2,12,17,15],[3,11],[4,18],[5,13,14,6],[8,16],[10,19]]],
"automorphismsPlus":0}

Podemos exportar a Wolfram Cloud que usa IsomorphicGraphQ[g1, g2] resultando false con lo que también nos dice que no son isomórficos.

g1 = AdjacencyGraph[{{0,0,0,0,0,0,0,1,1,0,0,0,0,0,1,0,0,0,0,0},{0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,0,1,0,0,0},{0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,1,0},{0,0,0,0,0,0,1,0,0,0,0,1,0,1,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,0,1},{0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0},{0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0},{1,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0},
{1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1},{0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,0},{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,1},{0,0,0,1,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0},
{0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0},{0,0,1,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0},{1,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0},{0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0},
{0,1,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0},{0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0},{0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0},{0,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0}}, 
ImageSize -> 250, VertexSize -> {"Scaled", 0.07}, VertexLabels -> {1 -> Placed[0,Center], 2 -> Placed[1,Center], 3 -> Placed[2,Center], 4 -> Placed[3,Center], 5 -> Placed[4,Center], 
6 -> Placed[5,Center], 7 -> Placed[6,Center], 8 -> Placed[7,Center], 9 -> Placed[8,Center], 10 -> Placed[9,Center], 11 -> Placed[10,Center], 12 -> Placed[11,Center], 13 -> Placed[12,Center], 
14 -> Placed[13,Center], 15 -> Placed[14,Center], 16 -> Placed[15,Center], 17 -> Placed[16,Center], 18 -> Placed[17,Center], 19 -> Placed[18,Center], 20 -> Placed[19,Center]}, 
VertexLabelStyle -> Directive[Black,9], EdgeLabelStyle -> Directive[Black,9,Bold], VertexStyle -> White, EdgeStyle -> {{Black,Thickness[0.005]}}]
g2 = AdjacencyGraph[{{0,0,0,0,0,0,0,1,1,0,0,0,0,0,1,0,0,0,0,0},{0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,0,1,0,0,0},{0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,1,0},{0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,1},
{0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,0,1},{0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0},{0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0},{1,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0},
{1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1},{0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,0},{0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,1,0},{0,0,0,0,0,1,0,0,0,0,1,0,0,0,1,0,0,0,0,0},
{0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0},{0,0,1,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0},{1,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0},{0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0},
{0,1,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0},{0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0},{0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0},{0,0,0,1,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0}}, ImageSize -> 250];
IsomorphicGraphQ[g1, g2]

En el mismo documento de referencia [D11] aparece el grafo G de la Figura para explicar como es isomorfo al siguiente grafo H de la Figura, donde mostramos también su matriz de adyacencia.

0 1 1 1 0 0 0 0 0 0 0 0 0 0
1 0 0 0 1 1 0 0 0 0 0 0 0 0
1 0 0 0 0 0 1 1 0 0 0 0 0 0
1 0 0 0 0 0 0 0 1 1 0 0 0 0
0 1 0 0 0 0 0 0 0 0 1 0 1 0
0 1 0 0 0 0 0 0 0 0 1 0 1 0
0 0 1 0 0 0 0 0 0 0 1 0 1 0
0 0 1 0 0 0 0 0 0 0 0 1 0 1
0 0 0 1 0 0 0 0 0 0 0 1 0 1
0 0 0 1 0 0 0 0 0 0 0 1 0 1
0 0 0 0 1 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 1 0 0 0 0
0 0 0 0 1 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 1 0 0 0 0

El resultado del algoritmo isGraphIsomorphic() nos dice que son isomórficos:

Time: 2 ms

Es el grafo isomórfico: [true,"Canonical graphs are the same: 
0,11,0,12,0,13,1,4,1,5,1,7,2,4,2,5,2,7,3,4,3,5,3,6,6,9,6,10,7,10,8,11,8,12,8,13,9,11,9,12,10,13"]

Con este JSON puede importar el ejemplo:

{"nodes":[
    {"index":0,"nodeOffset":"-21.25 -0.93","parent":-1},
    {"index":1,"nodeOffset":"-54.59 41.4","parent":-1},
    {"index":2,"nodeOffset":"4.72 -25.93","parent":[0,1]},
    {"index":3,"nodeOffset":"-17.28 -4.77","parent":[0,1]},
    {"index":4,"nodeOffset":"-45.28 16.4","parent":[0,1]},
    {"index":5,"nodeOffset":"14.03 -50.93","parent":[2,3]},
    {"index":6,"nodeOffset":"31.67 -75.93","parent":5},
    {"index":7,"nodeOffset":"-1.67 -8.6","parent":[4,6]},
    {"index":8,"nodeOffset":"49.31 -100.93","parent":6},
    {"index":9,"nodeOffset":"66.95 -125.93","parent":8},
    {"index":10,"nodeOffset":"30.61 -104.77","parent":8},
    {"index":11,"nodeOffset":"33.61 -33.6","parent":7},
    {"index":12,"nodeOffset":"67.92 -150.93","parent":[9,11,10]},
    {"index":13,"nodeOffset":"51.25 -58.6","parent":[11,10,9]}
],
"config":{
    "algorithm":"Is graph isomorphic",
    "adjacencyMatrix":"0 1 1 1 0 0 0 0 0 0 0 0 0 0\n1 0 0 0 1 1 0 0 0 0 0 0 0 0\n1 0 0 0 0 0 1 1 0 0 0 0 0 0\n1 0 0 0 0 0 0 0 1 1 0 0 0 0\n0 1 0 0 0 0 0 0 0 0 1 0 1 0\n0 1 0 0 0 0 0 0 0 0 1 0 1 0\n0 0 1 0 0 0 0 0 0 0 1 0 1 0\n0 0 1 0 0 0 0 0 0 0 0 1 0 1\n0 0 0 1 0 0 0 0 0 0 0 1 0 1\n0 0 0 1 0 0 0 0 0 0 0 1 0 1\n0 0 0 0 1 1 1 0 0 0 0 0 0 0\n0 0 0 0 0 0 0 1 1 1 0 0 0 0\n0 0 0 0 1 1 1 0 0 0 0 0 0 0\n0 0 0 0 0 0 0 1 1 1 0 0 0 0\n",
    "methodIsomorphic":"McKay",
    "useMcrBreak":true,
    "typeIndicator":"lengths"
}}

Pasamos el test de isomorfismos al primer grafo con 100000 permutaciones aleatorias resultando todas isomórficas:

Time: 27633 ms

Test isomorfismos (McKay): {"useRefine":true,"orderRefine":"neighbors-desc-lengths-desc","typeCanon":"edges","targetCell":"max-length-first","useMcr":true,"useMcrPlus":false,"useMcrBreak":true,"typeIndicator":"lengths",
"isomorphic":100000,"nonIsomorphic":0,
"firstTime":0,"minTime":0,"averageTime":0,"maxTime":1,
"iter1":57,"iter2":44,
"indexTree1":25,"indexTree2":20,
"minIndexTree":20,"maxIndexTree":50,
"refine1":19,"refine2":15,
"numAut1":6,"numAut2":5,"numAutPlus1":0,"numAutPlus2":0,
"prunningMcr1":16,"prunningMcr2":11,"prunningMcrBreak1":1,"prunningMcrBreak2":1,
"rebuiltMcr1":0,"rebuiltMcr2":0,
"prunningIndicators1":0,"prunningIndicators2":0,
"prunningIndicators1b":3,"prunningIndicators2b":2,
"canonical":[[0,11],[0,12],[0,13],[1,4],[1,5],[1,7],[2,4],[2,5],[2,7],[3,4],[3,5],[3,6],[6,9],[6,10],[7,10],[8,11],[8,12],[8,13],[9,11],[9,12],[10,13]]}

El árbol de particiones del primer grafo es el siguiente, observando que tiene 26 nodos y se realizan 16+1 podas con automorfismos y 3 podas con indicadores:

Time: 2 ms

Obtener árbol particiones (McKay): {
"useRefine":true,"orderRefine":"neighbors-desc-lengths-desc","targetCell":"max-length-first","typeCanon":"edges","useMcr":true,"useMcrPlus":false,"useMcrBreak":true,"typeIndicator":"lengths",
"timeTotal":2,"timeIni":1,"timeRef":1,
"iter":57,"refine":19,"indexTree":25,
"leaves":7,
"prunningMcr":16,"prunningMcrBreak":1,
"prunningIndicators":0,"prunningIndicators2":3,
"firstCanonicalPartition":[[0],[12],[13],[8],[9],[10],[6],[11],[1],[5],[7],[2],[3],[4]],
"firstCanon":true,
"canonicalPartition":[[0],[12],[13],[8],[9],[10],[6],[11],[1],[5],[7],[2],[3],[4]],
"firstCanonicalLabel":[[0,11],[0,12],[0,13],[1,4],[1,5],[1,7],[2,4],[2,5],[2,7],[3,4],[3,5],[3,6],[6,9],[6,10],[7,10],[8,11],[8,12],[8,13],[9,11],[9,12],[10,13]],
"canonicalLabel":[[0,11],[0,12],[0,13],[1,4],[1,5],[1,7],[2,4],[2,5],[2,7],[3,4],[3,5],[3,6],[6,9],[6,10],[7,10],[8,11],[8,12],[8,13],[9,11],[9,12],[10,13]],
"canonicalIndicator":[1,11,12,13,0],
"nodes":
[[[-1,[],[1]]],
[[0,[0],[1,11]],[0,[1],[1,11]],[0,[2],[1,11]],[0,[4],[1,10]],[0,[6],[1,4]],[0,[8],[1,10]],[0,[9],[1,11]]],
[[0,[0,12],[1,11,12]],[0,[0,13],[1,11,12]],[1,[1,12],[1,11,12]],[2,[2,9],[1,11,12]],[6,[9,2],[1,11,12]]],
[[0,[0,12,9],[1,11,12,13]],[0,[0,12,10],[1,11,12,13]],[1,[0,13,9],[1,11,12,13]],[2,[1,12,9],[1,11,12,13]],[3,[2,9,12],[1,11,12,13]],[4,[9,2,0],[1,11,12,13]]],
[[0,[0,12,9,2],[1,11,12,13,0]],[0,[0,12,9,3],[1,11,12,13,0]],[1,[0,12,10,2],[1,11,12,13,0]],[2,[0,13,9,2],[1,11,12,13,0]],[3,[1,12,9,2],[1,11,12,13,0]],[4,[2,9,12,0],[1,11,12,13,0]],[5,[9,2,0,12],[1,11,12,13,0]]]],
"nodeBest":[4,0],
"mcr":[0,4,6],
"fixMcr":
[[[0,1,4,5,6,7,8,9,10,11,12,13],[0,1,2,4,5,6,7,8,9,10,11,12,13]],
[[0,1,2,3,4,5,6,7,8,11,12,13],[0,1,2,3,4,5,6,7,8,9,11,12,13]],
[[0,1,2,3,4,5,6,7,8,9,10,11],[0,1,2,3,4,5,6,7,8,9,10,11,12]],
[[2,3,4,5,6,7,8,9,10,11,12,13],[0,2,3,4,5,6,7,8,9,10,11,12,13]],
[[],[0,1,4,6,8,9,10]],
[[],[0,1,2,3,4,5,6]]],
"lastEqual":true,"rebuiltMcr":0,"nonRebuiltMcr":24,
"tree":null,
"automorphisms":6,
"automorphismsPlus":0}

En la Figura vemos la ejecución en Wolfram resultando isomórficos, usando el siguiente código.

g1 = AdjacencyGraph[{{0,0,1,1,1,0,0,0,0,0,0,0,0,0},{0,0,1,1,1,0,0,0,0,0,0,0,0,0},{1,1,0,0,0,1,0,0,0,0,0,0,0,0},{1,1,0,0,0,1,0,0,0,0,0,0,0,0},{1,1,0,0,0,0,0,1,0,0,0,0,0,0},
{0,0,1,1,0,0,1,0,0,0,0,0,0,0},{0,0,0,0,0,1,0,1,1,0,0,0,0,0},{0,0,0,0,1,0,1,0,0,0,0,1,0,0},{0,0,0,0,0,0,1,0,0,1,1,0,0,0},{0,0,0,0,0,0,0,0,1,0,0,0,1,1},
{0,0,0,0,0,0,0,0,1,0,0,0,1,1},{0,0,0,0,0,0,0,1,0,0,0,0,1,1},{0,0,0,0,0,0,0,0,0,1,1,1,0,0},{0,0,0,0,0,0,0,0,0,1,1,1,0,0}}, 
ImageSize -> 264, VertexSize -> {"Scaled", 0.06}, VertexLabels -> {1 -> Placed[0,Center], 2 -> Placed[1,Center], 3 -> Placed[2,Center], 4 -> Placed[3,Center], 5 -> Placed[4,Center], 
6 -> Placed[5,Center], 7 -> Placed[6,Center], 8 -> Placed[7,Center], 9 -> Placed[8,Center], 10 -> Placed[9,Center], 11 -> Placed[10,Center], 12 -> Placed[11,Center], 
13 -> Placed[12,Center], 14 -> Placed[13,Center]}, VertexLabelStyle -> Directive[Black,8], EdgeLabelStyle -> Directive[Black,8,Bold], VertexStyle -> White, 
EdgeStyle -> {{Black,Thickness[0.005]}}]
g2 = AdjacencyGraph[{{0,1,1,1,0,0,0,0,0,0,0,0,0,0},{1,0,0,0,1,1,0,0,0,0,0,0,0,0},{1,0,0,0,0,0,1,1,0,0,0,0,0,0},{1,0,0,0,0,0,0,0,1,1,0,0,0,0},{0,1,0,0,0,0,0,0,0,0,1,0,1,0},
{0,1,0,0,0,0,0,0,0,0,1,0,1,0},{0,0,1,0,0,0,0,0,0,0,1,0,1,0},{0,0,1,0,0,0,0,0,0,0,0,1,0,1},{0,0,0,1,0,0,0,0,0,0,0,1,0,1},{0,0,0,1,0,0,0,0,0,0,0,1,0,1},{0,0,0,0,1,1,1,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,1,1,1,0,0,0,0},{0,0,0,0,1,1,1,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,1,1,1,0,0,0,0}}, ImageSize -> 164]
IsomorphicGraphQ[g1, g2]

En un primer tema sobre isomorfismo vimos el ejemplo de la Figura tomado de la web Graph Theory, Part III. En aquel tema verificábamos con fuerza bruta que no eran isomórficos pues no se encontró una permutación entre las 8! = 40320 permutaciones del primer grafo que fuera igual que el segundo. La ejecución tomó 578 ms.

Verificándolo con McKay vemos que sólo tarda 1 ms en verificar que no son isomórficos, pues no se obtiene el mismo grafo canónico. Recuerde que lo que se obtiene son listas de aristas tal que 0,3,0,4,0,5... realmente es [[0,3],[0,4],[0,5],...]

0 1 1 0 0 0 0 0
1 0 0 1 0 0 0 0
1 0 0 1 0 0 1 0
0 1 1 0 0 0 0 1
0 0 0 0 0 1 1 0
0 0 0 0 1 0 0 1
0 0 1 0 1 0 0 1
0 0 0 1 0 1 1 0

Al primer grafo le pasamos la matriz de adyacencia del segundo, obteniéndose el siguiente resultado.

Time: 1 ms

Es el grafo isomórfico: [false
"Canonical graph   0,3,0,4,0,5,1,2,1,6,1,7,2,4,2,5,3,6,3,7 
is not the same as 0,1,0,2,0,7,1,3,1,6,2,3,2,4,3,5,4,5,6,7"]

Con estos JSON puede importar los grafos.

{"nodes":[
    {"index":0,"nodeOffset":"2.5","parent":-1},
    {"index":1,"nodeOffset":"67.5 15","parent":0},
    {"index":2,"nodeOffset":"-37.5 15","parent":0},
    {"index":3,"nodeOffset":"27.5 30","parent":[2,1]},
    {"index":4,"nodeOffset":"-22.5 -5","parent":0},
    {"index":5,"nodeOffset":"22.5 -10","parent":4},
    {"index":6,"nodeOffset":"-42.5 -10","parent":4},
    {"index":7,"nodeOffset":"2.5 -15","parent":[5,6,3]}
],
"config":{
    "algorithm":"Is graph isomorphic",
    "adjacencyMatrix":"0 1 1 0 0 0 0 0\n1 0 0 1 0 0 0 0\n1 0 0 1 0 0 1 0\n0 1 1 0 0 0 0 1\n0 0 0 0 0 1 1 0\n0 0 0 0 1 0 0 1\n0 0 1 0 1 0 0 1\n0 0 0 1 0 1 1 0",
    "methodIsomorphic":"McKay",
    "useMcrBreak":true
}}

{"nodes":[
    {"index":0,"nodeOffset":"19.17","parent":-1},
    {"index":1,"nodeOffset":"72.5 15","parent":0},
    {"index":2,"nodeOffset":"-27.5 15","parent":0},
    {"index":3,"nodeOffset":"19.17 30","parent":[2,1]},
    {"index":4,"nodeOffset":"-14.17 20","parent":-1},
    {"index":5,"nodeOffset":"12.5 15","parent":4},
    {"index":6,"nodeOffset":"-47.5 15","parent":[4,2]},
    {"index":7,"nodeOffset":"-14.17 10","parent":[5,6,3]}
],
"config":{}}

0 1 1 0 0 0 0 0
1 0 0 1 0 0 0 0
1 0 0 1 0 0 1 0
0 1 1 0 0 0 0 1
0 0 0 0 0 1 1 0
0 0 0 0 1 0 0 1
0 0 1 0 1 0 0 1
0 0 0 1 0 1 1 0

En la Figura vemos el resultado también no isomórficos en Wolfram usando IsomorphicGraphQ[g1, g2].

g1 = AdjacencyGraph[{{0,1,1,0,1,0,0,0},{1,0,0,1,0,0,0,0},{1,0,0,1,0,0,0,0},{0,1,1,0,0,0,0,1},{1,0,0,0,0,1,1,0},{0,0,0,0,1,0,0,1},{0,0,0,0,1,0,0,1},{0,0,0,1,0,1,1,0}}, ImageSize -> 263, VertexSize -> {"Scaled", 0.12}, VertexLabels -> {1 -> Placed[0,Center], 2 -> Placed[1,Center], 3 -> Placed[2,Center], 4 -> Placed[3,Center], 5 -> Placed[4,Center], 6 -> Placed[5,Center], 7 -> Placed[6,Center], 8 -> Placed[7,Center]}, VertexLabelStyle -> Directive[Black,17.5], EdgeLabelStyle -> Directive[Black,17.5,Bold], VertexStyle -> White, EdgeStyle -> {{Black,Thickness[0.005]}}]
g2 = AdjacencyGraph[{{0,1,1,0,0,0,0,0},{1,0,0,1,0,0,0,0},{1,0,0,1,0,0,1,0},{0,1,1,0,0,0,0,1},{0,0,0,0,0,1,1,0},{0,0,0,0,1,0,0,1},{0,0,1,0,1,0,0,1},{0,0,0,1,0,1,1,0}}, ImageSize -> 263]
IsomorphicGraphQ[g1, g2]

En la web Isomorphisms notes se muestra los dos grafos de la Figura que no son isomórficos, tal como obtenemos con el algoritmo isGraphIsomorphic() para lo que pasamos al primer grafo la matriz de adyacencia del segundo grafo:

0 0 0 1 1 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 0 0 0 0 0 0 0 0
0 0 0 0 0 1 1 0 0 0 0 0 0 0
1 0 0 0 0 0 0 1 0 0 0 0 0 0
1 1 0 0 0 0 0 0 1 0 0 0 0 0
0 1 1 0 0 0 0 0 0 1 0 0 0 0
0 0 1 0 0 0 0 0 0 0 1 0 0 0
0 0 0 1 0 0 0 0 0 0 0 1 0 0
0 0 0 0 1 0 0 0 0 0 0 1 1 0
0 0 0 0 0 1 0 0 0 0 0 0 1 1
0 0 0 0 0 0 1 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 0 0 0 0
0 0 0 0 0 0 0 0 0 1 1 0 0 0

Observe que no es posible verificarlo con fuerza bruta pues hay 14! ≃ 8.72×10¹⁰ permutaciones y en este caso habría que comprobarlas todas para deducir que no hay ninguna permutación del primer grafo con la que se obtenga el segundo.

Con McKay se obtiene que no son isomórficos en solo 2 ms pues no se obtiene el mismo grafo canónico.

Time: 2 ms

Es el grafo isomórfico: [false,
"Canonical graph 
0,8,0,10,1,9,1,11,2,3,2,11,3,10,4,7,4,13,5,6,5,12,6,9,7,8,10,13,11,12,12,13
is not the same as
0,3,0,7,1,2,1,5,2,4,3,6,4,11,5,10,6,12,7,13,8,11,8,13,9,10,9,12,10,11,12,13"]

Con este JSON puede importar el ejemplo. También se incluye el resultado de un test de isomorfismos para el primer grafo con 100000 permutaciones aleatorias resultando todas isomórficas.

{"nodes":[
    {"index":0,"nodeOffset":"-0.83 -3.73","value":"a","parent":-1},
    {"index":1,"nodeOffset":"-9.71 -2.88","value":"b","parent":-1},
    {"index":2,"nodeOffset":"-2.94 -14.34","value":"c","parent":0},
    {"index":3,"nodeOffset":"-3.58 -13.77","value":"d","parent":[0,1]},
    {"index":4,"nodeOffset":"-4.04 -15.18","value":"e","parent":1},
    {"index":5,"nodeOffset":"-3.73 -21.55","value":"f","parent":2},
    {"index":6,"nodeOffset":"-2.54 -22.4","value":"g","parent":3},
    {"index":7,"nodeOffset":"-2.91 -23.25","value":"h","parent":4},
    {"index":8,"nodeOffset":"-16.35 -31.6","value":"i","parent":5},
    {"index":9,"nodeOffset":"-14.68 -29.9","value":"j","parent":[5,6]},
    {"index":10,"nodeOffset":"-14.18 -31.6","value":"k","parent":[6,7]},
    {"index":11,"nodeOffset":"-24.18 -38.53","value":"l","parent":8},
    {"index":12,"nodeOffset":"-31.7 -38.82","value":"m","parent":9},
    {"index":13,"nodeOffset":"-29.86 -47.45","value":"n","parent":[11,12]}
],
"config":{
    "algorithm":"Is graph isomorphic",
    "adjacencyMatrix":"0 0 0 1 1 0 0 0 0 0 0 0 0 0\n0 0 0 0 1 1 0 0 0 0 0 0 0 0\n0 0 0 0 0 1 1 0 0 0 0 0 0 0\n1 0 0 0 0 0 0 1 0 0 0 0 0 0\n1 1 0 0 0 0 0 0 1 0 0 0 0 0\n0 1 1 0 0 0 0 0 0 1 0 0 0 0\n0 0 1 0 0 0 0 0 0 0 1 0 0 0\n0 0 0 1 0 0 0 0 0 0 0 1 0 0\n0 0 0 0 1 0 0 0 0 0 0 1 1 0\n0 0 0 0 0 1 0 0 0 0 0 0 1 1\n0 0 0 0 0 0 1 0 0 0 0 0 0 1\n0 0 0 0 0 0 0 1 1 0 0 0 0 0\n0 0 0 0 0 0 0 0 1 1 0 0 0 0\n0 0 0 0 0 0 0 0 0 1 1 0 0 0",
    "methodIsomorphic":"McKay",
    "useMcrPlus":true,
    "typeIndicator":"lengths"
}}

Time: 7498 ms
Test isomorfismos (McKay): {"useRefine":true,"orderRefine":"neighbors-desc-lengths-desc","typeCanon":"edges","targetCell":"max-length-first","useMcr":true,"useMcrPlus":true,"useMcrBreak":false,"typeIndicator":"lengths",
"isomorphic":100000,"nonIsomorphic":0,
"firstTime":1,"minTime":0,"averageTime":0,"maxTime":1,
"iter1":3,"iter2":3,
"indexTree1":3,"indexTree2":3,
"minIndexTree":3,"maxIndexTree":3,
"refine1":3,"refine2":3,
"numAut1":1,"numAut2":1,"numAutPlus1":0,"numAutPlus2":0,
"prunningMcr1":0,"prunningMcr2":0,"prunningMcrBreak1":0,"prunningMcrBreak2":0,
"rebuiltMcr1":0,"rebuiltMcr2":0,
"prunningIndicators1":0,"prunningIndicators2":0,
"prunningIndicators1b":0,"prunningIndicators2b":0,
"canonical":[[0,8],[0,10],[1,9],[1,11],[2,3],[2,11],[3,10],[4,7],[4,13],[5,6],[5,12],[6,9],[7,8],[10,13],[11,12],[12,13]]}

{"nodes":[
    {"index":0,"nodeOffset":"-4.03 1.15","value":1,"parent":-1},
    {"index":1,"nodeOffset":"-4.56 2","value":2,"parent":-1},
    {"index":2,"nodeOffset":"-1.67 1.71","value":3,"parent":-1},
    {"index":3,"nodeOffset":"-9.47 -9.46","value":4,"parent":0},
    {"index":4,"nodeOffset":"-5.1 -8.89","value":5,"parent":[0,1]},
    {"index":5,"nodeOffset":"-0.57 -10.3","value":6,"parent":[1,2]},
    {"index":6,"nodeOffset":"3.56 -11.15","value":7,"parent":2},
    {"index":7,"nodeOffset":"-10.25 -16.68","value":8,"parent":3},
    {"index":8,"nodeOffset":"-4.07 -17.53","value":9,"parent":4},
    {"index":9,"nodeOffset":"0.57 -18.37","value":10,"parent":5},
    {"index":10,"nodeOffset":"4.52 -20.07","value":11,"parent":6},
    {"index":11,"nodeOffset":"-0.7 -26.72","value":12,"parent":[7,8]},
    {"index":12,"nodeOffset":"-3.3 -26.72","value":13,"parent":[8,9]},
    {"index":13,"nodeOffset":"-3.13 -27.57","value":14,"parent":[9,10]}
],
"config":{}}

0 0 0 1 1 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 0 0 0 0 0 0 0 0
0 0 0 0 0 1 1 0 0 0 0 0 0 0
1 0 0 0 0 0 0 1 0 0 0 0 0 0
1 1 0 0 0 0 0 0 1 0 0 0 0 0
0 1 1 0 0 0 0 0 0 1 0 0 0 0
0 0 1 0 0 0 0 0 0 0 1 0 0 0
0 0 0 1 0 0 0 0 0 0 0 1 0 0
0 0 0 0 1 0 0 0 0 0 0 1 1 0
0 0 0 0 0 1 0 0 0 0 0 0 1 1
0 0 0 0 0 0 1 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 0 0 0 0
0 0 0 0 0 0 0 0 0 1 1 0 0 0

En la Figura vemos que en Wolfram también se obtiene que no son isomórficos usando IsomorphicGraphQ[g1, g2].

g1 = AdjacencyGraph[{{0,0,1,1,0,0,0,0,0,0,0,0,0,0},{0,0,0,1,1,0,0,0,0,0,0,0,0,0},{1,0,0,0,0,1,0,0,0,0,0,0,0,0},{1,1,0,0,0,0,1,0,0,0,0,0,0,0},{0,1,0,0,0,0,0,1,0,0,0,0,0,0},
{0,0,1,0,0,0,0,0,1,1,0,0,0,0},{0,0,0,1,0,0,0,0,0,1,1,0,0,0},{0,0,0,0,1,0,0,0,0,0,1,0,0,0},{0,0,0,0,0,1,0,0,0,0,0,1,0,0},{0,0,0,0,0,1,1,0,0,0,0,0,1,0},{0,0,0,0,0,0,1,1,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,1,0,0,0,0,1},{0,0,0,0,0,0,0,0,0,1,0,0,0,1},{0,0,0,0,0,0,0,0,0,0,0,1,1,0}}, ImageSize - 247, VertexSize -> {"Scaled", 0.1},
VertexLabels -> {1 -> Placed["a",Center], 2 -> Placed["b",Center], 3 -> Placed["c",Center], 4 -> Placed["d",Center], 5 -> Placed["e",Center], 6 -> Placed["f",Center], 7 -> Placed["g",Center], 
8 -> Placed["h",Center], 9 -> Placed["i",Center], 10 -> Placed["j",Center], 11 -> Placed["k",Center], 12 -> Placed["l",Center], 13 -> Placed["m",Center], 14 -> Placed["n",Center]}, 
VertexLabelStyle -> Directive[Black,17.5], EdgeLabelStyle -> Directive[Black,17.5,Bold], VertexStyle -> White, EdgeStyle -> {{Black,Thickness[0.005]}}];
g2 = AdjacencyGraph[{{0,0,0,1,1,0,0,0,0,0,0,0,0,0},{0,0,0,0,1,1,0,0,0,0,0,0,0,0},{0,0,0,0,0,1,1,0,0,0,0,0,0,0},{1,0,0,0,0,0,0,1,0,0,0,0,0,0},{1,1,0,0,0,0,0,0,1,0,0,0,0,0},
{0,1,1,0,0,0,0,0,0,1,0,0,0,0},{0,0,1,0,0,0,0,0,0,0,1,0,0,0},{0,0,0,1,0,0,0,0,0,0,0,1,0,0},{0,0,0,0,1,0,0,0,0,0,0,1,1,0},{0,0,0,0,0,1,0,0,0,0,0,0,1,1},{0,0,0,0,0,0,1,0,0,0,0,0,0,1},
{0,0,0,0,0,0,0,1,1,0,0,0,0,0},{0,0,0,0,0,0,0,0,1,1,0,0,0,0},{0,0,0,0,0,0,0,0,0,1,1,0,0,0}}, ImageSize -> 247];
IsomorphicGraphQ[g1, g2]

En la Figura vemos dos grafos isomórficos. Visualmente no lo aparentan, pero si obtenemos el primero como un grafo círculo con 13 nodos y luego le aplicamos la operación permutación de grafo con la permutación [0,2,4,6,8,10,12,1,3,5,7,9,11] obtenemos el segundo grafo, con lo que deben ser isomorfos pues uno es la permutación del otro.

Con el algoritmo isGraphIsomorphic() comprobamos que son isomórficos:

Time: 1 ms
Es el grafo isomórfico: [true,
"Canonical graphs are the same: 
0,11,0,12,1,3,1,5,2,4,2,6,3,4,5,
8,6,7,7,10,8,9,9,12,10,11"]

Un test de isomorfismos en 30 segundos comprueba que las 301959 primeras permutaciones son isomórficas ("isomorphic": 301959, "nonIsomorphic": 0).

Con este JSON puede importar el ejemplo.

{"nodes":[
    {"index":0,"nodeOffset":"2.5","parent":-1},
    {"index":1,"nodeOffset":"37.76 -20.42","parent":0},
    {"index":2,"nodeOffset":"35.42 -32.72","parent":1},
    {"index":3,"nodeOffset":"42.21 -39.82","parent":2},
    {"index":4,"nodeOffset":"39.9 -45.82","parent":3},
    {"index":5,"nodeOffset":"29.02 -55.06","parent":4},
    {"index":6,"nodeOffset":"12.07 -71.16","parent":5},
    {"index":7,"nodeOffset":"-7.07 -96.16","parent":6},
    {"index":8,"nodeOffset":"-24.02 -130.06","parent":7},
    {"index":9,"nodeOffset":"-34.9 -170.82","parent":8},
    {"index":10,"nodeOffset":"-37.21 -214.82","parent":9},
    {"index":11,"nodeOffset":"-30.42 -257.72","parent":10},
    {"index":12,"nodeOffset":"-32.76 -20.42","parent":[0,11]}
],
"config":{
    "algorithm":"Is graph isomorphic",
    "adjacencyMatrix":"0 0 0 0 0 0 1 1 0 0 0 0 0\n0 0 0 0 0 0 0 1 1 0 0 0 0\n0 0 0 0 0 0 0 0 1 1 0 0 0\n0 0 0 0 0 0 0 0 0 1 1 0 0\n0 0 0 0 0 0 0 0 0 0 1 1 0\n0 0 0 0 0 0 0 0 0 0 0 1 1\n1 0 0 0 0 0 0 0 0 0 0 0 1\n1 1 0 0 0 0 0 0 0 0 0 0 0\n0 1 1 0 0 0 0 0 0 0 0 0 0\n0 0 1 1 0 0 0 0 0 0 0 0 0\n0 0 0 1 1 0 0 0 0 0 0 0 0\n0 0 0 0 1 1 0 0 0 0 0 0 0\n0 0 0 0 0 1 1 0 0 0 0 0 0",
    "methodIsomorphic":"McKay",
    "useMcrBreak":true
}}

{"nodes":[
    {"index":0,"nodeOffset":"38.21","parent":-1},
    {"index":1,"nodeOffset":"42.52 4.58","parent":-1},
    {"index":2,"nodeOffset":"42.56 17.28","parent":-1},
    {"index":3,"nodeOffset":"35.07 35.18","parent":-1},
    {"index":4,"nodeOffset":"18.47 54.18","parent":-1},
    {"index":5,"nodeOffset":"-6.69 69.94","parent":-1},
    {"index":6,"nodeOffset":"49.57 53.84","parent":0},
    {"index":7,"nodeOffset":"17.93 53.84","parent":[0,1]},
    {"index":8,"nodeOffset":"-11.52 44.94","parent":[1,2]},
    {"index":9,"nodeOffset":"-34.9 29.18","parent":[2,3]},
    {"index":10,"nodeOffset":"-49.71 10.18","parent":[3,4]},
    {"index":11,"nodeOffset":"-55.42 -7.72","parent":[4,5]},
    {"index":12,"nodeOffset":"-53.59 -20.42","parent":[5,6]}
],
"config":{}}

0 0 0 0 0 0 1 1 0 0 0 0 0
0 0 0 0 0 0 0 1 1 0 0 0 0
0 0 0 0 0 0 0 0 1 1 0 0 0
0 0 0 0 0 0 0 0 0 1 1 0 0
0 0 0 0 0 0 0 0 0 0 1 1 0
0 0 0 0 0 0 0 0 0 0 0 1 1
1 0 0 0 0 0 0 0 0 0 0 0 1
1 1 0 0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0 0 0 0
0 0 1 1 0 0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0 0 0 0 0 0
0 0 0 0 1 1 0 0 0 0 0 0 0
0 0 0 0 0 1 1 0 0 0 0 0 0

En la Figura vemos que en Wolfram también se obtiene que son isomórficos usando IsomorphicGraphQ[g1, g2]. Observe que el código que usamos para exportar no incluye la posición de los nodos en el plano, viendo que Wolfram posiciona también el segundo formando un círculo y no una estrella tal como hicimos nosotros.

g1 = AdjacencyGraph[{{0,1,0,0,0,0,0,0,0,0,0,0,1},{1,0,1,0,0,0,0,0,0,0,0,0,0},{0,1,0,1,0,0,0,0,0,0,0,0,0},{0,0,1,0,1,0,0,0,0,0,0,0,0},{0,0,0,1,0,1,0,0,0,0,0,0,0},{0,0,0,0,1,0,1,0,0,0,0,0,0},
{0,0,0,0,0,1,0,1,0,0,0,0,0},{0,0,0,0,0,0,1,0,1,0,0,0,0},{0,0,0,0,0,0,0,1,0,1,0,0,0},{0,0,0,0,0,0,0,0,1,0,1,0,0},{0,0,0,0,0,0,0,0,0,1,0,1,0},{0,0,0,0,0,0,0,0,0,0,1,0,1},
{1,0,0,0,0,0,0,0,0,0,0,1,0}}, ImageSize -> 160, VertexSize -> {"Scaled", 0.12}, VertexLabels -> {1 -> Placed[0,Center], 2 -> Placed[1,Center], 3 -> Placed[2,Center], 4 -> Placed[3,Center], 
5 -> Placed[4,Center], 6 -> Placed[5,Center], 7 -> Placed[6,Center], 8 -> Placed[7,Center], 9 -> Placed[8,Center], 10 -> Placed[9,Center], 11 -> Placed[10,Center], 12 -> Placed[11,Center], 
13 -> Placed[12,Center]}, VertexLabelStyle -> Directive[Black,9], EdgeLabelStyle -> Directive[Black,9,Bold], VertexStyle -> White, EdgeStyle -> {{Black,Thickness[0.005]}}];
g2 = AdjacencyGraph[{{0,0,0,0,0,0,1,1,0,0,0,0,0},{0,0,0,0,0,0,0,1,1,0,0,0,0},{0,0,0,0,0,0,0,0,1,1,0,0,0},{0,0,0,0,0,0,0,0,0,1,1,0,0},{0,0,0,0,0,0,0,0,0,0,1,1,0},
{0,0,0,0,0,0,0,0,0,0,0,1,1},{1,0,0,0,0,0,0,0,0,0,0,0,1},{1,1,0,0,0,0,0,0,0,0,0,0,0},{0,1,1,0,0,0,0,0,0,0,0,0,0},{0,0,1,1,0,0,0,0,0,0,0,0,0},{0,0,0,1,1,0,0,0,0,0,0,0,0},
{0,0,0,0,1,1,0,0,0,0,0,0,0},{0,0,0,0,0,1,1,0,0,0,0,0,0}}, ImageSize -> 160];
IsomorphicGraphQ[g1, g2]