Вводные определения
Граф, любая пара вершин которого может быть соединена маршрутом, называется связанным.
Связанный граф,не содержащий циклов,называется деревом. Если граф является взвешенным,то актуальной задачей является задача построения минимального дерева,т.е. дерева с минимальным суммарным весом его ребер.
При построении минимального дерева важнейшим ограничением является максимально допустимая степень вершины,т.е. максимальное количество ребер, инцидентных одной вершине в графе.Вес ребра определяется по расстоянию между инцидентными данному ребру вершинами.
Расстояние определяется в ортогональной метрике по следующей формуле: $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 вершинами графа.
Алгоритм состоит из следующей последовательности действий:
- В матрице D просматриваются элементы первой строки и выбирается минимальный элемент(например, элемент g-го столбца).
- Исключаются из рассмотрения 1-й и g-й столбцы и строится ребро, соединяющее 1-ю и g-ю вершины.
- Просматриваются 1-я и g-я строки и выбирается в одной из них минимальный элемент (если минимальных элементов несколько,то выбирается любой из них).
- Прежде чем построить ребро, соответствующее выбранному минимальному элементу,проверяется степень инцидентных ему вершин (например,g-й и r-й). Если степени данных вершин не превышают заданного ограничения,то данное ребро включается в строющееся дерево,в матрице вычеркивается r-й столбец,а к строкам в которых ищется минимальный элемент добавляется r-я строка и повторяются п.п. 3 и 4.
- Если ограничение на степень вершины нарушено,то соответствующий минимальный элемент вычеркивается из рассмотрения и повторяется выполнение п.З,т.е. ищется новый минимум.
- Матрица просматривается до тех пор,пока не будут включены все строки.
Алгоритм Краскала
Алгоритм Краскала может строить дерево одновременно для нескольких компонент связности,которые в процессе решения объединяются в одно связанное дерево.
Полный граф задается списком ребер. Перед работой список ребер сортируется по возрастанию длины.На каждом шаге просматривается список ребер,начиная с ребра,следующего за вошедшим в решение на предыдущем шаге, и к строящемуся поддереву присоединяют то ребро,которое не образует цикла с ребрами, ухе включенными в решение.
Алгоритм состоит из следующей последовательности действий:
- Создается список ребер R,содержащий длину ребра, номер исходной вершины ребра (i),номер конечной вершины ребра (j), признак включения данного ребра в дерево.
- Данный список упорядочивается в порядке возрастания длин ребер.
- Просматривается список R и выбирается из него ребро с минимальной длиной, еще не включенное в результирующее дерево и не образующее цикла с уже построенными ребрами.
- Если все вершины включены в дерево и количество ребер на единицу меньше количества вершин,то алгоритм свою работу закончил. В противном случае осуществляется возврат к пункту 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 из решения исключаются, так как они также образуют циклы.
