Árbol generador mínimo

Llamamos grafo con pesos a todo grafo $G = (V, X, e)$ , donde $e$ es una función de pesos $X \to R$ , que le asigna a cada arista un número real. Este número bien podria representar distancias, pesos, o alguna otra medida de interes, segun el contexto del problema.

flowchart LR

id1((1))
id2((2))
id3((3))
id4((4))
id5((5))

id1 ---|3| id2
id1 ---|7| id3
id2 ---|4| id3
id2 ---|2| id4
id3 ---|3| id5
id4 ---|5| id5

La función de pesos

e

no necesariamente debe ser una función matematicamente rigurosa como la conocen, puede ser un simple remapeo de valores.

Los grafos con pesos son muy utiles para representar ideas del mundo real (por ejemplo, los nodos pueden ser ciudades y las aristas el largo de las rutas uniendolas), pero suelen complicar un poco los algoritmos.

En particular, nos interesan los arboles generadores de los grafos con pesos, ya que podemos estar buscando algun recorrido que una todos los nodos. Mayormente, nos gustaria encontrar el conjunto de aristas de menor peso. En el ejemplo de las ciudades, esto podria ser quedarnos con las rutas mas cortas (quizas queremos establecer una conexion electrica entre las ciudades, y nos interesa reducir el costo de los cables, que se traduce en su largo). A este árbol de menor distancia es lo que llamamos árbol generador mínimo.

En el ejemplo de antes, el árbol generador minimo seria:

flowchart LR

id1((1))
id2((2))
id3((3))
id4((4))
id5((5))

id1 ===|3| id2
id1 ---|7| id3
id2 ===|4| id3
id2 ===|2| id4
id3 ===|3| id5
id4 ---|5| id5

La raíz del árbol no nos es relevante para este tipo de busquedas, ya que solo nos interesa el conjunto de aristas con el que nos quedamos.