Permutaciones en grafos

Si tenemos el grafo G con matriz de adyacencia A con n nodos y una permutación del conjunto de índices M = {0, 1, 2,..., n-1} que genera la matriz permutación P, siendo P^⊤ su matriz transpuesta, decimos que G_p es una permutación del grafo G con matriz de adyacencia A_p como el resultado de la operación:

Permutar un grafo supone permutar sus vértices manteniendo las relaciones de aristas, tal que si tenemos dos vértices "u" y "v" y al permutarlos obtenemos "p(u)" y "p(v)", existirá una arista entre estos "p(u)-p(v)" si y solo si existe la arista "u-v".

Un grafo y sus permutaciones son isomórficos. Conocer como permutar un grafo es básico para implementar algoritmos para saber si dos grafos son isomórficos, como el algoritmo isGraphIsomorphic() que puede encontrar en la sección de algoritmos que explicaremos en un tema posterior.

Ya expusimos lo anterior al comentar la operación operatePermuteGraph(), que en la aplicación Grafos SVG nos permite obtener las permutaciones de un grafo, explicándose en ese tema con detalle como se obtiene la permutación de un grafo.

Veamos el siguiente JSON de ejemplo para un grafo inicial:

{"nodes":[
    {"index":0,"nodeColor":"lightpink","parent":[{"index":-1}]},
    {"index":1,"nodeColor":"lightblue","parent":[{"index":0}]},
    {"index":2,"nodeColor":"lightgreen","parent":[{"index":0}]}
],
"config":{}}

Si importamos en la aplicación el JSON obtendremos el primero que vemos en la Figura. Exportando su matriz de adyacencia nos dará [[0,1,1],[1,0,0],[1,0,0]]. Vamos a aplicar todas las permutaciones que vimos antes a este grafo con la operación operatePermuteGraph(), que nos devuelve un objeto como {"error":"","matrix":[[0,0,1],[0,0,1],[1,1,0]],"edges":[],"permutation":[[0,0,1],[0,1,0],[1,0,0]]}, donde vemos en "matrix" la matriz de adyacencia permutada y en "permutation" la matriz permutación. Por ahora solo nos interesan las matrices permutadas que, tras obtenerlas todas y agruparlas por similitud, relacionamos a continuación:

Permutación  Matriz adyacencia permutada
--------------------------------------
[0,1,2]      [[0,1,1],[1,0,0],[1,0,0]]
[0,2,1]      [[0,1,1],[1,0,0],[1,0,0]]
--------------------------------------
[1,0,2]      [[0,1,0],[1,0,1],[0,1,0]]
[2,0,1]      [[0,1,0],[1,0,1],[0,1,0]]
--------------------------------------
[1,2,0]      [[0,0,1],[0,0,1],[1,1,0]]
[2,1,0]      [[0,0,1],[0,0,1],[1,1,0]]

En la Figura vemos estos 6 grafos, cuyos JSON se exponen a continuación.

Permutaciones: [0,1,2], [0,2,1]
Matriz: [[0,1,1],[1,0,0],[1,0,0]]

{"nodes":[
    {"index":0,"nodeColor":"lightpink","parent":[{"index":-1}]},
    {"index":1,"nodeColor":"lightblue","parent":[{"index":0}]},
    {"index":2,"nodeColor":"lightgreen","parent":[{"index":0}]}
],
"config":{}}

{"nodes":[
    {"index":0,"nodeColor":"lightpink","parent":[{"index":-1}]},
    {"index":1,"nodeColor":"lightblue","nodeOffset":"33.34","parent":[{"index":0}]},
    {"index":2,"nodeColor":"lightgreen","nodeOffset":"-33.34","parent":[{"index":0}]}
],
"config":{}}

Permutaciones: [1,0,2], [2,0,1]
Matriz: [[0,1,0],[1,0,1],[0,1,0]]

{"nodes":[
    {"index":0,"nodeOffset":"-16.67 25","nodeColor":"lightpink","parent":[{"index":-1}]},
    {"index":1,"nodeOffset":"0 -25","nodeColor":"lightblue","parent":[{"index":0}]},
    {"index":2,"nodeOffset":"16.67 -25","nodeColor":"lightgreen","parent":[{"index":1}]}
],
"config":{}}

