Рассмотрим задачу: имеется n городов A₁, … ,A_n, которые необходимо связать между собой сетью шоссейных или железных дорог. Для каждой пары городов A_iA_j известна стоимость C_ij соответствующей магистрали (С_ij можно рассматривать как расстояние между городами A_i и A_j). Задача состоит в том, чтобы построить самую дешевую из сетей дорог, которые связывает все эти города. Вместо сети дорог можно рассмотреть сеть электропередач, оросительную сеть и т.д. Вместо строительства новых сетей можно рассмотреть вопрос о ремонте уже существующих.

Рассмотрим задачу в общем случае.

Дано n точек и для каждой пары точек i и j известно расстояние C_ij=C_ji, т.е. в данном случае некоторому ребру (i,j) приписывается число C_ij (которое означать стоимость, длину, время и т.д.). Необходимо построить связную неориентированную сеть с n вершинами, сумма длин ребер которой будет наименьшей. Такую сеть будем называть минимальной связывающей сетью.

Граф минимальной связывающей сети является деревом, (дерево не содержит циклов). Если бы граф содержал цикл, то, удалив одно из ребер этого цикла, можно было бы оставить все точки (вершины графа) все еще соединенными, а сумма длин ребер после удаления уменьшилась бы. Такое дерево будем называть минимальным связывающим деревом.

Задачу построения минимального связывающего дерева с n вершинами можно построить методом перебора, но такой путь не рационален. Различных деревьев с n вершинами существует n^n-2. Если n=10, то деревьев 10⁸.

Наиболее простой метод решения этой задачи алгоритм Краскала:

Изобразим города A₁,A₂,…,A_n dв виде кружочков с соответствующим обозначением, т.е. в виде вершин графа. Пару вершин i и j соединим ребром, если это ребро соответствует самому короткому расстоянию C_ij. Из всех оставшихся значений C_ij снова выбираем самое маленькое и пару вершин i и j соединим ребром в том случае, если на графе не образуется цикла. И так далее. Процесс соединения вершин прекращается, когда все вершины будут соединены ребрами. Каждое дерево, построенное таким образом будем называть экономичным деревом.

Самостоятельно показать, что экономичное дерево имеет наименьшую сумму длин ребер.

Теорема: Любое дерево с n вершинами имеет в точности n-1 ребро.

Пример: Дано 5 городов, расстояния между которыми приведены в таблице. Найти оптимальное связывающее дерево.

min C_ij=C₁₄=1

min C_ij=C₁₃=C₂₄=2

min C_ij=C₁₂=3 нельзя так как образует цикл

min C_ij=C₁₅=4

Длина min связывающей цепи:l_min=1+2+2+4=9