El árbol Gomory-Hu de un grafo permite encontrar el corte mínimo de aristas con menor coste que otros algoritmos cuando se aplica sobre grafos no dirigidos y conectados y, especialmente, sobre grafos ponderados.

Implementamos el algoritmo getGomoryHuTree() para construir ese árbol y también findEdgeCutGomoryHu() para encontrar las aristas de corte mínimo en un grafo a partir de ese árbol.

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