Деревья. Алгоритм Краскала

1. Деревья. Алгоритм Краскала

1. Деревья и их свойства.
2. Алгоритм Краскала нахождения минимального
остовного дерева

2.

ПОВТОРЕНИЕ
Граф – это множество точек, называемых вершинами, и множество
линий, называемых ребрами, которые соединяют пары вершин (или
вершину саму с собой).
Граф называется связным, если для любых двух его вершин
имеется путь, соединяющий эти вершины.
Маршрутом в графе называется последовательность вершин и
ребер, начинающаяся и заканчивающаяся вершиной
Маршрут, в котором все ребра различны, называется цепью
(путем)
Длиной маршрута называется количество ребер в нем.
Расстоянием между вершинами u, v (обозначается s(u,v))
называется наименьшая длина цепи < u,v >

3.

ОПРЕДЕЛЕНИЕ ДЕРЕВА
Деревом называется связный граф с выделенной вершиной
(корнем), не содержащий циклов.
Дерево не имеет петель и кратных (параллельных) рёбер (т.к
кратные рёбра, инцидентные одним и тем же двум вершинам,
образуют цикл).

4.

СВОЙСТВА ДЕРЕВЬЕВ
Для каждой пары вершин дерева
(узлов) существует единственный
маршрут, поэтому вершины удобно
классифицировать по степени
удаленности от корневой вершины.
Расстояние до корневой вершины V0 называется ярусом s
вершины, s = d(V0,V).
В дереве любые две вершины связаны единственной цепью
Любая ветвь дерева является мостом – при ее удалении граф
распадается на две части (два подграфа)
Узел без поддеревьев называется листом и является висячей
вершиной.

5.

СВОЙСТВА ДЕРЕВЬЕВ
Граф G(V, X ) является деревом тогда и только тогда, когда
выполняется хотя бы одно из условий:
граф G(V,X ) связан и не содержит циклов;
граф G(V, X ) не содержит циклов и имеет n –1 ребро;
граф G(V, X ) связан и имеет n –1 ребро;
граф G(V, X ) не содержит циклов, но добавление ребра
между несмежными вершинами приводит к появлению одного
и только одного элементарного цикла;
граф G(V, X ) связный, но утрачивает это свойство после
удаления любого ребра;
в графе G(V, X ) всякая пара вершин соединена цепью, и
притом только одной.
Дерево с n вершинами имеет n –1 ребро, поэтому оно будет
минимальным связным графом.

6.

Дерево с n вершинами имеет n –1 ребро, поэтому оно будет
минимальным связным графом.

7.

Лес – это граф, компоненты
которого являются деревьями.
Узел без поддеревьев называется листом и является висячей
вершиной.
Дерево, в котором каждый узел либо является листом, либо
образует два поддерева (левое и правое), называется бинарным

8.

Бинарное дерево называется деревом поиска, если его
элементы расположены так, что для каждого элемента n все
элементы в левом поддереве будут меньше, чем n, а все
элементы в правом поддереве - больше, чем n.
20, 10, 35, 15, 17, 27, 24, 8, 30
20
10
8
35
27
15
17
24
30

9.

Пирамида - это такое двоичное дерево, для которого выполнены
три условия:
- Значение в любой вершине больше, чем значения ее потомков.
- Все слои, кроме, может быть, последнего, заполнены
полностью.
- Последний слой заполняется слева направо.
16, 11, 9, 10, 5, 6, 8, 1, 2, 4
16
11
9
10
1
5
2
4
6
8

10.

СЕТИ. СЕТЕВЫЕ МОДЕЛИ
ПРЕДСТАВЛЕНИЯ ИНФОРМАЦИИ
Граф называется взвешенным или сетью, если каждому его
ребру поставлено в соответствие некоторое число (вес).
Взвешенными графами могут быть схемы в электронике,
электрические схемы, схемы компьютерных сетей, карты
автомобильных и железных дорог и др.
На картах автодорог вершины являются населенными пунктами,
ребра — дорогами, а весом — числа, равные расстоянию между
населенными пунктами.
Ребрам графа могут соответствовать числа, означающие
длину, уклон, запланированное время и другие
характеристики.

