Стягивающее дерево графа это

Содержание

Каркасы графа. Алгоритм построения остовного дерева методом поиска в глубину
1.4.Стягивающие деревья (каркасы)
8.3 Поиск в ширину в графе
8.4 Стягивающие деревья (каркасы)

Каркасы графа. Алгоритм построения остовного дерева методом поиска в глубину

Каркас графа Лекция 3 Каркасы графа Каждый граф имеет каркас. Более того, у одного графа может быть несколько каркасов. Связный неориентированный граф называется деревом, если он не имеет циклов. Дерево не имеет петель и кратных ребер Остовное дерево или каркас графа — подграф: 1) содержит все вершины графа, 2) является деревом. Каркасы графа Каркас графа так же называют «Стягивающее дерево» или «Остовное дерево» Ребра графа, вошедшие в каркас будут называться ветвями, а не вошедшие в каркас- хордами. Каркасы можно строить как поиском в глубину, так и поиском в ширину. В любом случае достижение «новой» вершины u из «старой» вершины v означает включение ребра в каркас. Алгоритм построения остовного дерева методом поиска в глубину 1 procedure КАРКАС ГЛУБИНА(v) <поиск в глубину из вершины v, соединенный с нахождением ребра дерева; переменные НОВЫЙ, ЗАПИСЬ, T – глобальные>2 begin НОВЫЙ[v]:= ложь; 3 for u ЗАПИСЬ[v] do 4 if НОВЫЙ[u] then < (u, v) - новая ветвь>5 begin T := T + (v, u); КАРКАС ГЛУБИНА(u) end 6 end ; begin главная программа for u ∈ V do НОВЫЙ[u]:= истина; < инициализация>T := пусто; КАРКАС ГЛУБИНА(r) end. Докажем корректность этого алгоритма. Алгоритм строит СВЯЗНЫЙ граф, т.к. каждое новое ребро (v-u) продолжает уже существующий путь от к к v. Построенный граф не содержит ЦИКЛОВ. Каждая новая ветвь (v-u) соединяет уже рассмотренную v с НОВОЙ и. Чтобы замкнуть, цикл, требуется ребро, соединяющее две уже РАССМОТРЕННЫЕ вершины. Построенный граф содержит ВСЕ вершины графа G — это свойство поиска в глубину. По этой же причине вычислительная сложность алгоритма O(n+m). Свойства каркаса Любой каркас обладает важным свойством — от корня к до произвольной вершины v существует ровно ОДИН путь, состоящий из ветвей каркаса. Если бы их было два, получился» бы цикл, если бы ни одного, каркас не был бы связным. 2. Кроме того, если каркас D построен поиском в-глубину, то для двух вершин u и v, СОЕДИНЕННЫХ РЕБРОМ, всегда можно сказать: или v — потомок и, или и — потомок v (относительно каркаса D). Первое означает, что и лежит на пути из корня к в вершину v, второе — v на пути из к в и. Это легко доказать. Пусть одна из вершин, например,v просмотрена раньше и. Построен путь от корня к до v. Процесс поиска в глубину начинается с вершины v. Taк как и u v соединены ребром, то, рано или поздно, будет рассмотрена вершина u и построен путь от v до u. Получился путь k—v—u. Если v и и соединены ВЕТВЬЮ каркаса, то одна из них— СЫН, другая — ОТЕЦ. 1. Алгоритм построения остовного дерева методом поиска в ширину Данные: связный граф G= . представленный списками ЗАПИСЬ[v], v e V. Результаты: каркас D = графа G. •begin for u  Запись[V] do НОВЫЙ[u] :=истина; •T:=0 •ОЧЕРЕДЬ=NIL; ОЧЕРЕДЬ NIL do 7 begin v 1 выполнить: 6. < выбрать в Q ребро (v, w) наименьшей стоимости; 7. удалить (v, w) из Q; 8. если v и w принадлежат различным множествам W1 и W2 из VS то 9. < заменить W1 и W2 на W1W2 в VS; 10. добавить (v, w) к Т; >> Пример 23 4 1 9 3 17 Время работы: Cортировка рёбер — O(|E|×log|E|) Компоненты связности удобно хранить в виде системы непересекающихся множеств. Все операции в таком случае займут O(E) Получившееся дерево является каркасом минимального веса. Введем массив меток вершин графа Mark. Начальные значения элементов массива равны номерам соответствующих вершин (Mark[i] = i; i  1.. N). Ребро выбирается в каркас в том случае, если вершины, соединяемые им, имеют разные значения меток. Пример приведен на следующем слайде, изменения Mark показаны в таблице. Алгоритм Краскала с системой непересекающихся множеств Так же, как и в простой версии алгоритма Крускала, отсортируем все рёбра по неубыванию веса. Затем поместим каждую вершину в своё дерево (т.е. в своё множество) с помощью вызова функции MakeSet — на это уйдёт в сумме O (N). Перебираем все рёбра и для каждого ребра за O (1) определяем, принадлежат ли его концы разным деревьям (с помощью двух вызовов FindSet за O (1)). Наконец, объединение двух деревьев будет осуществляться вызовом Union — также за O (1). Итого мы получаем: O (M log N + N + M) = O (M log N). Реализация за O (M log N + N2) Отсортируем все рёбра в списках смежности каждой вершины по увеличению веса – O (M log N)). Для каждой вершины заведем указатель, указывающий на первое доступное ребро в её списке смежности. Изначально все указатели указывают на начала списков. На i-ой итерации перебираем все вершины, и выбираем наименьшее по весу ребро среди доступных. Поскольку всё рёбра уже отсортированы по весу, а указатели указывают на первые доступные рёбра, то выбор наименьшего ребра осуществится за O (N). После этого обновляем указатели (сдвигаем вправо), т.к. некоторые из них указывают на ставшие недоступными рёбра (оба конца которых оказались внутри дерева). На поддержание работы указателей требуется O (M) действий. Количество остовных деревьев графа • Количество остовных деревьев(каркасов) графа определяется матрицей Кирхгофа , а именно: алгебраическим дополнением любого элемента матрицы Кирхгофа. Матрица Кирхгофа • Матрица (n*n) • По диагонали – степени вершин • остальные элементы (i,j) при наличии ребра заполняются -1 1 2 3 4 1 1 -1 2 -1 3 -1 -1 3 -1 2 -1 4 -1 -1 2

