Как найти все остовные деревья графа

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

В ряде случаев возникает необходимость в построении полного списка остовных деревьев графа G. Например, в том случае, когда надо отобрать «наилучшее» дерево, а критерий, позволяющий осуществить такой отбор, является очень сложным (или даже частично субъективным), так что непосредственное решение задачи оптимизации (не использующее перечисление всех остовных деревьев) оказывается невыполнимым.

Число различных остовов полного связного неориентированного помеченного графа с n вершинами равно . Число различных остовов неориентированного графа без петель с n вершинами равно значению определителя , где B₀ — матрица инциденций с одной удаленной строкой (т.е. с n-1 независимыми строками), — транспонированная матрица к B₀.

Элементарные преобразования деревьев

Рассмотрим два (ориентированных или неориентированных) остовных дерева и графа . «Расстояние» между двумя деревьями обозначается через и определяется как число дуг из , которых нет в (или, что эквивалентно, как число дуг из , которых нет в , поскольку оба дерева и имеют дуг). Если , т.е. если

,

где и , то дерево можно получить из дерева удалив из дугу и добавив дугу . Такое преобразование дерева в дерево называется элементарным преобразованием дерева. На рис. 3 приведено дерево T₄, которое получено из дерева T₀ c помощью 4 элементарных преобразований: убрать (x₁, x₈) и добавить (x₅, x₈); убрать (x₅, x₆) и добавить (x₆, x₇); убрать (x₂, x₃) и добавить (x₂, x₄); убрать (x₃, x₅) и добавить (x₄, x₅).

Рис.3. Остовы T₀ и T₄.

Существует теорема, согласно которой дерево T_k может быть получено из дерева T₀ с помощью серий из k элементарных преобразований при =k.

Процедура порождения всех деревьев неориентированного графа

Первый шаг состоит в приписывании номеров ребрам графа G (ребра нумеруются от 1 до m, где m — число ребер в графе G). На каждом этапе (т. е. при каждом ветвлении в дереве решений) выбирается ребро, которое вместе с остальными, выбранными уже на предыдущих этапах, будет образовывать часть конструируемого дерева. Таким образом, прежде чем отобрать такое ребро, выясняют, действительно ли добавление его к частично сформированному дереву (которое на этом шаге является набором поддеревьев) не приводит к появлению цикла. Если цикл появляется, то данное ребро отбрасывается и проверке подвергается следующее ребро, с большим номером. Если цикла нет, то ребро добавляется к другим, уже отобранным, и процесс продолжается до тех пор, пока не будет построено остовное дерево. Ребра перебираются в порядке возрастания их номеров; это приводит к исчерпывающему и без повторений решению задачи.

Для облегчения манипуляций с поддеревьями в каждом поддереве выделяют произвольным образом корень (некоторую вершину поддерева) и затем рассматриваю поддерево уже как древовидность. Для организации проверки на возможность образования (при добавлении ребра) каждую вершину x_j помечают парой (r_j, p_j). Первая пометка r_j указывает «корень» поддерева, содержащего вершину x_j. Первоначально r_j = x_j для всех вершин x_j. На некотором шаге два поддерева T₁, и T₂ сращиваются посредством добавления ребра a_l=(x_a, x_b) с вершиной x_a из T₁ и вершиной x_b из T₂. Если на этом шаге r₁ — «корневая» пометка вершин в T₁, а r₂ — «корневая» пометка вершин в T₂ и для примера r₁ < r₂, то все вершины в T₂, должны «сменить» свои корневые пометки на r₁, и два поддерева T₁ и T₂ «сольются» в единственное новое дерево T₁.

Вторая пометка p_j, приписанная вершине x_j, указывает вершину, предшествующую вершине x_j, т.е. если =(x_k, x_j) — дуга рассматриваемого поддерева, то p_j = x_k. Для корневой вершины дерева такая пометка полагается равной нулю.

А. Замена корня дерева

Если корнем дерева T является вершина r и нужно в качестве корня выбрать новую вершину x_s, то такую «замену» r на x_s можно осуществить простым обращением ориентации дуг, принадлежащих цепи, идущей от r к x_s, не меняя при этом ориентацию других дуг. Соответствующие изменения пометок будут таковы.