{"nodes":[
    {"index":0,"nodeOffset":"16.67 25","nodeColor":"lightpink","parent":[{"index":-1}]},
    {"index":1,"nodeOffset":"0 -25","nodeColor":"lightblue","parent":[{"index":0}]},
    {"index":2,"nodeOffset":"-16.67 -25","nodeColor":"lightgreen","parent":[{"index":1}]}
],
"config":{}}

Permutaciones: [1,2,0], [2,1,0]
Matriz: [[0,0,1],[0,0,1],[1,1,0]]

{"nodes":[
    {"index":0,"nodeOffset":"0 25","nodeColor":"lightpink","parent":[{"index":-1}]},
    {"index":1,"nodeOffset":"0 25","nodeColor":"lightblue","parent":[{"index":-1}]},
    {"index":2,"nodeOffset":"0 -25","nodeColor":"lightgreen","parent":[{"index":0},{"index":1}]}
],
"config":{}}

{"nodes":[
    {"index":0,"nodeOffset":"33.34 25","nodeColor":"lightpink","parent":[{"index":-1}]},
    {"index":1,"nodeOffset":"-33.34 25","nodeColor":"lightblue","parent":[{"index":-1}]},
    {"index":2,"nodeOffset":"0 -25","nodeColor":"lightgreen","parent":[{"index":0},{"index":1}]}
],
"config":{}}

El grafo inicial tiene los vértices V = {0, 1, 2}. Las permutaciones de estos vértices son P = {{0, 1, 2}, {0, 2, 1}, {1, 0, 2}, {1, 2, 0}, {2, 0, 1}, {2, 1, 0}}, con total de permutaciones P(n) = n! = 3! = 6, como podemos obtener en la aplicación Combine Tools. Sin embargo la restricción de conservar la conectividad de las aristas hace que algunas de ellas conduzcan a un mismo grafo permutado.

En la Figura vemos el grafo inicial y sus permutaciones que se corresponden con la lista de permutaciones del párrafo anterior. La primera permutación {0, 1, 2} es la identidad que no modifica el grafo inicial. Viendo la segunda permutación P₂ ={0, 2, 1} es la aplicación p(0)=0, p(1)=2, p(2)=1 de tal forma que las aristas iniciales 0-1, 0-2 ahora son p(0)-p(1), p(0)-p(2) lo que equivale a 0-2, 0-1 que vemos en el segundo grafo de la Figura. Observe que la lista de aristas iniciales era 0-1, 0-2 y ahora tras la permutación sigue siendo la misma lista. Así que estos dos primeros grafos tienen la misma lista de aristas y, por tanto la misma matriz de adyacencia. Como adelanto que luego explicaremos, podemos decir que el segundo grafo es un automorfismo con respecto al primero, que no es otra cosa que una simetría que no modifica la matriz de adyacencia.

Veamos la tercera permutación P₃ ={1, 0, 2} que es la aplicación p(0)=1, p(1)=0, p(2)=2, de tal forma que las aristas 1-0, 0-2 en el grafo inicial son ahora p(1)-p(0), p(0)-p(2) lo que equivale a 0-1, 1-2 tal como vemos en el tercer grafo de la Figura. Podemos adelantar que este tercer grafo es un isomorfismo con respecto al primero. Y el cuarto es un automorfismo con respecto al tercero. De hecho todos los grafos anteriores son isomórficos. Y en cada línea son automórficos. Veamos esto en los siguientes apartados.

Isomorfismos en grafos

Sean dos grafos G y H con vértices V_n = {0, 1, ..., n-1} y con aristas E(G) y E(H). Decimos que G y H son isomórficos si hay una permutación p de los vértices V_n tal que la arista {u, v} está en E(G) si y solo si {p(u), p(v)} está en E(H). O dicho en otras palabras, dos grafos con el mismo número de vértices conectados de la misma forma se dice que son isomórficos.

En la Figura vemos dos grafos isomórficos. El segundo es el que se corresponde con la permutación [3, 0, 4, 1, 2] que aplica p(0)=3, p(1)=0, p(2)=4, p(3)=1, p(4)=2. Observe por ejemplo que la arista 3-4 en el permutado equivale a 1-2 en el original dadas las permutaciones p(3)=1, p(4)=2, con lo que no sólo se permutan los nodos sino que además se mantienen las aristas. Con los siguientes JSON puede importar esos dos grafos:

