He agregado una nueva utilidad a Grafos SVG para cambiar la dirección del grafo de una forma más simple. En la imagen podemos ver el panel para cambiar la dirección, entre dirigido arriba, dirigido abajo, no dirigido, todo dirigido, todo arriba, todo abajo, doble flecha e inverso.

Si i, j son dos índices de nodos con j > i, si la mitad o más de las aristas son j🡒i lo denominamos grafo dirigido arriba. Si menos de la mitad son j < i tendremos i🡒j y lo denominamos dirigido abajo.

También podemos decir que un grafo es dirigido arriba si la mitad o más aristas van de un nodo con índice mayor que el índice del nodo de destino. En otro caso será dirigido abajo.

Inicié la aplicación Grafos SVG para construir grafos con la publicación del tema estructura de partición que se usa para resolver planificaciones, o bien en el algoritmo de Kruskal para resolver el problema del árbol de recubrimiento mínimo de un grafo. Para la estructura de partición necesitaba representar gráficamente un árbol, que es un grafo conexo no dirigido sin ciclos o, alternativamente, un grafo no dirigido donde cada par de nodos están conectados por un único camino. Si el grafo es dirigido y se anulan las direcciones en la aristas convirtiéndose en un árbol según las definiciones anteriores, entonces se le denomina árbol dirigido.

En un árbol podemos representar los nodos visualmente en niveles, como el de la imagen que tiene 4 niveles, numerados desde el 0 hasta el 3. Cada nodo tiene una arista apuntando a un único padre y una o más aristas a los hijos. El nivel 0 lo ocupa el nodo raíz y los nodos en los sucesivos niveles apuntan a nodos del nivel inmediato superior. Esta forma de ubicar automáticamente los nodos en niveles la usamos para presentar visualmente cualquier grafo, aunque no sea un árbol.

Las estructuras de datos para representar un grafo que usa la aplicación Grafos SVG son, básicamente, el propio JSON de la aplicación basado en relaciones padre-hijo y la matriz de adyacencia. Importamos estas dos estructuras en el área de texto que se observa en la Figura que expone una matriz de adyacencia. Mediante el uso del botón podemos acceder a otros modos como la lista de aristas, lista de adyacencia, matriz de incidencia y matriz de distancias, tanto para importar como para exportar grafos.

En 2020 implementé la aplicación Grafos SVG para crear grafos en SVG. Quería seguir con este apasionante y complejo tema de los grafos, estudiando problemas como el de los caminos y ciclos Hamiltonianos, búsquedas en profundidad o anchura, coloreado de grafos, tipos de subgrafos, cliques, operaciones en grafos, isomorfirmos de grafos y subgrafos, entre otros.

Para implementar algoritmos para resolverlos y otros futuros en esa aplicación necesitaba llevar a cabo algunas mejoras que explicaremos en este tema:

• Botones de edición para agregar, eliminar y contraer nodos y aristas, permitiendo selección visual de elementos para su modificación, pudiendo moverlos con el ratón para reubicarlos. Se incluyen también acciones para deshacer y rehacer cambios.
• Agregar aristas con curvas Bezier cuadráticas o cúbicas.
• Ajustes visuales para modificar la presentación gráfica.
• Mejoras en exportación e importación de grafos soportando además de la matriz de adyacencia, la matriz de incidencia, lista de adyacencia, lista de aristas, matriz de distancias, así como exponer código para ejecutar en Wolfram Cloud y Wolfram Alpha.
• Asistente de generación de nuevos grafos y operaciones sobre grafos.
• Ejecución de algoritmos sobre grafos.

Definimos el Grupo de permutaciones, que denominaremos G, aquel cuyos elementos son permutaciones de un conjunto M. Este conjunto es la lista de elementos con los que hemos venido generando funciones combinatorias en estos temas, algo como M = {1, 2, 3, 4, 5}.

El grupo G dispone de una operación de composición o producto de permutaciones de G que resultan en otra permutación de G, operación que no es conmutativa en general. Como grupo matemático además dispone de un elemento neutro (o pemutación identidad) y de una operación inversa de permutación.

Implementamos una Calculadora de permutaciones cíclicas en la aplicación Combine Tools, cuyo objeto es poner en práctica los conceptos anteriores.

En la aplicación definimos el conjunto M y una o dos permutaciones σ y π en notación cíclica, pudiendo realizar operaciones como el producto o composición de permutaciones, potencia, inversa, inversiones, transposiciones, signatura, índice, orden, ... O bien extraer el grafo de una permutación, basado en el componente que explicamos en la página Web Tools online: Grafos con SVG.

Una permutación cíclica es una permutación que fija cero o más elementos y mueve el resto de forma cíclica. Cuando no se fija ningún elemento se denomina permutación circular.

En la imagen vemos las permutaciones cíclicas de 4 elementos {a, b, c, d}, que de forma compacta representamos como abcd, tomando 3 ciclos. Un ciclo se presenta con una permutación entre paréntesis. Los ciclos son como las particiones que vimos en temas anteriores, en el sentido de que son subconjuntos disjuntos del conjunto de partida. Al ser subconjuntos, el orden de los ciclos en la permutación no importa, con lo que algo como (a)(b)(cd) es lo mismo que (b)(cd)(a) y cualquiera de las otras posibles permutaciones de los ciclos.

Las particiones también cuentan el número de esquemas de rimas de un poema. Entonces podemos generar B(n) particiones y por tanto rimas distintas. Si el conjunto de partida son n líneas de poemas (o versos) numeradas 1..n, podemos generar B(n) posibles formas de disponer las rimas en esas líneas.

Por ejemplo, con n=3 disponemos del conjunto de partida de líneas numeradas {1, 2, 3}, generándose las particiones 123, 12.3, 13.2, 1.23, 1.2.3 expresadas de forma compacta. Cada dígito representa la línea donde hemos de incluir una rima entre [A, B, C], que se van seleccionando en orden. Así una partición como 12.3 se traduce como AAB indicando que las 2 primeras líneas riman, pues están en el mismo subconjunto. Y la tercera no rima con ninguna al ser única en su subconjunto.

Las particiones con bloques parciales (o Bell parcial), que denominaremos pB(n, k), son las particiones de un conjunto con n elementos tal que alguno de los subconjuntos (o bloques) son de longitud igual a k. En la Figura vemos las particiones con bloques parciales de tamaño k=2 para un conjunto con n=4 elementos, donde cada partición contiene al menos un subconjunto o bloque de tamaño k=2.

Por otro lado las particiones con semi bloques parciales (o semi Bell), que denominaremos sB(n, k), son las particiones de un conjunto con n elementos tal que ninguno de los subconjuntos (o bloques) son de longitud igual a k. Por ejemplo, para el conjunto con n elementos {a, b, c} tenemos con k=1 la única partición abc expresada de forma compacta, donde ningún subconjunto o bloque tienen longitud unitaria; con k=2 tenemos abc, a.b.c; con k=3 tenemos ab.c, ac.b, a.bc, a.b.c; mientras que con k=0 o k>3 tenemos todas las particiones posibles abc, ab.c, ac.b, a.bc, a.b.c.