Теория:

Область применения теории графов широка. Использование различных методов и алгоритмов построения графов дает оптимальные решения задач из разных областей науки.
Представим, что перед тобой стоит задача. Тебе надо соединить \(n\) контактов \((n-1) \)проводами с минимальной суммарной стоимостью.
Если переложить задачу на теорию графов, звучать она будет так. У тебя есть связный взвешенный неориентированный граф. Каждое ребро имеет вес или длину. Надо найти такое дерево, содержащее все вершины графа, у которого сумма весов всех рёбер дерева была бы минимальна. Такое дерево носит название каркас минимального веса (другое название: минимальный остов графа).
Такую задачу можно решить с помощью алгоритма Краскала.
Алгоритма Краскала — алгоритм построения каркаса минимального веса для взвешенного связного неориентированного графа. Суть алгоритма заключается в сортировке всех рёбер графа в порядке возрастания веса. Затем они поочередно добавляются в дерево. Но при этом должно соблюдаться условие, что рёбра соединяют различные вершины и их добавление не вызовет появление цикла в дереве. Когда таких рёбер больше нет, алгоритм считается завершённым. Дерево, которое получается в итоге — каркас минимального веса.
Пример:
тебе надо соединить \(7\) контактов \(6\) проводами с минимальной суммарной стоимостью. Условия представлены в виде следующего графа на рис. \(1\). Решим данную задачу, используя алгоритм Краскала.
граф1.png
Рис. \(1\). Граф по условиям задачи
Исходный граф
Ход решения
Ход построения каркаса минимального веса
граф2.pngРассмотрим граф. Рёбра \(14\) и \(35\) имеют минимальный вес, равный \(5\). Выбираем произвольно ребро \(14 \)кар3.png
граф3.pngТеперь из оставшихся рёбер выбираем ребро с минимальным весом. Это ребро \(35\). Его вес равен \(5\). Добавляем его в каркас, так как это ребро соединяет различные вершины и это не вызовет появление циклакар4.png
граф4.pngСледующее из оставшихся с минимальным весом — ребро \(46\) с весом \(6\). Добавляем его в каркаскар5.png
граф5.pngТеперь с минимальным весом \(7\) стали рёбра \(12\) и \(25\). Выбираем ребро \(12\). Теперь видно, что ребро \(24\) выбирать нельзя в будущих шагах, так как может образоваться цикл \(124\)кар6.png
граф6.pngТеперь выбираем второе ребро \(25\) с весом \(7\). На этом этапе появляется больше рёбер, которые могут привести к образованию циклов (\(23\), \(45\), \(56\))кар7.png
граф7.pngОстаются два подходящих ребра \(57\) и \(67\). Однако, минимальный вес имеет ребро \(57\). Его вес — \(9\). Поэтому выбираем егокар8.png
граф8.png
Больше рёбер, не приводящих к зацикливанию, не осталось. Алгоритм завершён. Мы получили каркас минимального веса для исходного графа.
Вес каркаса — \(39\)