{"nodes":[
    {"index":0,"nodeColor":"lightpink","parent":[{"index":-1}]},
    {"index":1,"nodeColor":"lightcyan","parent":[{"index":0}]},
    {"index":2,"nodeColor":"lightgreen","parent":[{"index":0},{"index":1}]},
    {"index":3,"nodeColor":"beige","parent":[{"index":1},{"index":4}]},
    {"index":4,"nodeColor":"gold","parent":[{"index":1},{"index":2}]}
],
"config":{}}

{"nodes":[
    {"index":0,"nodeOffset":"0 50","nodeColor":"lightpink","parent":[{"index":-1}]},
    {"index":1,"nodeOffset":-16.67,"nodeColor":"lightcyan","parent":[{"index":-1}]},
    {"index":2,"nodeOffset":"41.67 25","nodeColor":"lightgreen","parent":[{"index":0}]},
    {"index":3,"nodeOffset":-16.67,"nodeColor":"beige","parent":[{"index":0},{"index":1},{"index":2}]},
    {"index":4,"nodeOffset":-8.33,"nodeColor":"gold","parent":[{"index":1},{"index":2},{"index":3}]}
],
"config":{}}

En la aplicación posicionamos los nodos de la permutación con las posiciones de las imágenes en el grafo inicial, con lo que visualmente vemos que se mantiene la misma relación de aristas tras permutar todos los nodos, lo que hacemos con la operación para permutar un grafo operatePermuteGraph(), usando la permutación [3, 0, 4, 1, 2] obteniéndose el siguiente resultado:

{"error":"",
"matrix":[[0,0,1,1,0],[0,0,0,1,1],[1,0,0,1,1],[1,1,1,0,1],[0,1,1,1,0]],
"edges":[],
"permutation":[[0,0,0,1,0],[1,0,0,0,0],[0,0,0,0,1],[0,1,0,0,0],[0,0,1,0,0]]}

En este caso se observa que ambas matrices de adyacencia son distintas:

Inicial:
0 1 1 0 0
1 0 1 1 1
1 1 0 0 1
0 1 0 0 1
0 1 1 1 0
Permutaciones [3,0,4,1,2] o [0,3,2,1,4]
0 0 1 1 0
0 0 0 1 1
1 0 0 1 1
1 1 1 0 1
0 1 1 1 0

Con 5 nodos hay 5! = 120 permutaciones, tal como podemos obtener en la aplicación Combine Tools, obteniéndose una lista de permutaciones en forma compacta como la siguiente:

01234, 10234, 02134, 20134, 21034, 12034, 01324, 10324, 03124, 30124, 31024, 13024, 03214,
30214, 02314, 20314, 23014, 32014, 31204, 13204, 32104, 23104, 21304, 12304, 01243, 10243,
02143, 20143, 21043, 12043, 01423, 10423, 04123, 40123, 41023, 14023, 04213, 40213, 02413,
20413, 24013, 42013, 41203, 14203, 42103, 24103, 21403, 12403, 01432, 10432, 04132, 40132,
41032, 14032, 01342, 10342, 03142, 30142, 31042, 13042, 03412, 30412, 04312, 40312, 43012,
34012, 31402, 13402, 34102, 43102, 41302, 14302, 04231, 40231, 02431, 20431, 24031, 42031,
04321, 40321, 03421, 30421, 34021, 43021, 03241, 30241, 02341, 20341, 23041, 32041, 34201,
43201, 32401, 23401, 24301, 42301, 41230, 14230, 42130, 24130, 21430, 12430, 41320, 14320,
43120, 34120, 31420, 13420, 43210, 34210, 42310, 24310, 23410, 32410, 31240, 13240, 32140,
23140, 21340, 12340

Así que para saber si los dos grafos de la Figura son isomorfos podemos aplicar las permutaciones anteriores al primer grafo hasta que consigamos una que tenga la misma matriz de adyacencia que el segundo grafo. En este caso tenemos que llegar hasta la permutación resaltada en azul, o incluso antes con la resaltada en verde que también produce la misma matriz. O recorrerlas todas sin encontrar ninguna para deducir que no son isomorfos. Esta técnica es posible si no hay muchas permutaciones, pero por ejemplo, con un grafo con 10 nodos hay 10! = 3 628 800 permutaciones. Y con 20 nodos hay 20! ≈ 2.43×10¹⁸ permutaciones. Y esos números son computacionalmente impracticables, así que hay que plantear otro enfoque como veremos en un siguiente tema con el algoritmo de McKay que implementaremos con el algoritmo isGraphIsomorphic() para saber si dos grafos son isomorfos.

