Un corte mínimo de vértices s-t supone encontrar un conjunto mínimo de vértices que separe los nodos "s" y "t" en distintos componentes conectados. Y un corte mínimo de vértices del grafo aplica lo anterior a todas las parejas de nodos "s" y "t" no adyacentes del grafo devolviendo el mímimo corte s-t.

En la aplicación Grafos SVG implementamos findSTVertexCut() y findVertexCut() para resolver esos problemas así como getVertexConnectivity() para obtener la conectividad de vértices.

Un corte mínimo de aristas s-t supone encontrar un conjunto mínimo de aristas que separe los nodos "s" y "t" en distintos componentes conectados. En Grafos SVG se dispone de un algoritmo para encontrar el corte mínimo de aristas entre dos nodos "s" y "t".

Otro algoritmo de este tema tiene por objeto encontrar todos los cortes de aristas, lo que supone iterar por todas las parejas de nodos "u" y "v" encontrando las aristas que producen un corte mínimo y finalmente devolver todos los resultados ordenados por la suma de flujos creciente, siendo el primer resultado la solución con mínimo corte.

Y también otro para obtener la conectividad de aristas s-t de un grafo, que es el mínimo número de aristas que al eliminarlas separa los nodos "s" y "t" en distintos componentes conectados, o bien la conectividad de aristas de un grafo que es el mínimo de todos los cortes mínimos de aristas para todas las parejas de nodos del grafo.

Un grafo conectado es aquel donde desde un nodo podemos llegar a cualquier otro del grafo. En otro caso pueden existir subgrafos conectados que son aquellos donde todos los nodos del subgrafo están conectados. Si el grafo es dirigido podemos hablar de débilmente conectado si no consideramos la dirección de las aristas, es decir, si consideramos el grafo como no dirigido. Y fuertemente conectado cuando se considera la dirección de las aristas.

En Grafos SVG tenemos varios algoritmos relacionados con los componentes conectados de un grafo, como obtener los componentes conectados, saber si un grafo está desconectado, saber si un vértice es de articulación, saber si una arista es puente, encontrar todos los vértices de articulación, encontrar todas las aristas puente, encontrar un conjunto separador de vértices (como el de la imagen adjunta de tamaño 3) y encontrar un conjunto separador de aristas.

Una red de flujo puede representarse en un grafo dirigido ponderado donde los pesos representan las capacidades de las aristas, con un nodo identificado como fuente (source) tomando sólo las aristas salientes y otro identificado como sumidero (sink) tomando sólo las aristas entrantes, considerando que la dirección de la aristas representan un flujo existente desde la fuente hasta el sumidero. El flujo puede ser cualquier cosa que fluye en una unidad de tiempo, como litros de agua que pasan por una tubería, número de vehículos que pasan por una carretera, etc.

En Grafos SVG el algoritmo encontrar máximo flujo del grafo se refiere entonces a calcular cuál es la cantidad máxima de flujo que puede circular desde el nodo fuente hasta el nodo sumidero sin superar las capacidades de las aristas. En este tema también veremos un algoritmo para encontrar caminos con aristas independientes usando el princicipio de que el máximo flujo de un grafo es igual que el número de caminos con aristas independientes.

Un algoritmo de Grafos SVG es encontrar camino en un grafo entre dos nodos, donde buscamos un camino que empiece en un nodo y acabe en el otro. En la imagen vemos el primer camino encontrado entre los nodos "0" y "6" que incluye los los nodos 0,2,4,1,3,6.

Se expone en este tema también un algoritmo para encontrar un camino de cobertura que pase por una lista de nodos que se especifique y otro algoritmo para encontrar los caminos independientes entre dos nodos, con independencia en nodos o aristas.

En Grafos SVG encontramos el algoritmo de búsqueda primero en profundidad, en inglés Depth-first search y su abreviatura DFS, recorre el grafo empezando en un nodo que se indique atravesando los nodos primero hacia abajo y luego hacia algún lado (izquierda o derecha).

En este tema se presenta esa búsqueda en profundidad (DFS) tanto iterativa como recursiva, la búsqueda en anchura (BFS) recursiva y otro algoritmo para realmente buscar un nodo o arista con un valor de etiqueta que se especifique.