Изменение пометок «предшествования»

Пусть x_j = x_s и z = p_j.

Положить x_i = z, a z = p_i.

Шаг обновления: p_i = x_j.

Если x_i = r, то перейти к шагу 5. в противном случае положить x_j = x_i и перейти к шагу 2.

Положить p_s = 0, стоп.

Изменение корневых пометок

У всех вершин, имеющих корневую пометку r, заменить ее на пометку x_s.

Б. Сращивание двух поддеревьев

Если осуществлено сращивание двух поддеревьев T₁ и T₂ (путем добавления ребра (x_a, x_b)), то в пометки необходимо внести следующие изменения:

(1) У вершин с корневой пометкой r₂ заменить эту пометку на r₁.

(2) Заменить в дереве T₂ корень r₂ на x_b (пункт А), после чего изменить пометку «предшествования» у вершины x_b с p_b = 0 на p_b = x_a.

B. Расщепление дерева на две части

Поскольку метод порождения деревьев, рассматриваемый ниже, является поиском, использующим дерево решений, то возникает необходимость удаления некоторых ребер (на шагах возвращения), чтобы испытать затем другие ребра. В такой ситуации удаление ребра приводит к расщеплению некоторого дерева на две части, например на T₁ и T₂, и в пометки одного из этих поддеревьев должны быть внесены изменения. Пусть удаляется ребро (x_a, x_b), где x_aÎT₁ и x_bÎT₂. Тогда при p_b = x_a (т. е. если ребро (x_a, x_b) в первоначальном дереве ориентировано от x_a к x_b) пометки в дереве T₁, можно оставить прежними, а пометки в дереве T₂ должны быть изменены. Если же p_a = x_b (т. е. ребро (x_a, x_b) ориентировано от x_b к x_a), то можно не менять пометки в дереве T₂, но нужно изменить пометки в T₁. Предполагая, что пометки меняются в дереве T₂, покажем, как надо «восстанавливать» корень в этом дереве.

Положить S = <x_b> и p_b = 0 (x_b будет корнем дерева T₂).

Найти все вершины x_j с p_jÎS и изменить их корневые пометки на r_j = x_b. Если таких вершин нет, остановиться.

Шаг обновления: S = S È <x_j | p_jÎS>; вернуться к шагу 2.

Следует отметить, что ни у одной вершины, кроме нового корня x_b, пометки предшествования менять не нужно. Заметим также, что число описанных выше шагов 2 и 3, которое необходимо для восстановления корня, равно длине самой длинной цепи в T₂ исходящей из вершины x_b.

Описание алгоритма. Возьмем произвольную вершину x * графа G. Пусть ее степень равна d * . Перенумеруем ребра, инцидентные этой вершине: a₁, a₂, …, a_d*. Затем перенумеруем остальные ребра графа G: a_d*+1, a_d*+2, …, a_m. При порождении деревьев ребра будут перебираться в соответствии с введенной нумерацией.

Шаг 1. Приписать вершинам пометки: (r_i, p_i), где r_i=x_i и p_i=0, «x_iÎX. Положить k=1.

Шаг 2. Выбрать для исследования некоторое ребро. Например, a_k=(x_i, x_j). Если k≤m, где m — число ребер графа, то перейти к 2 (1). При k=m+1, т. е. если «неисследованных» ребер нет, перейти к шагу 5.

(1) Если r_i=r_j, то это означает, что вершины x_i и x_j принадлежат одному и тому же поддереву и добавление ребра a_k приведет к появлению цикла. Отбросить ребро a_k, т. е. положить k=k-1 и вернуться к шагу 2.

(2) Если r_i≠r_j то ребро a_k можно добавить к ребрам построенных поддеревьев. Перейти к шагу 3.

Шаг 3. Срастить два поддерева, у которых вершины имеют корневые пометки r_i и r_j, применив для этого метод, описанный выше в пункте Б.

Шаг 4. Отобрав n-1 ребер, мы получаем некоторое дерево. Заполнить это дерево и перейти к шагу 5. Если отобрано меньше, чем n-1 ребер, то положить k=k+1 и вернуться к шагу 2.