Si aplicamos otra permutación [3,1,4,0,2] obtenemos con operatePermuteGraph() la misma matriz de adyacencia que la original.

{"error":"",
"matrix":[[0,1,1,0,0],[1,0,1,1,1],[1,1,0,0,1],[0,1,0,0,1],[0,1,1,1,0]],
"edges":[],
"permutation":[[0,0,0,1,0],[0,1,0,0,0],[0,0,0,0,1],[1,0,0,0,0],[0,0,1,0,0]]}

Estos isomorfismos que no modifican la matriz de adyacencia son los automorfismos, que veremos a continuación.

Automorfismos en grafos

Un automorfismo de un grafo G es un isomorfismo consigo mismo, esto es, una aplicación desde los vértices de G a los propios vértices de G tal que el grafo resultante es isomorfo con G.

Otra forma de decirlo es que un automorfismo es una forma de simetría en la cuál el grafo se mapea sobre sí mismo mientras se preserva la conectividad arista-vértice. Y esto conecta con lo que vimos en el apartado anterior, que un automorfismo es un isomorfirsmo donde la matriz permutada es la misma que la inicial.

El grafo estrella (star) S₄ de 4 nodos de la Figura tiene 6 simetrías, el primero el propio grafo original y las otras 5 son reflexiones y rotaciones de los nodos radiales {0, 1, 2}, habiendo en total las permutaciones de estos 3 nodos 3! = 6. Para cualquier grafo estrella S_n con n≥3 sucede que tiene (n-1)! simetrías. Cada tipo de grafo tendrá su propio cálculo de simetrías dependiendo de como se estructura.

Con este JSON puede importar el primer grafo inicial, cuya matriz de adyacencia es [[0,0,0,1],[0,0,0,1],[0,0,0,1],[1,1,1,0]]

{"nodes":[
    {"index":0,"nodeOffset":"17.5 8.83","nodeColor":"lightcyan","parent":[{"index":-1}]},
    {"index":1,"nodeOffset":"10.83 40.58","nodeColor":"lightgreen","parent":[{"index":-1}]},
    {"index":2,"nodeOffset":"-50.83 40.58","nodeColor":"beige","parent":[{"index":-1}]},
    {"index":3,"nodeOffset":"-7.5 5","nodeColor":"lightpink","parent":[{"index":0},{"index":2},{"index":1}]}
],
"config":{}}

Los cinco grafos anteriores que siguen al inicial son la aplicación de las permutaciones [0,2,1,3], [1,0,2,3], [1,2,0,3], [2,0,1,3], [2,1,0,3] usado la operación operatePermuteGraph() para permutar el primer grafo. Estos son los resultados obtenidos, observando que el campo "matrix" es igual en todo los casos, con lo que aplicar estas permutaciones no modifica la matriz de adyacencia del grafo.

Permutación [0,2,1,3]
{"error":"","matrix":[[0,0,0,1],[0,0,0,1],[0,0,0,1],[1,1,1,0]],"edges":[],"permutation":[[1,0,0,0],[0,0,1,0],[0,1,0,0],[0,0,0,1]]}

Permutación [1,0,2,3]
{"error":"","matrix":[[0,0,0,1],[0,0,0,1],[0,0,0,1],[1,1,1,0]],"edges":[],"permutation":[[0,1,0,0],[1,0,0,0],[0,0,1,0],[0,0,0,1]]}

Permutación [1,2,0,3]
{"error":"","matrix":[[0,0,0,1],[0,0,0,1],[0,0,0,1],[1,1,1,0]],"edges":[],"permutation":[[0,1,0,0],[0,0,1,0],[1,0,0,0],[0,0,0,1]]}

Permutación [2,0,1,3]
{"error":"","matrix":[[0,0,0,1],[0,0,0,1],[0,0,0,1],[1,1,1,0]],"edges":[],"permutation":[[0,0,1,0],[1,0,0,0],[0,1,0,0],[0,0,0,1]]}

Permutación [2,1,0,3]
{"error":"","matrix":[[0,0,0,1],[0,0,0,1],[0,0,0,1],[1,1,1,0]],"edges":[],"permutation":[[0,0,1,0],[0,1,0,0],[1,0,0,0],[0,0,0,1]]}

En la aplicación podemos hacer ajustes visuales como reflejar y rotar, como vemos en la Figura, panel que se accede con el botón . Los ajustes visuales modifican la presentación del grafo pero no la matriz de adyacencia.

1 Grafo inicial
2 Reflejar (1) horizontal
3 Rotar (2) 120º
4 Rotar (1) 240º
5 Rotar (1) 120º
6 Rotar (2) 240º

Podemos obtener las simetrías de la Figura aplicando reflexión y rotación, como por ejemplo las que se adjuntan. Y como hemos dicho, estas simetrías son los automorfismos del grafo. La cuestión es ver como podemos obtener todos los automorfismos de un grafo.

El conjunto de todos los automorfismos de un grafo define un grupo de automorfismos denominado Aut(G), constituyéndose como un grupo de permutaciones, algo que vimos cuando hablamos de las permutaciones cíclicas. Como vimos en ese tema, un grupo de permutaciones dispone de una operación de composición o producto de permutaciones cuyo resultado es otra permutación del grupo, operación no necesariamente conmutativa. Como grupo dispone de un elemento neutro (permutación identidad) y de una operación inversa de permutación.

"automorphisms":
[[[0],[1,2],[3]],
[[0,1],[2],[3]],
[[0,1,2],[3]],
[[0,2,1],[3]],
[[0,2],[1],[3]]]

Cuando veamos en un tema siguiente el algoritmo getPartitionTree() que nos permite obtener el árbol de particiones con el algoritmo de McKay, podemos obtener todos los automorfismos del grafo como estos cinco adjuntos, al que habría que incluir la permutación identidad [[0],[1],[2],[3]], con lo que tendríamos las seis simetrías que comentábamos más arriba, que son las mismas permutaciones pero en notación cíclica, tal como explicamos a continuación.

En la serie de temas sobre combinatoria vimos que una permutación cíclica es una permutación que fija cero o más elementos y mueve el resto de forma cíclica. En el tema siguiente de esa serie hablábamos sobre la notación de permutaciones cíclicas, explicando además el funcionamiento de la herramienta calculara permutaciones cíclicas de la aplicación Combine Tools.

Para manejar esa calculadora primero incluimos la lista de elementos (conjunto M), que para nuestro caso es el conjunto de vértices M = {0, 1, 2, 3}.

Una permutación como [0,2,1,3] se maneja en notación 1 línea como 0 2 1 3. Y en notación cíclica como (0)(1 2)(3), que también podemos ocultar los puntos fijos siendo simplemente como (1 2). La permutación (0)(1 2)(3) la manejamos con JavaScript como [[0],[1,2],[3]] usando arrays. En la Figura vemos como podemos convertir entre notaciones. Estas 6 permutaciones forman un grupo de permutaciones con la operación producto de permutaciones. Así el producto de dos cualesquiera es otra permutación del grupo. Por ejemplo (1 2) × (0 1) = (0 2 1). En la tabla siguiente se calculan todos los productos, observando que el resultado es siempre un elemento del grupo.

En la Figura vemos en Wolfram el grafo inicial y la obtención del grupo de permutaciones usando GraphAutomorphismGroup[g] y a continuación GroupElements[%], observando que son los mismos automorfismos que obtuvimos si consideramos que Wolfram inicia los índices en 1 y nosotros en 0. En formato texto esto es lo que devuelve Wolfram:

PermutationGroup[{Cycles[{{2,3}}],Cycles[{{1,2}}]}]

{Cycles[{}], Cycles[{{2,3}}], Cycles[{{1,2}}], Cycles[{{1,2,3}}], Cycles[{{1,3,2}}],
Cycles[{{1,3}}]}

PermutationGroup[p₁, ..., p_n] representa el grupo generado por productos de las permutaciones p₁, ..., p_n, denominándose conjunto fuerte de generación que se obtiene con el algoritmo de Schreir-Sims. Así los elementos del grupo de permutaciones en notación cíclica {{}}, {{2,3}}, {{1,2}}, {{1,2,3}}, {{1,3,2}}, {{1,3}} en Wolfram, que equivale a las nuestras (), (1 2), (0 1), (0 1 2), (0 2 1), (0 2), puede ser generado sólo con productos de (1 2) y (0 1) y sus resultados. Obtener ese subconjunto mínimo generador no es fácil y no se contempla en la aplicación de grafos.

Este es el código para la ejecución en Wolfram Cloud:

g = AdjacencyGraph[{{0,0,0,1},{0,0,0,1},{0,0,0,1},{1,1,1,0}}, ImageSize -> 186, VertexSize -> {"Scaled", 0.17}, VertexLabels -> {1 -> Placed[0,Center], 2 -> Placed[1,Center], 
3 -> Placed[2,Center], 4 -> Placed[3,Center]}, VertexLabelStyle -> Directive[Black,17.5], EdgeLabelStyle -> Directive[Black,17.5,Bold], 
VertexStyle -> {1 -> LightCyan,2 -> LightGreen,3 -> RGBColor["beige"],4 -> RGBColor["lightpink"]}, EdgeStyle -> {{Black,Thickness[0.005]}}]
GraphAutomorphismGroup[g]
GroupElements[%]
    

Al final del apartado anterior dijimos que si aplicamos la permutación [3,1,4,0,2] al grafo de la izquierda de la Figura obtenemos con operatePermuteGraph() la misma matriz de adyacencia que la del grafo inicial, con el siguiente resultado:

{"error":"",
"matrix":[[0,1,1,0,0],[1,0,1,1,1],[1,1,0,0,1],[0,1,0,0,1],[0,1,1,1,0]],
"edges":[],
"permutation":[[0,0,0,1,0],[0,1,0,0,0],[0,0,0,0,1],[1,0,0,0,0],[0,0,1,0,0]]}

Con estos JSON puede importar los grafos de la Figura.

{"nodes":[
    {"index":0,"nodeColor":"lightpink","parent":[{"index":-1}]},
    {"index":1,"nodeColor":"lightcyan","parent":[{"index":0}]},
    {"index":2,"nodeColor":"lightgreen","parent":[{"index":0},{"index":1}]},
    {"index":3,"nodeColor":"beige","parent":[{"index":1},{"index":4}]},
    {"index":4,"nodeColor":"gold","parent":[{"index":1},{"index":2}]}
],
"config":{}}

{"nodes":[
    {"index":0,"nodeColor":"lightpink","nodeOffset":"-16.67 50","parent":[{"index":-1}]},
    {"index":1,"nodeColor":"lightcyan","parent":[{"index":0}]},
    {"index":2,"nodeColor":"lightgreen","nodeOffset":"0 25","parent":[{"index":0},{"index":1}]},
    {"index":3,"nodeColor":"beige","nodeOffset":"16.67 -50","parent":[{"index":1},{"index":4}]},
    {"index":4,"nodeColor":"gold","nodeOffset":"0 -25","parent":[{"index":1},{"index":2}]}
],
"config":{}}

Resulta que ese grafo sólo tiene un automorfismo que esa esa permutación [3,1,4,0,2] (a excepción de la identidad), que en notación cíclica es [[0,3],[1],[2,4]] o puesto en la notación usual (0 3)(2 4). Eso quiere decir que itercambiando los nodos "0" y "3" por un lado y "2" y "4" por otro obtendremos un grafo automorfo con la misma matriz de adyacencia, como vemos a la derecha de la Figura. Se corresponde con un ajuste visual mediante una reflexión vertical y reposicionando los nodos "3" y "4" con las posiciones previas de "0" y "2" respectivamente. Estos ajustes visuales en la aplicación no modifican la matriz de adyacencia.

Si ejecutamos el algoritmo getPartitionTree() podemos obtener los automorfismos, que resulta ser, aparte de la permutación identidad que es obvia, precisamente ese único que hemos comentado, obteniéndose "automorphisms": [[[0,3],[1],[2,4]]].

En la Figura vemos que en Wolfram con GraphAutomorphismGroup[g] y GroupElements[%] se obtiene el mismo autormorfismo (aparte de la identidad), recordando que los índices en Wolfram se inician en 1.