Источник

1.4.Стягивающие деревья (каркасы)

Деревом называется произвольный неориентированный связный граф без циклов. Для произвольного связного неориентированного графа G = каждое дерево , где , будем назвать стягивающим деревом (каркасом или остовом) графа G. Ребра такого дерева являются ветвями, а все остальные ребра графа – хордами (очевидно это имеет смысл в контексте фиксированного стягивающего дерева). Следует отметить, что каждое дерево с n вершинами имеет n-1 ребер. Этот факт можно просто доказать, применяя индукцию относительно n.

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

WGD = proc (v:int; g:graph; НОВЫЙ:array of bool; T:stack)

modifies НОВЫЙ, T

effects 1. НОВЫЙ [v] = false

2. c = graph.fetch(g,v); i = circ.size(c)

3. пока i > 0

3.2. если НОВЫЙ[j], то

3.2.1. stack.pop(T,v); stack.pop(T,j)

3.2.2. WGD(j,g,НОВЫЙ,T)

иначе circ.change(c)

Рис.1.14.Процедура поиска в глубину в сочетании с нахождением ребра дерева.

Frame1 = proc(g:graph; r:int) returns(T:stack)

effects 1. для i = 1 до n НОВЫЙ[i] = true

3. WGD(r,g,НОВЫЙ,T)

Рис.1.15.Процедура нахождения стягивающего дерева связного графа методом поиска в глубину.

На рис.1.16 представлены результаты определения стягивающих деревьев для графа, представленного на рис.1.1.б в общем виде и на рис.1.5.а в виде «массива» кольцевых структур, начиная от 1-ой (рис.1.16.а) и 6-ой вершин (рис.1.16.б).

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

Для двух различных вершин v и u дерева будем считать, что u является потомком вершины v, если v лежит на пути (в дереве ) из u в корень. Если при этом имеет место v-u, то u – сын вершины v, v – отец вершины u.

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

Frame2 = proc (g:graph; r:int) returns (T:stack)

effects 1. для i = 1 до n НОВЫЙ[i] = true

5. НОВЫЙ[r] = false

6. пока not(intqueue.isempty(q))

6.1. v = intqueue.remfirst(q)

6.2. c = graph.fetch(g,v); i = circ.size(c)

6.3. пока i > 0

6.3.2. если НОВЫЙ[u], то

6.3.2.1. intqueue.append(q,u)

6.3.2.2. НОВЫЙ[u] = false

Рис.1.17.Процедура нахождения стягивающего дерева связного графа методом поиска в ширину.

На рис.1.18 представлены результаты определения стягивающих деревьев для графа, представленного на рис.1.1.б в общем виде и на рис.1.5.а в виде «массива» кольцевых структур, начиная от 1-ой (рис.1.18.а) и 6-ой вершин (рис.1.18.б).

Построение стягивающего дерева с помощью процедуры Frame2 обеспечивает следующее свойство. Пусть — стягивающее дерево связного графа , построенное при помощи Frame2. Тогда путь в из произвольной вершины v до корня r является к ратчайшим путем из v в r в графе G.

Источник

8.3 Поиск в ширину в графе