Шаг 5. (Возвращение.) Удалить ребро, добавленное последним. Предположим, что таким ребром является a_l. Если a_l — единственное оставшееся для добавления ребро, l=d * то остановиться. Все остовные деревья, таким образом построены, т. к. при любом дальнейшем ветвлении дерева решений вершина x * останется изолированной.

В противном случае надо обновить пометки, действуя так, как указано в пункте B, положить k=l-1 и возвратиться к шагу 2.

Построим все остовные деревья графа, изображенного на рис.4. Выберем в качестве x * вершину x₁.

Рис.4. Граф G.

На рис.5 изображено соответствующее дерево решений, которое порождено в процессе работы алгоритма. Если взять ребра, указанные в кружочках какой-либо цепи, выходящей из верхнего узла этого дерева и оканчивающейся в самом нижнем узле, то из них можно построить некоторый остов данного графа. Эти остовы перенумерованы числами от 1 до 21 и приведены на рис.6.

Рис.5. Полное дерево поиска.

Рис.6. Все остовы графа G.

Кратчайший остов графа

Рассмотрим взвешенный связный неориентированный граф G=(X, A); вес ребра (x_i, x_j) обозначим c_ij. Из большого числа остовов графа нужно найти один, у которого сумма весов ребер наименьшая. Такая задача возникает, например, в том случае, когда вершины являются клеммами электрической сети, которые должны быть соединены друг с другом с помощью проводов наименьшей общей длины (для уменьшения уровня наводок). Другой пример: вершины представляют города, которые нужно связать сетью трубопроводов; тогда наименьшая общая длина труб, которая должна быть использована для строительства (при условии, что вне городов «разветвления» трубопроводов не допускаются), определяется кратчайшим остовом соответствующего графа.

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

Задача построения кратчайшего остова графа является одной из немногих задач теории графой, которые можно считать полностью решенными. Итак, пусть T_i и T_j — два произвольных поддерева, полученных путем добавления ребер при построении кратчайшего остова графа. Определим D_ij, как кратчайшее из расстояний между вершинами из T_i и вершинами из T_j следующим образом:

, i≠j. (1)

Зададим следующую операцию: Для поддерева T_s найти такое поддерево T_j*, чтобы . Пусть будет тем ребром, вес которого соответствует величине в выражении (1). Тогда ребро принадлежит кратчайшему остову и может быть добавлено к другим ребрам частично сформированного кратчайшего остова.

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

Алгоритм Краскала, Прима для нахождения минимального остовного дерева

Алгоритмы нахождения MST применимы в различных областях, начиная от кластеризации данных до построения компьютерных, транспортных сетей.
Я надеюсь, что вы после прочтения данной статьи, примерно понимали, как работают жадные алгоритмы нахождения MST.

Формальная постановка задачи

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

Исходный граф

Неформальная постановка задачи

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

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

Механизм, по которому работает данный алгоритм, очень прост. На входе имеется пустой подграф, который и будем достраивать до потенциального минимального остовного дерева. Будем рассматривать только связные графы, в другом случае при применении алгоритма Краскала мы будем получать не минимальное остовное дерево, а просто остовной лес.

Вначале мы производим сортировку рёбер по неубыванию по их весам.

Добавляем i-ое ребро в наш подграф только в том случае, если данное ребро соединяет две разные компоненты связности, одним из которых является наш подграф. То есть, на каждом шаге добавляется минимальное по весу ребро, один конец которого содержится в нашем подграфе, а другой — еще нет.

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

Данный алгоритм называется жадным из-за того, что мы на каждом шаге пытаемся найти оптимальный вариант, который приведет к оптимальному решению в целом.

Разбор конкретного примера по шагам

Из представленного сверху графа, выпишем все его ребра в отсортированном порядке:

1) D <—> B; w = 2
2) D <—> C; w = 6
3) A <—> B; w = 7
4) A <—> C; w = 8
5) C <—> E; w = 9
6) D <—> F; w = 9
7) F <—> E; w = 10
8) B <—> C; w = 11
9) D <—> E; w = 11