g = AdjacencyGraph[{{0,1,1,0,0},{1,0,1,1,1},{1,1,0,0,1},{0,1,0,0,1},{0,1,1,1,0}}, ImageSize -> 188, VertexSize -> {"Scaled", 0.17}, 
VertexLabels -> {1 -> Placed[0,Center], 2 -> Placed[1,Center], 3 -> Placed[2,Center], 4 -> Placed[3,Center], 5 -> Placed[4,Center]}, 
VertexLabelStyle -> Directive[Black,17.5], EdgeLabelStyle -> Directive[Black,17.5,Bold], VertexStyle -> {1 -> RGBColor["lightpink"],2 -> LightCyan,
3 -> LightGreen,4 -> RGBColor["beige"],5 -> RGBColor["gold"]}, EdgeStyle -> {{Black,Thickness[0.005]}}];
GraphAutomorphismGroup[g]
GroupElements[%]

Vimos que un grafo estrella con n≥3 tenía Aut(G) = (n-1)! automorfismos. Los grafos completos tienen Aut(G) = n! El número de automorfismos dependerá de cada grafo, como vemos en la página Graph Automorphism de Wolfram MathWorld. Pero puede haber grafos sin automorfismos, como veremos a continuación.

En la Figura vemos un grafo sin automorfismos a excepción de la identidad, tal como podemos verificar ejecutando getPartitionTree(). Se expone en la presentación 55 Years of Graph Isomorphism Testing de Brendan McKay, que puede importar con el siguiente JSON:

{"nodes":[
    {"index":0,"nodeOffset":"16.13 23.42","parent":[{"index":-1}]},
    {"index":1,"nodeOffset":"22.12 9.71","parent":[{"index":0}]},
    {"index":2,"nodeOffset":"24.74 15.64","parent":[{"index":0}]},
    {"index":3,"nodeOffset":"24.19 3.06","parent":[{"index":1}]},
    {"index":4,"nodeOffset":"17.63 5.31","parent":[{"index":2},{"index":3}]},
    {"index":5,"nodeOffset":"24.05 10.55","parent":[{"index":0}]},
    {"index":6,"nodeOffset":"48.51 -8.68","parent":[{"index":4}]},
    {"index":7,"nodeOffset":"66.57 -20.98","parent":[{"index":6},{"index":5}]},
    {"index":8,"nodeOffset":"41.84 -20.65","parent":[{"index":5}]},
    {"index":9,"nodeOffset":"50.17 17.29","parent":[{"index":8}]},
    {"index":10,"nodeOffset":"-8.54 -26.62","parent":[{"index":6}]},
    {"index":11,"nodeOffset":"38.63 -18.04","parent":[{"index":10},{"index":9}]},
    {"index":12,"nodeOffset":"-23.78 -35.53","parent":[{"index":7},{"index":9}]},
    {"index":13,"nodeOffset":"-25.17 -72.95","parent":[{"index":12},{"index":3}]},
    {"index":14,"nodeOffset":"-34.48 -81.02","parent":[{"index":13},{"index":11}]},
    {"index":15,"nodeOffset":"-34.48 -153.72","parent":[{"index":14},{"index":10},{"index":8,"lineType":"quadratic","lineOffset":"0 -11.65"}]}
],
"config":{}}

En Wolfram vemos que también no encuentra autormorfismos, a excepción de la identidad.

g = AdjacencyGraph[{{0,1,1,0,0,1,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},{1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0},{0,1,0,0,1,0,0,0,0,0,0,0,0,1,0,0},
{0,0,1,1,0,0,1,0,0,0,0,0,0,0,0,0},{1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0},{0,0,0,0,1,0,0,1,0,0,1,0,0,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,0,0,0,1,0,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,1,0,0,0,0,1,0,0,0,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,0,1,0,0,0,1,0,0},{0,0,0,1,0,0,0,0,0,0,0,0,1,0,1,0},
{0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,1},{0,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0}}, ImageSize -> 300, VertexSize -> {"Scaled", 0.08}, 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]}, VertexLabelStyle -> Directive[Black,17.5], EdgeLabelStyle -> Directive[Black,17.5,Bold], VertexStyle -> White, EdgeStyle -> {{Black,Thickness[0.005]}}];
GraphAutomorphismGroup[g]
GroupElements[%]

Cuando presentemos el algoritmo de McKay veremos la importancia de encontrar autormorfismos, pues nos permitirán recortar la búsqueda cuando chequeemos si dos grafos son isomorfos.