Математика. Алгоритм Краскала.

Алгоритм был предложен Джозефом Краскалом в 1957 г. Алгоритм Крускала (или алгоритм Краскала) — эффективный алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа.

Области применения

 Разработка сетей. Ранее был приведен пример о соединении n городов в единую телефонную сеть с минимальной суммарной стоимостью соединений.

 Производство печатных плат. По аналогии с сетью: мы хотим соединить n контактов проводами с минимальной суммарной стоимостью. (Здесь стоит отметить, что задача о минимальном остовном дереве является упрощением реальности. В самом деле, если соединяемые контакты находятся в вершинах единичного квадрата, разрешается соединять любые его вершины, и вес соединения равен его длине, то минимальное покрывающее дерево будет состоять из трех сторон квадрата. Между тем все его четыре вершины можно электрически соединить двумя пересекающимися диагоналями, суммарная длина которых будет равна 2√2, что меньше 3 в первом случае).

 Минимальное остовное дерево может использоваться для визуализации многоаспектных, многомерных данных, например, для отображения их взаимосвязи 

 Наука, и в частности биология, используют многомерные данные для группировки объектов, растений, животных. Минимальное остовное дерево позволяет разбивать их на взаимосвязанные классы, четко отслеживая близкие по строению и характеристикам группы.