Второй алгоритм решения

1. По заданному множеству точек на плоскости (каждая точка является вершиной графа) построить триангуляцию Делоне.

2. В качестве весов ребер взять их длину.

3. Использовать алгоритм Прима или Краскала для нахождения минимального каркасного дерева.

Замечания

1. Борис Николаевич Делоне предложил этот метод триангуляции в 1934 году в работах по вычислительной геометрии.

2. Существуют эффективные алгоритмы построения триангуляции Делоне.

3.3. Минимальные каркасные деревья

с

Определения

ограничениями

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

В литературе можно найти свыше 30 вариантов двухкритериальных минимальных каркасных проблем, а также несколько многокритериальных проблем.

3.3.1. Минимальное каркасное дерево

с заданной степенью

Определения

Если потребовать, чтобы степень минимального каркасного дерева не превышала заданного числа, т.е. deg(Т)=k,k2, то возникает проблема нахожденияминимального каркасного дерева с заданной степенью. Далее для краткости эта проблема будет называтьсяk-MST проблемой(k-MinimumSpanningTreeproblem).

2-MSPпроблема является проблемой нахождения гамильтонова пути минимальной длины.

Класс сложности

k-MSTпроблема относится кNP-тяжелым при любомk.

Алгоритмы для k-MSTпроблемы на евклидовой плоскости

При задании графа Gна евклидовой плоскости вес его ребер есть расстояние между смежными вершинами. Для данного случая было доказано, что существует минимальное каркасное дерево со степенью не более 5. Однако приk=3 проблемаNP-тяжела, приk=4 доказательства нет.

Для решения k-MSTпроблемы на евклидовой плоскости существуют эвристические алгоритмы полиномиального времени (в частности, модифицированный алгоритм Прима (k-Primalgorithm)).

Весьма успешно применяются различные версии генетических и эволюционных алгоритмов.

3.3.2. Минимальное каркасное дерево с максимальным числом листьев

Определение

Для заданного взвешенного ненаправленного графа G=(V,E) найти минимальное каркасное дерево Т с максимальным числом листьев.

Класс сложности

П

Алгоритмы

роблема относится кNP-тяжелым.

Известны достаточно хорошие аппроксимационные алгоритмы, лучший из имеет сложность почти линейную в размерах графа. Аппроксимационное отношение алгоритмов – 2,5 – 3,0.

3.3.3. Каркасное дерево с кратчайшей

о

Определение

бщей длиной пути

Задан взвешенный ненаправленный граф G=(V,E) и положительное целое числоB. Имеется ли каркасное деревоT=(V,F),FE, такое, что сумма всех путей между всеми возможными парами вершинuиvв этом дереве не превышала величинуB?

Класс сложности

П

Алгоритмы

роблема относится кNP-тяжелым.

Имеются эвристические алгоритмы, позволяющие получить аппроксимационные отношения 2,15/8 и 3/2 за время О(n²+f(G)),O(n³) иO(n⁴) соответственно, гдеf(G) – время вычисления кратчайших путей между всеми парами вершин графаG, аn– число вершин графаG.

3.3.4. Каркасное дерево с ограничением диаметра

Определение

Для заданного взвешенного связного графа найти минимальное каркасное дерево с заданной нижней границей диаметра D2.

Класс сложности

Проблема относится к NP-тяжелой для 4Dn-1, гдеn– число вершин графа.

Алгоритмы

Точные алгоритмы позволяют получить за разумное на практике время решение для полного графа размером менее 100 вершин. Имеются жадные эвристические алгоритмы, основанные на алгоритме Прима, а также эволюционные алгоритмы решения проблемы.