Рассмотрим несколько иной метод поиска в графе, называемый поиском в ширину (breadth first search). Этот метод основан, грубо говоря, на замене стека очередью. В этом случае чем раньше посещается вершина (помещается в очередь), тем раньше она используется (удаляется из очереди). Использование вершины происходит с помощью просмотра сразу всех еще непросмотренных соседей этой вершины.

8.4 Стягивающие деревья (каркасы)

Вспомним, что деревом называется произвольный неориентированный связный граф без циклов. Для произвольного неориентированного графа G = каждое дерево , где ТсЕ, будем называть стягивающим деревом или каркасом графа G. Ребра такого графа (дерева) назовем ветвями, а остальные ребра графа G будем называть хордами. Отметим, что каждое дерево с п вершинами имеет п-1 ветвь. (В каждую вершину, кроме корня, входит только одно ребро). Пусть имеем граф, в котором стягивающие деревья можно построить, например, способами а) и б) (рис. 29). а) 9 б) 9 8 ^ 67 8 ^ 67 3 4 3 4 2 2 1 1 Рис. 29 Два способа построения стягивающего дерева Процедуры поиска в глубину и в ширину можно использовать для нахождения стягивающих деревьев. В обоих случаях достижение из вершины v новой вершины u вызывает включение в дерево ребра . Рассмотрим алгоритм нахождения стягивающего дерева связного графа методом поиска в глубину. Пусть исходный граф G = задан списками инцидентности СПИСОК[v], v∈V. Алгоритм реализуем процедурой WGD(v):

PROCEDURE WGD(v);

BEGIN НОВЫЙ[v] := false;

Читайте также: Мирт адамово дерево семена

3 FOR u∈СПИСОК[v] DO

4 IF НОВЫЙ[u] THEN BEGIN

5 T := T ∪ ;

6 WGD(u)

7 END

8 END ;

Основная программа

1 BEGIN

2 FOR u∈V DO НОВЫЙ[u] := true;

3 Т:=0;

4 WGD( r )

5 END

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

в момент добавления к множеству Т новой ветви (строка 5 WGD) в дереве существует путь из r в v. Таким образом алгоритм строит связанный граф;

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

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

Следовательно, граф , построенный нашим алгоритмом, есть стягивающее дерево графа G. Очевидно, что вычислительная сложность алгоритма будет порядка С(n+m), т.е. того же порядка, что и поиск в глубину. Стягивающее дерево, построенное для нашего примера с помощью поиска в глубину, изображено на рис. 30,а. Вершина r, с которой начинается поиск, есть корень дерева. Очевидно, что в дереве существует в точности один путь от произвольной вершины к корню. Для двух различных вершин v и u дерева будем говорить, что u является потомком v, если v лежит на пути (в дереве) из u в корень. 8 а) 9У 7 б) / 1 \ 9
3 Рис. 30 Стягивающие деревья, построенные с помощью поиска в глубину и поиска в ширину Подобным же способом можно построить стягивающее дерево, используя метод поиска в ширину. Алгоритм, реализующий этот метод, можно записать так: 1 2 3 4 5 6 7 8 9 10 11 12 13 BEGIN FOR ueV DO НОВЫЙи] := trae; T := 0; ОЧЕРЕДЬ := 0; ОЧЕРЕДЬ г; НОВЫЙг] := false; г — корень стягивающего дерева> WHILE ОЧЕРЕДЬ Ф0 DO BEGIN v <= ОЧЕРЕДЬ; FOR иеСПИСОКи] DO IF НОВЫЙи] THEN BEGIN ОЧЕРЕДЬ и; НОВЫЙи] := false; Т := Т uи> END END END Путем рассуждений, которые приводили ранее, можно показать, что данный алгоритм корректно строит стягивающее дерево для произвольного связного графа за 0(n+m) шагов, т.е. за число шагов не более, чем С(n+m). На рис. 30,б приведено стягивающее дерево, построенное для нашего примера с помощью поиска в ширину. Преимущества процедуры поиска в ширину, о которых мы уже говорили, приводят к следующему выводу. Пусть Т> — стягивающее дерево произвольного связного графа G = , построенное с помощью алгоритма поиска в ширину. Тогда путь в Т> из произвольной вершины v к корню г является кратчайшим путем из v к г в графе G. Все рассуждения о стягивающих деревьях легко перенести на произвольные, не обязательно связанные графы. Максимальный подграф без циклов произвольного графа G называется стягивающим лесом графа G. Очевидно, что стягивающий лес графа с к компонентами связности определяется через стягивающие деревья этих компонент и, следовательно, содержит n-k-1 ребер. Тесно связана с задачей нахождения стягивающего дерева задача отыскания фундаментального множества циклов в графе.

Источник