И начнем по списку добавлять эти ребра в наш остов:

Подграф после добавиления 1-го ребра Подграф после добавления 2-го и 3-го рёбер

При добавлении в наше остовное дерево ребра A <—> C, как вы можете заметить, образовывается цикл, поэтому мы просто пропускаем данное ребро.

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

Минимальный остов

Проводим проверку с помощью встроенного алгоритма для нахождения MST на graphonline, и видим, что подграфы идентичны.
И да, из-за того, что при равенстве весов рёбер мы можем выбрать любое из них, конечные подграфы, являющиеся минимальными остовными деревьями, могут различаться с точностью до некоторых рёбер.

Провели проверку

Суммарный вес искомого MST равен 33.

Реализация

Реализовать представленный алгоритм проще всего с помощью СНМ(система непересекающихся отрезков).

Вначале, как мы уже раннее говорили, необходимо отсортировать ребра по неубыванию по их весам. Далее с помощью вызовов функции make_set() мы каждую вершину можем поместить в свое собственное дерево, то есть, создаем некоторое множество подграфов. Дальше итерируемся по всем ребрам в отсортированном порядке и смотрим, принадлежат ли инцидентные вершины текущего ребра разным подграфам с помощью функции find_set() или нет, если оба конца лежат в разных компонентах, то объединяем два разных подграфа в один с помощью функции union_sets().

В итоге асимптотическая сложность данного алгоритма сводится к:

, где:
sort() —
make_set()-
find_set —
union_sets —

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

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

Изначально наш подграф состоит из одной любой вершины исходного графа.

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

Продолжаем выполнять предыдущий шаг до тех пор, пока не найдем искомое MST.

Разбор конкретного примера

Выбираем чисто случайно вершину E, далее рассмотрим все ребра исходящие из нее, включаем в наше остовное дерево ребро C <—> E; w = 9, так как данное ребро имеет минимальный вес из всех рёбер инцидентных множеству вершин нашего подграфа. Имеем следующее:

Подграф после добавления 1-го ребра

Теперь выборка производится из рёбер:
D <—> C; w = 6
A <—> C; w = 8
F <—> E; w = 10
B <—> C; w = 11
D <—> E; w = 11

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

Добавляем в наш подграф ребро D <—> C и по аналогии добаляем ребро D <—> B . Получаем следующее:

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

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

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

Искомое минимальное остовное дерево

GRAFY_Lab#3

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

Рассмотрим неориентированный граф G=(X,U) с n вершинами. Следующие определения дерева, как легко показать, эквивалентны друг другу:

i. связный граф, не имеющий циклов;

ii. связный граф, содержащий n вершин и n-1 ребер;

iii. граф, в котором каждая пара вершин соединена одной единственной простой цепью.

Граф G 1 =(X 1 ,U 1 ) называется подграфом (или частью) графа G=(X,U), если , . Подграф G 1 называется остовным подграфом, если .

Остовным деревом (или остовом) графа G называется всякий остовный подграф графа G, являющийся деревом. Например, если G – граф, показанный на рис. 1.а, то граф, на рис. 1.б является остовом графа G, как и граф, изображенный на рис. 1.в.

рис. 1.а рис. 1.б рис. 1.в

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

Теорема 1. Пусть G – n-вершинный граф без петель и – его матрица инциденций с одной удаленной строкой (т.е. с n-1 независимыми строками). Пусть – транспонированная матрица к . Тогда определитель равен числу различных остовных деревьев графа G.

Теорема 2. При n>1 число остовов в полном графе равно .

II. Практический пример.

• Задача :

Найти все остовные деревья в графе.

• Решение :

1.) Т.к. нам дан полный граф с числом вершин n=4 , то используя Теорему 1 сможем найти количество всех остовов:

K_n = n n -2 = 4 2 = 16

2.) Находим все остовные деревья графа:

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

Кратчайший остов графа (остов минимального веса).

Рассмотрим взвешенный связный неориентированный граф G=(X,U); вес ребра (x_i, x_j) обозначим c_ij. Из большого числа остовов графа нужно найти один, у которого сумма весов ребер наименьшая. Такая задача возникает, например, в том случае, когда вершины являются клеммами электрической цепи которые должны быть соединены друг с другом с помощью проводов наименьшей общей длины (для уменьшения уровня наводок).

Аналогично, при проектировании линий электропередачи, трубопроводов, дорог и т.п., требуется заданные центры соединить некоторой системой каналов связи так, чтобы длина (или, например, стоимость) каналов связи была минимальной. В этой ситуации заданные центры можно считать вершинами полного графа с весами ребер, равными длинам (стоимости) соединяющих эти центры каналов. Тогда искомая сеть будет кратчайшим остовным подграфом полного графа.

Поскольку полный граф содержит различных остовных деревьев, то решение этой задачи «слепым” перебором вариантов потребовало бы чрезвычайно больших вычислений даже при относительно малых n. Однако для ее решения имеются эффективные алгоритмы.

Воспользуемся алгоритмом Р. Прима ( 1957 г .), применимый к произвольному связному графу

Шаг 1. Выбираем ребро минимального веса и строим дерево .

Шаг 2. Если дерево порядка уже построено и , то среди ребер, соединяющих вершины этого дерева с вершинами графа G=(X,U), не входящими в , выбираем ребро минимального веса. Строим дерево , присоединяя к ребро вместе с его не входящим в концом.

IV. Текст программы.

V. Вывод.

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

Как найти все остовные деревья графа

В некоторых ситуациях возникает необходимость в построении полного списка остовных деревьев графа Например, в том случае, когда надо отобрать «наилучшее» дерево, а критерий, позволяющий осуществить такой отбор, является очень сложным (или даже частично субъективным), так что непосредственное решение задачи оптимизации (не использующее перечисление всех остовных деревьев) оказывается невыполнимым. В других ситуациях, например при нахождении передаточной функции системы [42,6] или при вычислении определителей некоторых матриц в макроэкономической теории [2], с помощью порождения всех остовов соответствующих графов можно добиться упрощения вычислительных процедур.

Число различных остовов полного связного неориентированного помеченного графа с вершинами было найдено впервые Кэли [4]. Оно равно . У Муна [45] приводится список из более чем 25 работ, содержащих разнообразные доказательства этой формулы. (См. также задачу 6.) Формулы для числа остовов в более общих графах можно найти у Риордана [49]. Хотя эти формулы, как правило, очень сложные и их вывод для наших целей не нужен, но стоит, пожалуй, привести следующий результат.

Теорема 1. Пусть -вершинный граф без петель и его матрица инциденций с одной удаленной строкой (т. е. с независимыми строками). Пусть транспонированная матрица к Тогда определитель равен числу различных остовных деревьев графа

Доказательство этой теоремы можно найти в [53] и в [1] (см. также задачу 5).

2.1. Элементарные преобразования деревьев

Рассмотрим два (ориентированных или неориентированных) остовных дерева и графа «Расстояние» между двумя деревьями обозначается через и определяется как число дуг из которых нет в (или, что эквивалентно, как число дуг из которых нет в поскольку оба дерева имеют дуг). Если т. е. если

где то дерево можно получить из дерева удалив из дугу и добавив дугу Такое преобразование дерева в дерево называется элементарным преобразованием дерева.

Теорема 2. Если остовные деревья графа и , то дерево может быть получено из с помощью серий из к элементарных преобразований.

Доказательство. Пусть дуг из которых нет в Тк, и к дуг из Тк, которых нет в Если в дерево добавить дугу то в получившемся графе, согласно определению дерева, найдется цикл. (На рис. жирными линиями показано неориентированное дерево а пунктирной линией — дуга дерева приведенного на рис. 7.5(д).) В полученном цикле содержится по крайней мере одна дуга, не принадлежащая дереву Тк. Следовательно, ее можно удалить, разорвав тем самым цикл, и это даст новое дерево Поскольку в число дуг, общих с дугами из Тк, на единицу больше (чем в ), то Применяя элементарные преобразования дальше, получим последовательность деревьев , в которой для каждого . На рис. 7.5(б) — (д) показано, как с помощью 4 элементарных преобразований из дерева получается дерево