Неориентированные дерево может быть

какая-то теория / деревья

Деревья Рассмотрим особый вид графов, называемый «деревом». Впервые ввел понятие деревьев физик Г. Кирхгофф в 1847 году. Будучи студентом Кёнигсбергского университета, он сформулировал законы, управляющие течением тока в электрических сетях. Сети проводов могут быть рассмотрены как графы. Уравнения, которые вытекают из законов Кирхгоффа, не являются независимыми, и Кирхгофф использовал деревья для получения независимого подмножества уравнений. Независимо от Кирхгоффа А. Кэли, перечисляя изомеры насыщенных углеводородов, еще раз ввел понятие деревьев и первым исследовал их свойства. Как чисто математический объект деревья были введены и исследованы К. Жорданом.

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

Свойства деревьев Теорема . Пусть граф G = (V, E) имеет n вершин и m ребер. Тогда эквивалентными являются такие утверждения: 1) G является деревом; 2) G является ациклическим графом и m = n −1; 3) G является связным графом и m = n −1; 4) любые две вершины графа G соединяет единственная простая цепь; 5) G является ациклическим графом, но добавление любого нового ребра способствует возникновению ровно одного цикла.

Деревья Следствие . В любом дереве с числом вершин n ≥ 2 имеется не менее двух концевых вершин. Следствие . Пусть G − лес с n вершинами и k компонентами, тогда G имеет n − k ребер. Теорема (теорема Кэли). Число различных деревьев, которые можно построить на n вершинах, равно

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

Остовное дерево Построение последовательности деревьев при нахождении остовного дерева алгоритмом поиска в ширину равносильно удалению лишних ребер в каждом цикле исходного графа. Число ребер, которые необходимо удалить в графе G для получения остовного дерева, называется цикломатическим числом графа G и обозначается v(G) .

Источник

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

В ряде случаев возникает необходимость в построении полного списка остовных деревьев графа 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, не меняя при этом ориентацию других дуг. Соответствующие изменения пометок будут таковы.

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

1. Пусть x_j = x_s и z = p_j.
2. Положить x_i = z, a z = p_i.
3. Шаг обновления: p_i = x_j.
4. Если x_i = r, то перейти к шагу 5. в противном случае положить x_j = x_i и перейти к шагу 2.
5. Положить 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₂, покажем, как надо «восстанавливать» корень в этом дереве.

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

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

1. Шаг обновления: 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). Тогда ребро принадлежит кратчайшему остову и может быть добавлено к другим ребрам частично сформированного кратчайшего остова. Многократное применение нижеследующей операции приводит к построению кратчайшего остова графа. Многие методы, позволяющие строить кратчайший остов графов, основываются на частных случаях описанной выше операции. Первый из таких методов был предложен Краскалом.

Источник