Упражнения. > 20.81.Дайте встречный пример, показывающий, почему не работает следующий ме­тод поиска эвклидова дерева MST: Сортировать точки по их координатам х

> 20.81. Дайте встречный пример, показывающий, почему не работает следующий ме­тод поиска эвклидова дерева MST: " Сортировать точки по их координатам х, затем найти минимальные основные деревья первой половины и второй половины, затем найти кратчайшие ребра, соединяющие их".

о 20.82. Разработайте быструю версию алгоритма Прима для вычисления эвклидового дерева MST для множества точек, равномерно распределенных на плоскости, в основу которой положен принцип игнорирования отдаленных точек до тех пор, пока к ним не приблизится само дерево.

•• 20.83. Разработайте алгоритм, который при заданном множестве N точек на плоско­сти находит множество ребер, мощность которого пропорциональна N и в котором обязательно содержится достаточно просто вычисляемое дерево MST, так что можно отдать предпочтение компактной и эффективной реализации алгоритма.

о 20.84. Пусть дано случайное множество, состоящее из N (равномерно распределен­ных) точек в единичном квадрате. Эмпирическим путем определите значение d с точ­ностью до двух десятичных разрядов, такое, что множество ребер, образованных все­ми парами точек в пределах расстояния, не превышающего d, с вероятностью 99% содержит дерево MST.

о 20.85. Выполните упражнение 20.84 для точек, в которых каждая координата получе­на путем выборки из распределения Гаусса со средним значением 0.5 и со среднеквад­ратическим отклонением 0.1.

• 20.86. Опишите, как вы смогли бы увеличить производительность алгоритмов Крус-кала и Борувки для случая разреженных эвклидовых графов.