Материал: Решение задач теории графов методические указания к практическим занятиям по дисциплине «Дискретная математика». Белецкая С.Ю

3. Построение остовных деревьев графа

3.1. Теоретические сведения

Связный ациклический граф, имеющий не менее двух вершин, называется деревом. Ориентированным деревом называется орграф без циклов, в котором имеется вершина x₀, из которой существует только один ориентированный путь в любую другую вершину. Деревом графа G называется любой его связный ациклический подграф. называется остовным деревом (остовом) Т графа G. При этом ребра остовного дерева T называются ветвями, а ребра графа G, не принадлежащие остову T - хордами. На рис 6. а представлен граф G, на рис. 6. б - одно из его деревьев, на рис. 6 в, г - два остова T₁ и T₂ графа G, на рис. 6. д - остовное 2 - дерево (лес) графа G.

а б в г д

Рис. 6

Очевидно, что в любом графе существует остов, причем в общем случае остов может быть выделен не единственным способом.

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

Опишем алгоритм поиска в глубину (этот метод стал одной из основных методик проектирования графовых алгоритмов). Поиск начинается с некоторой фиксированной вершины x_o, например, с висячей. Затем выбирается вершина x₁, смежная с x_o. После этого выбирается вершина x₂, смежная с x₁, и т.д. Ещё не просмотренные вершины будем условно называть новыми. Если на k-м шаге поиска для вершины x_k существует новая вершина x_k+1, то она выбирается (перестаёт быть новой) и поиск продолжается от вершины x_k+1. Если же для вершины x_k новых вершин не существует, осуществляется возврат к вершине, из которой мы попали в x_k, и поиск осуществляется от неё. Процесс продолжается до тех пор, пока не будет произведён возврат в вершину x_o. В процессе поиска вершины соединяют рёбрами.

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

Рассмотренные алгоритмы могут быть использованы для построения всех остовных деревьев графа.

При конструкторском и топологическом проектировании РЭА и ЭВА, создании вычислительных сетей важное значение имеет задача определения кратчайшего остова (остова минимального веса) взвешенного графа. Кратчайшим остовом взвешенного графа G будем называть остов, у которого сумма весов всех ребер наименьшая.

Для построения кратчайшего остова графа используются алгоритмы Краскала и Прима.

Алгоритм Краскала заключается в следующем. На начальном этапе из всех ребер графа G выбирается ребро минимального веса и включается в остов. На каждом последующем i-м шаге из еще не включенных в остов ребер выбирается ребро, имеющее минимальный вес и не составляющее циклов с уже выбранными ребрами. Процесс продолжается до тех пор, пока в остов не будет включено n-1 ребро.

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

3.2. Примеры решения задач

Задача 1. Построить остовное дерево графа с использованием стратегий поиска в глубину и ширину.

Рис. 7

Решение.

1. Поиск в глубину.

Начинаем поиск с любой вершины, допустим, с x₁. Выбираем вершину, смежную с x₁, например x₂. Вершины x₁ и x₂ соединяем ребром. Далее выбираем вершину x₃, смежную с x₂. Вершины x₂ и x₃ соединяем ребром. Продолжая двигаться дальше, соединяем вершины x₃ и x₄. У вершины x₄ три смежных вершины - x₅,x₇ и x₈. Для продолжения поиска можно выбрать любую из них, например x₅ . Соединяем ребром вершины x₅ и x₆, а затем x₆ и x₇. Попав в вершину x₇, видим, что смежной с ней является вершина x₄. Но продолжать поиск в данном направлении нельзя, так как вершина x₄ уже была просмотрена. Согласно алгоритму возвращаемся в предыдущую вершину, то есть в x₆. Так как у x₆ нет новых вершин, то возвращаемся в вершину x₅. Аналогично из x₅ переходим в вершину x₄. Вершина x₈ является новой, поэтому, согласно алгоритму, выбираем вершину x₈ и соединяем вершины x₄ и x₈ ребром, затем соединяем x₈ и x₉. У x₉ нет новых вершин, кроме x₁, но соединить эти вершины мы не можем, так как граф тогда не будет остовом. Мы просмотрели все вершины графа G. Возвращаемся в вершину x₁. Найденный остов графа G представлен на рис. 8, а.

2. Поиск в ширину.

Начинаем поиск с любой вершины, например с x₁. Соединяем ребрами вершину x₁ со всеми смежными ей вершинами - x₂, x₄ и x₉. Теперь по порядку рассматриваем эти смежные вершины. Берем вершину x₂. Соединяем её со всеми смежными ей вершинами, то есть с x₃. Следующая по порядку вершина x₄. Соединяем её со смежными вершинами, то есть с x₅, x₇ и x_8. Затем по порядку идет вершина x₉, но соединить её со смежной вершиной x₈ мы не можем, так как полученный граф не будет являться остовом. Далее рассматриваем вершины x₅, x₇ и x_8. У x₅ есть смежная вершина x₆. Соединяем их ребром. У вершин x₇ и x₈ нет таких смежных вершин. Таким образом, мы получили один из остовов графа G (рис. 8, б).

а б

Рис. 8

Задача 2. С использованием алгоритмов Краскала и Прима построить кратчайший остов для графа

Рис. 9

Решение Кратчайший остов для данного графа имеет следующий вид:

В таблицах приводится последовательность выбора ребер остовного дерева с использованием алгоритмов Краскала и Прима.

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

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

Суммарный вес построенного остова равен 125.

3.3. Упражнения

1. Для заданных графов построить остовные деревья с использованием стратегий поиска в глубину и в ширину

а б

Рис. 10

2. Построить кратчайшее остовное дерево с использованием алгоритмов Краскала и Прима для следующих графов: