Задача поиска наименьшего остового дерева.
Наименьшее остовое дерево – это вариант остового дерева имеющий наименьший суммарный вес дуг. При анализе структуры системы решение задачи поиска нахождения наименьшего остового дерева позволяет выбирать вариант соединения вершин системы с наименьшей затратой некоторого ресурса.
Дано:
G <V, U> - взвешенный неориентированный граф.
D (N, N) – взвешенная матрица смежности для заданного графа.
|
a |
b |
c |
d |
e |
f |
a |
∞ |
6 |
∞ |
∞ |
∞ |
7 |
b |
6 |
∞ |
7 |
10 |
10 |
6 |
c |
∞ |
7 |
∞ |
5 |
5 |
∞ |
d |
∞ |
10 |
5 |
∞ |
8 |
∞ |
e |
∞ |
10 |
5 |
8 |
∞ |
7 |
f |
7 |
6 |
∞ |
∞ |
7 |
∞ |
Рис 4.11. Заданный взвешенный граф.
Алгоритмы построения наименьшего остового дерева.
Создаем матрицу столбец R, в которую будут заноситься кратчайшие расстояния от вершин графа до остового дерева.
В качестве начальных значений заносится ∞, элементы матрицы соответствуют вершинам графа.
Создаем матрицу столбец В. В неё будут заноситься вершины остового дерева, ближайшие к соответствующим вершинам графа. В качестве начальных значений вводятся пробелы.
Взять любую вершину графа, и поместить ее в остовое дерево, т.е. принять в качестве вершины Vk. Вычеркнуть вершину Vk из вершин графа.
Пересчитать расстояния от вершин графа до остового дерева, т.е. значения элементов матрицы R по схеме.
Если расстояние до остового дерева для какой либо вершины Vj больше чем вес дуги между данной вершиной и вершиной Vk , т.е. вершиной включенной в остовое дерево, то в качестве значения расстояния до остового дерева от этой вершины принимается данный вес дуги между вершиной Vj и Vk.
В качестве вершины остового дерева у которой найдено расстояние, т.е. вершины остового дерева ближайшей вершины Vk – принимается вершина Vk.
В качестве вершины Vk, т.е. вершины включенной в остовое дерево принимается вершина с наименьшим значением матрицы R, т.е. вершины ближайшей к остовому дереву. Вершина Vk вычеркивается из множества вершин.
Если не все вершины графа вычеркнуты, то переход к этапу 2.
Рис 4.12. Полученное наименьшее остовое дерево.
Данный алгоритм основан на повторяющемся поиске вершин графа ближайших к уже построенному остовому дереву.
Найденная ближайшая вершина включается в остовое дерево и удаляется из оставшихся вершин графа.
На начальном этапе в остовое дерево включается любая вершина графа. При пересчете расстояний от вершин графа до вершин остового дерева предшествующее расстояние сравнивается с расстоянием до вершины последней включенной в остовое дерево.
Из этих двух значений выбирается минимальное.
Задача построения наименьшего остового дерева решается как в качестве отдельной задачи анализа структуры системы так и в качестве промежуточной вспомогательной задачи при решении задачи поиска кратчайшего пути обхода всех вершин графа (задача коммивояжера).