11.

АЛГОРИТМ КРАСКАЛА
Остов графа (стягивающее дерево, spanning tree) – дерево,
полученное из графа, выбрасыванием части ребер.
Имеется n сельских домов, которые нужно объединить в единую
компьютерную сеть. Для этого достаточно проложить (n-1)
линий между домами. Как соединить дома так, чтобы
суммарная стоимость соединений (кабеля) была минимальна?

12.

ПОСТАНОВКА ЗАДАЧИ
Дан связный неориентированный граф G(V;E), и каждой его дуге
е сопоставлено некоторое число, называемое весом или
длиной этой дуги. Сумму весов дуг дерева в дальнейшем
будем называть весом дерева или его множества дуг. Требуется
найти такое остовное дерево Т, содержащего все вершины
графа G, у которого вес был бы минимален. Такое дерево будет
называться минимальным остовным деревом.
Суммарный вес равен
4 + 7 + 5 + 10 + 11 = 37

13.

ОПИСАНИЕ АЛГОРИТМА
1. Вначале текущее множество рѐбер устанавливается
пустым.
2. Затем, пока это возможно, проводится следующая
операция:
из всех рѐбер, добавление которых к уже
имеющемуся множеству не вызовет появление в нѐм
цикла, выбирается ребро минимального веса и
добавляется к уже имеющемуся множеству.
Когда таких рѐбер больше нет, алгоритм завершѐн. Подграф
данного графа, содержащий все его вершины и найденное
множество рѐбер, является его остовным деревом
минимального веса

14.

начало
выбор первого ребра с
минимальным весом
выбор следующего ребра с
минимальным весом
ребро создаст
цикл?
нет
добавить ребро в остовное
дерево
да
да
еще есть
ребра?

15.

ПРИМЕР
Ребра AD и CE имеют минимальный
вес, равный 5. Произвольно
выбирается ребро AD
Теперь наименьший вес, равный 5,
имеет ребро CE. Так как добавление
CE не образует цикла, то выбираем
его в качестве второго ребра

16.

ПРИМЕР
Аналогично выбираем ребро DF, вес
которого равен 6
Следующие ребра — AB и BE с весом
7. Произвольно выбирается ребро
AB, выделенное на рисунке.
Ребро BD (выделено красным)
ВЫБИРАТЬ ЗАПРЕЩЕНО, так как будет
образован цикл ABD

17.

ПРИМЕР
Аналогичным образом выбирается
ребро BE, вес которого равен 7.
ВЫБИРАТЬ ЗАПРЕЩЕНО:
(выделено красным)
BC - создаст цикл BCE,
DE - создаст цикл DEBA,
FE - сформирует цикл FEBAD.
Алгоритм завершается добавлением
ребра EG с весом 9. Минимальное
остовное дерево построено.

18.

Пример:

19.

Пример:

20.

Пример:
1
2
8
1
2
3
8
6
7
3
1
8
1
6
4
5
5
4

21.

Пример:
1
2
8
7
8
8
6
6
3
1
5
1
5
4
2
8
6
6
3
1
5
1
5
4
4
1
2
3
8
6
6
3
1
5
1
3
7
8
4
1
2
8
7
8
2
3
1
2
8
1
1
5
4
4

22.

Пример:

23. Контрольные вопросы:

1. Что называется деревом в графе?
2. Опишите свойства деревьев.
4. Что называется бинарным деревом?
5. Что называется цикломатическим числом графа? Чему
равно это число в дереве? Лесе?
6. Какой граф называется сетью?
7. Что называется весом или длиной дуги?
8. Дайте определение остов графа.
9. Дайте определение минимальный остов графа.
10. В чем смысл алгоритма Краскала?