En la sección de acciones de Grafos SVG ejecutamos algoritmos sobre un grafo. Uno de ellos es encontrar una ruta Euleriana en un grafo, que será un camino que debe recorrer todas las aristas del grafo una única vez. En la imagen vemos un ruta Euleriana en el grafo Completo K5 mostrando el circuito 0,1,2,0,3,1,4,2,3,4,0

He separado las operaciones en un grafo de la aplicación Grafos SVG en dos páginas: por un lado operaciones básicas con edición, contracción, división, subdivisión y dirección, y por otro lado operaciones avanzadas con complemento, transposición, línea, permutación y cociente.

En el tema de inicio ya habíamos incluido edición de nodos y aristas cuando esas operaciones se ejecutan desde la estructura JSON, lo que se lleva a cabo con los botones

Ahora además implementamos esas misma operaciones sobre la matriz de adyacencia que se exponen en el nuevo tema operaciones básicas.

He separado los ajustes visuales de la aplicación Grafos SVG en una página separada del tema inicial mejora aplicación grafos, aplicando también mejoras en algunos ajustes visuales.

En la sección de acciones de Grafos SVG ejecutamos algoritmos sobre un grafo. Uno de ellos es encontrar un camino Hamiltoniano entre dos nodos del grafo, que será un camino que debe recorrer todos los nodos del grafo una única vez. En la imagen vemos un camino Hamiltoniano en el grafo de Petersen 5,2 mostrando un camino entre los nodos "0" y "7" que recorre todos los nodos.

Una ruta en un grafo es una secuencia de visitas a varios nodos con aristas incidentes en el recorrido, diferenciándose entre recorrido (walk), rastro (trail), circuito (circuit), camino (path) y ciclo (cycle). En lugar de rutas suele usarse caminos, tanto en sentido genérico para agrupar todos los anteriores como específico para el propio camino, que es una ruta con vértices y aristas que no pueden repetirse. Para ser coherentes deberíamos titular este tema rutas en grafos en lugar de caminos en grafos.

En este tema vermos el algoritmo identifyRoute() que implementamos en Grafos SVG y que nos permitirá identificar una ruta en un grafo a partir de su matriz de adyacencia, como el circuito 1,0,4,5,2,3,6,5,1 de la imagen.

En la sección de acciones de Grafos SVG ejecutamos algoritmos sobre un grafo. Estas acciones pueden ser muy simples como obtener el número de vértices de un grafo. O más complejas como obtener los ciclos de un grafo desde un nodo concreto, como vemos en la imagen, obteniendo tres ciclos desde el nodo "0" de un grafo dirigido.

Veremos acciones para obtener el total de vértices o aristas, obtener grados de los vértices, comprobar si tiene ciclos, obtener ciclos desde un nodo y obtener todos los ciclos. Algunas acciones ya se han expuesto en temas anteriores. Otras más complejas se expondrán en temas siguientes.

En el asistente de generación de Grafos SVG que se accede con generamos nuevos grafos. En el tema anterior vimos los nuevos grafos simples, en este veremos algunos más avanzados como Kneser, Johnson, Petersen, circulante, Platónico, permutación cíclica, permutación y Sudoku.

Veremos también como resolver un SUDOKU coloreando un grafo Sudoku.

Podemos a acceder al asistente de generación en la aplicación Grafos SVG con el botón . Ahí encontraremos las operaciones en grafos que vimos en el tema anterior. Y la generación de nuevos grafos que veremos en este tema.

Se exponen grafos simples rejilla, círculo, cíclico, completo, bipartito, puesta sol, rueda y estrella.

En la aplicación Grafos SVG se encuentra el panel de operaciones en grafos dentro de la sección del asistente de generación. Las operaciones en grafos producen nuevos grafos diferentes de los iniciales. Se ejecutan sobre la matriz de adyacencia modificándola y, por tanto, modificando también el grafo.

Existen operaciones unarias y binarias. Dentro de las unarias están las simples, como añadir o eliminar nodos o aristas. Y las complejas que se ejecutan en ese panel de operaciones, como cambiar la dirección, complementar, transponer, permutar, obtener el grafo línea y obtener el grafo cociente. No se implementan las binarias y otras unarias, como grafo menor, dual o potencia de un grafo.

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.