Un problema recurrente en teoría de grafos es el de hallar el mínimo árbol generador de un grafo ponderado y conexo. Recordemos que un árbol es un grafo conexo y acíclico mientras que un grafo generador es un grafo que contiene los mismos vértices que el original y cuyo conjunto de aristas es un subconjunto del original, en otras palabras es el grafo que resulta de extraer alguna (o ninguna) artista de otro.