Закрыть

Алгоритмы построения кратчайших связывающих деревьев.

Автор: Васин Алексей
Опубликовано 08.02.2008 в 15:56
Раздел: Дискретная математика

Вводные определения

Граф, любая пара вершин которого может быть соединена маршрутом, называется связанным.

Связанный граф,не содержащий циклов,называется деревом. Если граф является взвешенным,то актуальной задачей является задача построения минимального дерева,т.е. дерева с минимальным суммарным весом его ребер.

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

Расстояние определяется в ортогональной метрике по следующей формуле: $D_{ij}=|x_i-x_j|+|y_i-y_j|$, где $x_i,y_i,x_j,y_j$-координаты вершин i и j по осям X и Y.

Алгоритмы Прима и Краскала дают точное решение этой задачи, т.е обеспечивают нахождение глобального оптимума.

Алгоритм Прима

Алгоритм Прима является последовательным и наращивает дерево, состоящее из одной компоненты связности по матрице расстояний $D=|d_{ij}|_{nxn}$ (n-количество вершин графа).Элемент матрицы $d_{ij}$ равен расстоянию между i и j вершинами графа.

Алгоритм состоит из следующей последовательности действий:

  1. В матрице D просматриваются элементы первой строки и выбирается минимальный элемент(например, элемент g-го столбца).
  2. Исключаются из рассмотрения 1-й и g-й столбцы и строится ребро, соединяющее 1-ю и g-ю вершины.
  3. Просматриваются 1-я и g-я строки и выбирается в одной из них минимальный элемент (если минимальных элементов несколько,то выбирается любой из них).
  4. Прежде чем построить ребро, соответствующее выбранному минимальному элементу,проверяется степень инцидентных ему вершин (например,g-й и r-й). Если степени данных вершин не превышают заданного ограничения,то данное ребро включается в строющееся дерево,в матрице вычеркивается r-й столбец,а к строкам в которых ищется минимальный элемент добавляется r-я строка и повторяются п.п. 3 и 4.
  5. Если ограничение на степень вершины нарушено,то соответствующий минимальный элемент вычеркивается из рассмотрения и повторяется выполнение п.З,т.е. ищется новый минимум.
  6. Матрица просматривается до тех пор,пока не будут включены все строки.

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

Алгоритм Краскала может строить дерево одновременно для нескольких компонент связности,которые в процессе решения объединяются в одно связанное дерево.

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

Алгоритм состоит из следующей последовательности действий:

  1. Создается список ребер R,содержащий длину ребра, номер исходной вершины ребра (i),номер конечной вершины ребра (j), признак включения данного ребра в дерево.
  2. Данный список упорядочивается в порядке возрастания длин ребер.
  3. Просматривается список R и выбирается из него ребро с минимальной длиной, еще не включенное в результирующее дерево и не образующее цикла с уже построенными ребрами.
  4. Если все вершины включены в дерево и количество ребер на единицу меньше количества вершин,то алгоритм свою работу закончил. В противном случае осуществляется возврат к пункту 3.

Примеры

Рассмотрим пример решения задачи построения минимального дерева с помощью алгоритма Прима и Краскала.

В табл.1 заданы координаты пяти вершин графа.

Таблица 1

$\begin{array}{rrr} Номера вершин & X & Y \\ x_1 & 1 & 1 \\ x_2 & 2 & 1 \\ x_3 & 5 & 4 \\ x_4 & 5 & 5 \\ x_5 & 6 & 5 \end{array}$

Допустим, что степень вершин графа ограничена числом 2. Строим матрицу расстояний D.

Матрица D:

$\begin{array}{lrrrrr} & x1 & x2 & x3 & x4 & x5 \\ x1 & 0 & 1 & 7 & 8 & 8 \\ x2 & 1 & 0 & 6 & 7 & 7 \\ x3 & 7 & 6 & 0 & 1 & 1 \\ x4 & 8 & 7 & 1 & 0 & 2 \\ x5 & 8 & 7 & 1 & 2 & 0 \end{array}$

Решение алгоритмом Прима.

Просматриваем первую строку матрицы расстояний и находим минимальный элемент $d_{12}=1$,соответствующий ребру $(х_1,х_2)$. Так как локальная степень вершины $х_1$ на данном этапе равна 0, то включаем ребро $(х_1,х_2)$ в результат. Вычеркиваем первый и второй столбец, и рассматриваем 1-ю и 2-ю строки. Находим в них минимальный элемент $d_{23}=6$, соответствующий ребру $(x_2,x_3)$.Так как локальная степень $х_2$ равна 1, то мы можем включить данное ребро в результат. Вычеркиваем столбец 3 и рассматриваем 1-ю, 2-ю и 3-ю строки. В 3-й строке находятся сразу два минимальных элемента $d_{34}=d_{35}=1$. Выбираем любой из них, например $d_{34}$,соответствующий ребру $(х_3,х_4)$. Данное ребро также можно включить в результат,так как степень вершины хЗ равна 1. Вычеркиваем 4-й столбец и снова ищем минимальный элемент в 1-й, 2-й, 3-й и 4-й строках. Таким элементом является $d_{35}=1$, соответствующий ребру $(х_3,х_5)$. Но данное ребро не может быть включено в результат, так как степень вершины $х_3$ уже равна 2, и добавление ребра $(х_3,х_5)$ увеличит её еще на 1 ( т.е. нарушается ограничение на максимально допустимую локальную степень вершины). Поэтому элемент $d_{35}$ исключаем из рассмотрения и выбираем элемент $d_{45}=2$. После включения в результат ребра $(х_4,х_5)$ работа алгоритма заканчивается, так как в матрице выбраны все строки.

Решение алгоримом Краскала.

Решение той же задачи алгоритмом Краскала рассмотрим без ограничения на локальную степень вершины. Список ребер графа упорядочим по возрастанию длины ребра: $(х_1,х_2), (x_3,х_4),(х_3,х_5),(х_4,x_5), (х_2,х_3), (х_1,x_3),(x_2,x_4), (х_2,х_5), (х_1,х_4), (х_1,х_5)$. Включаем в результат ребра 1,2,3, ребро 4 в результат не входит, так как оно образует цикл с ранее включенными ребрами 2 и 3.

Следующим в результирующее дерево включается ребро 5. Ребра 6,7,8,9 и 10 из решения исключаются, так как они также образуют циклы.

Комментарии (0)

Комментировать могут только зарегистрированные пользователи

Подразделы
Новые статьи
Aрхив статей