Кратчайший остов графа
Рассмотрим взвешенный связный неориентированный граф G=(X, A); вес ребра (xi, xj) обозначим cij. Из большого числа остовов графа нужно найти один, у которого сумма весов ребер наименьшая.
Такая задача возникает, например, в том случае, когда вершины являются клеммами электрической сети, которые должны быть соединены друг с другом с помощью проводов наименьшей общей длины (для уменьшения уровня наводок). Другой пример: вершины представляют города, которые нужно связать сетью трубопроводов; тогда наименьшая общая длина труб, которая должна быть использована для строительства (при условии, что вне городов «разветвления» трубопроводов не допускаются), определяется кратчайшим остовом соответствующего графа.Следует отметить, что кратчайший остов графа не имеет никакого отношения к дереву, дающему все кратчайшие пути, выходящие из некоторой выбранной вершины.
Задача построения кратчайшего остова графа является одной из немногих задач теории графой, которые можно считать полностью решенными. Итак, пусть Ti и Tj — два произвольных поддерева, полученных путем добавления ребер при построении кратчайшего остова графа. Определим Dij, как кратчайшее из расстояний между вершинами из Ti и вершинами из Tj следующим образом:
, i≠j. (1)
Зададим следующую операцию: Для поддерева Ts найти такое поддерево Tj*, чтобы 
. Пусть 
будет тем ребром, вес которого соответствует величине 
в выражении (1). Тогда ребро 
принадлежит кратчайшему остову и может быть добавлено к другим ребрам частично сформированного кратчайшего остова.
Многократное применение нижеследующей операции приводит к построению кратчайшего остова графа. Многие методы, позволяющие строить кратчайший остов графов, основываются на частных случаях описанной выше операции. Первый из таких методов был предложен Краскалом.