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

1.

Деревья. Алгоритм
Краскала
1. Деревья и их свойства.
2. Алгоритм Прима нахождения минимального
остовного дерева
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.

Цикломатическое число
Цикломатическое число γ показывает, сколько ребер нужно удалить из
графа, чтобы в нем не осталось циклов
γ = m – n + 1,
m - количество ребер
n - количество вершин

11.

Задача 1
В некотором районе было решено провести газопровод
между пятью деревнями. От Кошкино до Мышкино идти
10 км, от Мышкино до Ступино – 3 км, от Кошкино до
Малаховки – 6 км, от Малаховки до Черняевки – 12 км, от
Кошкино до Ступино – 11 км, от Мышкино до Чернеевки –
5 км, от Кошкино до Чернеевки – 7 км. Как необходимо
провести трубу, чтобы она соединяла все пять деревень, и
затраты при этом были минимальными?

12.

Задача 1
Построим граф, моделирующий дороги, соединяющие
деревни.
Малаховка
Чернеевка
10
Мышкино
Ступино
Кошкино

13.

Задача 1
Задача сводится к
минимального веса.
построению
остовного
связного
Рассчитаем цикломатическое число.
m (количество ребер) равно 7
n (количество вершин) рано 5
γ=7–5+1=3
Т.е.
три
деревни
напрямую
соединены газовой трубой не будут.
дерева

14.

Алгоритм Прима
Пусть дан взвешенный неориентированный граф.
Для построения минимального остовного
необходимо:
дерева
1. Представить граф в виде матрицы смежности
2. Найти в матрице наименьший элемент, соответствующий ребру, соединяющему i-ю и j-ю вершины графа
3. Вычеркнуть элементы i-й и j-й строки матрицы
4. Пометить i-й и j-й столбцы матрицы
5. В помеченных столбцах i и j найти
наименьший элемент, отличный от уже
найденного
6. Повторять пункты 3-5 до тех пор, пока не
будут задействованы все вершины графа
(переходы по щелчку)

15.

Задача 1
Решим задачу по алгоритму Прима.
Переопределим вершины графа.
4
Малаховка
5
Чернеевка
10
Мышкино
2
Кошкино
1
Ступино
3
(переходы по щелчку)

16.

Задача 1
Представим граф в виде матрицы смежности.
5
1
2
2
3
4
5
1
0
10
11
6
7
4
2
3
4
5
10
6
0
11
3
0
7
5
103
0
0
0
0
0
0
5
0
12
1
12
0
Найдем 3
минимальный элемент.
Он равен 3
(переходы по щелчку)

17.

Задача 1
Вычеркнем 2-ю и 3-ю строки таблицы. А столбцы 2 и 3
выделим.
1
2
3
4
5
1
0
10
6
2
10
11
6
7
0
11
3
0
7
5
3
0
0
0
0
0
0
12
55
0
12
0
3
4
5
Найдем минимальный
выделенных столбцах.
элемент
в
Он равен 5
(переходы по щелчку)

18.

Задача 1
Вычеркнем 5-ю строку таблицы. А столбец 5 выделим.
1
1
2
3
4
5
0
10
11
3
6
7
6
7
0
0
0
12
55
0
12
0
2
3
4
5
Найдем минимальный элемент в
выделенных столбцах.
Он равен 7
(переходы по щелчку)

19.

Задача 1
Вычеркнем 1-ю строку таблицы. А столбец 1 выделим.
1
1
2
3
4
5
0
10
11
3
6
7
6
6
0
0
0
12
2
3
4
5
5
Найдем минимальный элемент в
выделенных столбцах.
Он равен 6
(переходы по щелчку)

20.

Задача 1
Вычеркнем 4-ю строку таблицы. А столбец 4 выделим.
1
2
3
4
1
5
7
2
3
3
4
5
6
0
0
0
12
5
(переходы по щелчку)

21.

Задача 1
Получаем связное остовное дерево минимальное веса.
51
1
2
45
3
3
4
4
7
2
1
3
10
6
5
2
5
3
(переходы по щелчку)

22.

Задача 1
Ответ: газопровод с минимальными
необходимо прокладывать так:
5
Чернеевка
Мышкино
1
затратами
4
Малаховка
Кошкино
2
Ступино
3
Протяженность газопровода – 21 км.

23.

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

24.

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

25.

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

26.

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

27.

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

28.

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

29.

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

30.

Пример:

31.

Пример:

32.

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

33.

Пример:
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

34.

Пример:

35.

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