PPt4Web Хостинг презентаций

Главная / Информатика / Построение остовного (покрывающего) дерева графа
X Код для использования на сайте:

Скопируйте этот код и вставьте его на свой сайт

X

Чтобы скачать данную презентацию, порекомендуйте, пожалуйста, её своим друзьям в любой соц. сети.

После чего скачивание начнётся автоматически!

Кнопки:

Презентация на тему: Построение остовного (покрывающего) дерева графа


Скачать эту презентацию

Презентация на тему: Построение остовного (покрывающего) дерева графа


Скачать эту презентацию

№ слайда 1 Построение остовного (покрывающего) дерева графа Преподаватель «И и ИКТ» ГБОУ ли
Описание слайда:

Построение остовного (покрывающего) дерева графа Преподаватель «И и ИКТ» ГБОУ лицея №1557 Куленчик Олеся Николаевна

№ слайда 2 Основные определения Остовное дерево – это подграф, не содержащий циклов, включа
Описание слайда:

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

№ слайда 3 Метод Крускала Ребра исходного графа записываются в порядке возрастания их весов
Описание слайда:

Метод Крускала Ребра исходного графа записываются в порядке возрастания их весов, каждая вершина графа помещается в одноэлементное подмножество. Просматривая ребра исходного графа, делается вывод о включении, либо исключении ребра из остовного дерева. При этом, если ребро связывает вершины, принадлежащие разным подмножествам, то оно включается в остовное дерево, в противном случае ребро удаляется из рассмотрения.

№ слайда 4 Пример. Пусть дан граф (взвешенный, неориентированный). Необходимо построить ост
Описание слайда:

Пример. Пусть дан граф (взвешенный, неориентированный). Необходимо построить остовное дерево методом Крускала. Подсчитаем цикломатическое числоγ=n-m+1 γ=10-6+1=5 Проверка сошлась, надо было удалить 5 ребер и мы их удалили

№ слайда 5 Ответ: полученное остовное дерево
Описание слайда:

Ответ: полученное остовное дерево

№ слайда 6 Метод Прима В этом методе первоначально выбирается любая вершина для начального
Описание слайда:

Метод Прима В этом методе первоначально выбирается любая вершина для начального рассмотрения ее по отношению к другим вершинам. После чего, выбирается минимальный вес (с вершиной). Вершину с минимальным весом удаляем из дальнейшего рассмотрения и сносим ее на следующий уровень. Дальше мы начинаем рассматривать снесенную вершину относительно других, оставшихся вершин.

№ слайда 7 Пусть дан граф (взвешенный, неориентированный). Необходимо построить остовное де
Описание слайда:

Пусть дан граф (взвешенный, неориентированный). Необходимо построить остовное дерево методом Прима. Заполним таблицувесами ребер, которые соединяютрассматриваемые вершины. На первом шаге минимальныйвес был 1 и принадлежал он вершине V2, поэтому мы ее выбираем и удаляем из дальнейшего рассмотрения. На втором шаге мы рассматриваем вершину V2, т.к. ее мы удалили, относительно оставшихся вершин. Причем на втором шаге не только проставляем веса ребер, но и сравниваем их с предыдущим уровнем. Если на предыдущем уровне вес был меньше, то сносим min вес.

№ слайда 8 Ответ: полученное остовное дерево Метод построения: Берем последний min вес, он
Описание слайда:

Ответ: полученное остовное дерево Метод построения: Берем последний min вес, он равен 4 и относится квершине V6 что вершину V6 надо соединить в V3,т.к. первый раз 4, в этом столбце, появилось напротив вершины V3. Все оставшиеся вершины соединяются по этому же принципу.

Скачать эту презентацию

Презентации по предмету
Презентации из категории
Лучшее на fresher.ru