Разделы презентаций


Презентация на тему Деревья. Алгоритм Краскала

Презентация на тему Презентация на тему Деревья. Алгоритм Краскала из раздела Разное. Доклад-презентацию можно скачать по ссылке внизу страницы. Эта презентация для класса содержит 23 слайдов. Для просмотра воспользуйтесь удобным проигрывателем, если материал оказался полезным для Вас - поделитесь им с друзьями с помощью социальных кнопок и добавьте наш сайт презентаций TheSlide.ru в закладки!

Слайды и текст этой презентации

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

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

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 ) связан и не содержит циклов;
граф 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 ребро, поэтому оно будет минимальным связным графом.
Текст слайда:

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


Слайд 7
Лес – это граф, компоненты которого являются деревьями.Узел без поддеревьев называется листом и является висячей вершиной.
Текст слайда:

Лес – это граф, компоненты которого являются деревьями.

Узел без поддеревьев называется листом и является висячей вершиной.

Дерево, в котором каждый узел либо является листом, либо образует два поддерева (левое и правое), называется бинарным


Слайд 8
Бинарное дерево называется деревом поиска, если его элементы расположены так, что для каждого элемента n все элементы
Текст слайда:

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

20, 10, 35, 15, 17, 27, 24, 8, 30

20

10

35

8

15

27

30

24

17


Слайд 9
Пирамида - это такое двоичное дерево, для которого выполнены три условия: - Значение в любой вершине больше,
Текст слайда:

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

16, 11, 9, 10, 5, 6, 8, 1, 2, 4

16

11

9

10

5

6

8

4

1

2


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

СЕТИ. СЕТЕВЫЕ МОДЕЛИ ПРЕДСТАВЛЕНИЯ ИНФОРМАЦИИ

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

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


Слайд 11
АЛГОРИТМ КРАСКАЛА Имеется n сельских домов, которые нужно объединить в единую компьютерную сеть. Для этого достаточно проложить
Текст слайда:

АЛГОРИТМ КРАСКАЛА

Имеется n сельских домов, которые нужно объединить в единую компьютерную сеть. Для этого достаточно проложить (n-1) линий между домами. Как соединить дома так, чтобы суммарная стоимость соединений (кабеля) была минимальна?

Остов графа (стягивающее дерево, spanning tree) – дерево, полученное из графа, выбрасыванием части ребер.


Слайд 12
ПОСТАНОВКА ЗАДАЧИДан связный неориентированный граф G(V;E), и каждой его дуге е сопоставлено некоторое число, называемое весом или
Текст слайда:

ПОСТАНОВКА ЗАДАЧИ

Дан связный неориентированный граф G(V;E), и каждой его дуге е сопоставлено некоторое число, называемое весом или длиной этой дуги. Сумму весов дуг дерева в дальнейшем будем называть весом дерева или его множества дуг. Требуется найти такое остовное дерево Т, содержащего все вершины графа G, у которого вес был бы минимален. Такое дерево будет называться минимальным остовным деревом.

Суммарный вес равен
4 + 7 + 5 + 10 + 11 = 37


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

ОПИСАНИЕ АЛГОРИТМА

1. Вначале текущее множество рѐбер устанавливается пустым.
2. Затем, пока это возможно, проводится следующая операция:
из всех рѐбер, добавление которых к уже имеющемуся множеству не вызовет появление в нѐм цикла, выбирается ребро минимального веса и добавляется к уже имеющемуся множеству.

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


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

начало

выбор первого ребра с минимальным весом

выбор следующего ребра с минимальным весом

ребро создаст цикл?

добавить ребро в остовное дерево

еще есть ребра?

нет

да

да


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

ПРИМЕР

Ребра AD и CE имеют минимальный вес, равный 5. Произвольно выбирается ребро AD

Теперь наименьший вес, равный 5, имеет ребро CE. Так как добавление CE не образует цикла, то выбираем его в качестве второго ребра


Слайд 16
ПРИМЕРАналогично выбираем ребро DF, вес которого равен 6Следующие ребра — AB и BE с весом 7. Произвольно
Текст слайда:

ПРИМЕР

Аналогично выбираем ребро DF, вес которого равен 6

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


Слайд 17
ПРИМЕРАналогичным образом выбирается ребро BE, вес которого равен 7. ВЫБИРАТЬ ЗАПРЕЩЕНО:(выделено красным)BC - создаст цикл BCE, DE
Текст слайда:

ПРИМЕР

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

Алгоритм завершается добавлением ребра EG с весом 9. Минимальное остовное дерево построено.


Слайд 18
Пример:
Текст слайда:

Пример:


Слайд 19
Пример:
Текст слайда:

Пример:


Слайд 20
178264351328611458Пример:
Текст слайда:

1

7

8

2

6

4

3

5

1

3

2

8

6

1

1

4

5

8

Пример:


Слайд 21
178264351328611458178264351328611458178264351328611458Пример:
Текст слайда:

1

7

8

2

6

4

3

5

1

3

2

8

6

1

1

4

5

8

1

7

8

2

6

4

3

5

1

3

2

8

6

1

1

4

5

8

1

7

8

2

6

4

3

5

1

3

2

8

6

1

1

4

5

8

Пример:


Слайд 22
Пример:
Текст слайда:

Пример:


Слайд 23
Контрольные вопросы:1. Что называется деревом в графе? 2. Опишите свойства деревьев. 4. Что называется бинарным деревом? 5.
Текст слайда:

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

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


Обратная связь

Если не удалось найти и скачать доклад-презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:

Email: Нажмите что бы посмотреть 

Что такое TheSlide.ru?

Это сайт презентации, докладов, проектов в PowerPoint. Здесь удобно  хранить и делиться своими презентациями с другими пользователями.


Для правообладателей

Яндекс.Метрика