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 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 imagen 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.

Para verificar la corrección del algoritmo de McKay en nuestra implementación, usamos el algoritmo testIsomorphisms() como se observa en la imagen, algoritmo que nos permite verificar que la obtención del etiquetado canónico es correcta. Se trata de obtener el etiquetado canónico del grafo y luego permutarlo aleatoriamente tantas veces como especifique el campo número de tests, aunque limitado con el campo tiempo total tests (segundos), pues cuando se supere ese tiempo finalizará devolviendo los resultados alcanzados. Con cada permutación del grafo se obtiene su etiquetado canónico y se comprueba que sea igual que el del grafo original. En un tema anterior ya habíamos comprobado la corrección con la poda con automorfismos usando un conjunto de grafos de ejemplo. Y ahora en este tema comprobamos la corrección usando indicadores.

En los temas anteriores vimos la poda con automorfismos en el algoritmo de McKay, que simplificábamos con poda mcr de minimum cell representative. En algunos grafos es posible además aplicar una poda con indicadores que reduce mucho más el tamaño del árbol de particiones y, por tanto, de los tiempos de ejecución.

En la imagen vemos la ejecución del árbol de particiones con el grafo CFI con ejemplares de 200 a 460 vértices del grafo, midiendo el tamaño del árbol de particiones con el número de sus nodos (Size tree) en una escala logarítmica en base 10, donde valores como 1, 2, 3, 4, 5 significan 10, 100, 1000, 10000, 100000 nodos del árbol.

Con sólo poda automorfismos (mcr) tenemos la gráfica en color rojo, observando que para el último ejemplar de 460 vértices necesita un árbol de particiones con 13868 nodos (4.14 en el eje logarítmico vertical). Mientras que agregando la poda indicadores (mcr + indicator) en la gráfica en azul se reducen los nodos del árbol hasta 2232 nodos (3.35 en valor logarítmico). Esto supone una reducción de casi un 84% en número de nodos del árbol, algo que que se traduce en tiempos de ejecución, pues el tamaño del árbol de particiones es proporcional al tiempo de ejecución.

El objetivo principal del algoritmo de McKay con la implementación que llevo a cabo con getPartitionTree() es obtener el etiquetado canónico del grafo que se devuelve en el campo canonicalLabel del resultado. Pero también esta implementación me sirve para analizar y trazar la ejecución del árbol de particiones, automorfismos y cómo las opciones de ejecución pueden modificar el resultado.

Para ver esto último tomaremos el grafo de Miyazaki de 40 nodos que se observa en la imagen. El árbol de menor tamaño con 76 nodos se consigue con las opciones de ejecución orden refinamiento neighbors-desc-lengths-desc y celda objetivo max-joins, siendo el de mayor tamaño con 343 nodos con neighbors-asc-lengths-desc y min-length-last respectivamente.

En el tema anterior explicamos que con el algoritmo de McKay en aquellos grafos donde la primera hoja es la canónica ("f*") y las siguientes son todas iguales ("="), podábamos con automorfismos usando el campo "mcr" (MCR: minimum cell representative, representante mínimo de celda). Sin embargo cuando eso no sucede hay que usar otra técnica. Como ejemplo vemos el grafo Steiner Triple System (STS-13) con 26 nodos, donde hay que aplicar otra técnica que denominaremos reconstruir el MCR.

La teoría del algoritmo de McKay nos dice que si μ₁ y μ₂ son hojas del árbol de particiones donde se encuentra el automorfismo γ tal μ₂ = (μ₁)^γ, entonces γ mapea el subárbol descendente de μ₁ en el árbol descendente de μ₂. Así que cualquier etiquetado descendente de μ₂ es igual que alguno descendente de μ₁, con lo que se puede podar la rama del subárbol que descienda de ese nodo. Esto es lo que se entiende como poda con automorfismos

En la imagen vemos un grafo y su árbol de particiones obtenido con el refinamiento que vimos en el apartado anterior. Las ramas en colores se podan con automorfismos, reduciendo significativamente el tamaño del árbol.

El algoritmo de McKay tiene como objetivo obtener un etiquetado canónico de un grafo, etiquetado que es el mismo para todos los grafos que sean isomorfos. Así cuando ese etiquetado en dos grafos coincide entonces serán isomorfos.

En la imagen vemos el comportamiento del algoritmo de McKay en nuestra aplicación Grafos SVG para el grafo corona para tamaños pares desde 4 a 30 nodos tal como vemos en el eje horizontal. En el eje vertical se presentan los tamaños del árbol de particiones en escala logarítmica, así que los valores "y" de ese eje se corresponden con tamaños 10^y nodos del árbol de particiones. La técnica del refinamiento (refine) reduce el tamaño del árbol. Y si ademas aplcicamos la poda con automorfismos (mcr) se reduce hasta conseguir un comportamiento polinómico.

El primer paso para explicar el algoritmo de McKay, o al menos mi particular implementación, es ver como generamos el árbol de particiones para obtener todas las permutaciones del grafo, de donde localizaremos el etiquetado canónico (canonical label) para ese grafo. Usaremos un grafo estrella de 3 nodos con el que obtendremos un árbol de particiones con 10 nodos de los cuáles sus 6 hojas son las permutaciones del grafo.

El método de fuerza bruta para saber si dos grafos son isomorfos se basa en ir obteniendo las permutaciones del primer grafo hasta que consigamos una permutación cuya matriz de adyacencia sea igual que la del segundo grafo. El algoritmo está limitado por el número de permutaciones, pues por ejemplo, con 10 nodos hay 10! = 3 628 800 permutaciones y con 20 nodos hay 20! ≈ 2.43×10¹⁸ permutaciones, lo que supone que sea computacionalmente impracticable a partir de 10 nodos, planteándose el algoritmo de McKay que veremos en estos temas para resolver este problema de isomorfismos.

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 de la aplicación Grafos SVG que explicaremos en un tema posterior.

Un clique en un grafo es un subconjunto de nodos tal que cada par de nodos está conectado. El tamaño de un clique es su número de nodos. Los de tamaño 1 son los propios nodos y los de tamaño 2 las aristas. Para obtenerlos buscamos todos los subgrafos inducidos que sean completos.

Además podemos buscar los cliques máximos y cliques maximales. Así como los anticliques que son conjuntos independientes de vértices no conectados. De igual forma buscamos todos los anticliques, los máximos y los maximales.

Implementamos en Grafos SVG algoritmos para obtener subgrafos, que son subconjuntos de nodos y aristas. En un grafo con n nodos definimos un subgrafo inducido al grafo resultante compuesto con k ≤ n nodos y todas sus aristas incidentes. Y de forma general definimos un subgrafo a un inducido tras lo cual eliminamos cero o más aristas. Mientras que un subgrafo recubridor al que contiene todos los n nodos y sólo algunas aristas del grafo original.

Encontrar los caminos mínimos en un grafo dirigido supone definir un nodo raíz y buscar los caminos al resto de nodos con suma de longitudes mínima. En principio se define para grafos dirigidos, pero luego veremos que también puede aplicarse a no dirigidos. Es imprescindible que las longitudes de las aristas no sean negativas. Se resuelve con los algoritmos de Dijkstra y Floyd.

Ya traté este problema en el año 2020 en el tema algoritmo de Dijkstra con ocasión de exponer un ejemplo de aplicación de algoritmos voraces y también en el algoritmo de Floyd para exponer un ejemplo de aplicación de programación dinámica. Ahora los incorporo en la aplicación Grafos SVG con algunas mejoras en la presentación y trazado.