Предположим, что имеется n городов, которые нужно соединить нефтепроводом (электролинией, газопроводом). Стоимость строительства нефтепровода между городами xi, xj задана. Как построить самый дешевый нефтепровод, связывающий все города?
Построим граф, вершинами которого обозначены города, а ребрами возможные нефтепроводы между ними. Каждому ребру графа (xi,xj) поставим в соответствие число l(xi,xj)≥0, равное стоимости строительства нефтепровода на участке (xi,xj). Задача строительства самого дешевого нефтепровода сводится к следующей задаче на графе. Задан конечный неориентированный связной граф G(X,U) каждому ребру которого (xi,xj)=uk, uk 
U, поставлено в соответствие число l(uk)≥0, называемое длинной ребра. Требуется найти такой частичный граф-дерево графа G (частичное дерево), общая длина ребер которого минимальна. Решение этой задачи может быть получено с помощью следующего алгоритма.
