Árbol de expansión de peso mínimo

El árbol de expansión de peso mínimo es aquel que comienza desde un vértice y encuentra todos sus nodos accesibles y las relaciones en conjunto que permiten que se conecten dichos nodos con el menor peso posible. Este tipo de cálculo de alto interés cuenta con diversos usos que analizaremos a continuación. Este algoritmo se encuentra dentro de las librerias de Neo4j como uno de los más completos algoritmos de grafos.

Descubre cómo funciona este importante algoritmo, sus principales casos de uso y ejemplos de aplicación.

¿Qué es el árbol de expansión de peso mínimo?

Antes de abordar a profundidad el funcionamiento de este importante algoritmo, descubramos un poco sobre su historia. Esté algoritmo diseñado para diseñar un árbol de expansión mínima fue desarrollado por el científico checo Otakar Boruvka en 1926. Este algoritmo nace en el intento de encontrar una red eléctrica que fuese eficiente para Moravia.

A partir de este algoritmo nace lo que conocemos como árbol de expansión de peso mínimo que comienza desde un vértice especificado dentro de un grafo y encuentra todos los vértices a los que tiene accesibilidad determinando el conjunto de relaciones que conectan los nodos con un valor de peso del menor tamaño posible.

¿Cómo funciona el algoritmo?

Este algoritmo para ejecutar su funcionamiento requiere de ciertos pasos o proceso que te describimos a continuación los describiremos.

Empezamos con un árbol que posea únicamente un nodo y no tenga relaciones. Posteriormente se debe seleccionar la relación de peso mínimo proveniente de dicho nodo y se agrega al árbol en cuestión. Este proceso debe realizarse en diversas oportunidades para unir los nodos del árbol a los demás que conforman el grafo, agregando nuevas relaciones en cada una de las oportunidades. 

Cuando no hay más nodos para agregar, el árbol que hemos construido es un árbol de expansión de peso mínimo.

Casos de uso del árbol de expansión de peso mínimo

Al encontrar las relaciones de menor peso entre datos contenidos en vértices que conforman un grafo, este tipo de algoritmo puede ser utilizado para diseñar rutas de recorridos en sistemas de carreteras o itinerario de rutas aéreas para que las rutas planificadas sean más eficientes. También el árbol de expansión de peso mínimo puede ser utilizado para analizar correlaciones en sistemas financieros de mercados de divisas.

árbol

Adicionalmente, este algoritmo es de gran utilidad para rastrear datos dentro de sistemas complejos de comprender o que contengan muchas variables. Aunque hay casos específicos en los que no deben tomarse en cuenta los análisis bajo este algoritmo. En caso de que el grafo no posea ningún peso o las relaciones sean del mismo peso, el cálculo del algoritmo no serviría, ya que sería un árbol de expansión mínima. 

Ejemplo de aplicación y cálculo

En el siguiente ejemplo realizaremos una construcción de un grafo en forma de árbol en cypher, en el ambiente de desarrollo y análisis de Neo4j para comprender mejor su funcionamiento. Se inicia el proceso construyendo un grafo de este tipo:

MERGE (a:Place {id:"A"})
MERGE (b:Place {id:"B"})
MERGE (c:Place {id:"C"})
MERGE (d:Place {id:"D"})
MERGE (e:Place {id:"E"})
MERGE (f:Place {id:"F"})
MERGE (g:Place {id:"G"})

MERGE (d)-[:LINK {cost:4}]->(b)
MERGE (d)-[:LINK {cost:6}]->(e)
MERGE (b)-[:LINK {cost:1}]->(a)
MERGE (b)-[:LINK {cost:3}]->(c)
MERGE (a)-[:LINK {cost:2}]->(c)
MERGE (c)-[:LINK {cost:5}]->(e)
MERGE (f)-[:LINK {cost:1}]->(g);

Se ejecuta el cálculo del algoritmo de árbol de expansión de peso mínimo:

MATCH (n:Place {id:"D"})
CALL algo.spanningTree.minimum('Place', 'LINK', 'cost', id(n),
  {write:true, writeProperty:"MINST"})
YIELD loadMillis, computeMillis, writeMillis, effectiveNodeCount
RETURN loadMillis, computeMillis, writeMillis, effectiveNodeCount

Posteriormente se ejecuta la siguiente consulta:

MATCH path = (n:Place {id:"D"})-[:MINST*]-()
WITH relationships(path) AS rels
UNWIND rels AS rel
WITH DISTINCT rel AS rel
RETURN startNode(rel).id AS source, endNode(rel).id AS destination, rel.cost AS cost

Resultados:

SourceDestinationCost

D

B4
BA1
AC2
CE

5

Como resultado se puede observar en la tabla que los nodos F y G sin inalcanzables desde D y se destaca la relaciones existentes de B a C siendo estas las mas eficientes.

Esperamos que esta información sea de utilidad para comprender el alcance de este algoritmo.

Visita más de Grapheverywhere para conocer todo lo que necesitas sobre los algoritmos de grafos.

Share This