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

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

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

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

Расстояние определяется в ортогональной метрике по следующей формуле: 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

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

Просматриваем первую строку матрицы расстояний и находим минимальный элемент d₁₂=1,соответствующий ребру (х₁,х₂). Так как локальная степень вершины х₁ на данном этапе равна 0, то включаем ребро (х₁,х₂) в результат. Вычеркиваем первый и второй столбец, и рассматриваем 1-ю и 2-ю строки. Находим в них минимальный элемент d₂₃=6, соответствующий ребру (x₂,x₃).Так как локальная степень х₂ равна 1, то мы можем включить данное ребро в результат. Вычеркиваем столбец 3 и рассматриваем 1-ю, 2-ю и 3-ю строки. В 3-й строке находятся сразу два минимальных элемента d₃₄=d₃₅=1 . Выбираем любой из них, например d₃₄,соответствующий ребру (х₃,х₄). Данное ребро также можно включить в результат,так как степень вершины х_З равна 1. Вычеркиваем 4-й столбец и снова ищем минимальный элемент в 1-й, 2-й, 3-й и 4-й строках. Таким элементом является d₃₅=1, соответствующий ребру (х₃,х₅). Но данное ребро не может быть включено в результат, так как степень вершины х_З уже равна 2, и добавление ребра (х₃,х₅) увеличит её еще на 1 ( т.е. нарушается ограничение на максимально допустимую локальную степень вершины). Поэтому элемент d₃₅ исключаем из рассмотрения и выбираем элемент d₄₅=2. После включения в результат ребра (х₄,х₅) работа алгоритма заканчивается, так как в матрице выбраны все строки.

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

Решение той же задачи алгоритмом Краскала рассмотрим без ограничения на локальную степень вершины. Список ребер графа упорядочим по возрастанию длины ребра:(х₁,х₂), (x₃,х₄),(х₃,х₅),(х₄,x₅), (х₂,х₃), (х₁,x₃),(x₂,x₄), (х₂,х₅), (х₁,х₄), (х₁,х₅). Включаем в результат ребра 1,2,3, ребро 4 в результат не входит, так как оно образует цикл с ранее включенными ребрами 2 и 3 .

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