Презентация "Построение остовного (покрывающего) дерева графа" (11 класс) по информатике – проект, доклад

Построение остовного (покрывающего) дерева графа

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

Основные определения

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

Алгоритмы построения

метод Крускала метод Прима γ=n-m+1 Куленчик О.Н.

Метод Крускала

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

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

Подсчитаем цикломатическое число γ=n-m+1

Проверка сошлась, надо было удалить 5 ребер и мы их удалили

γ=10-6+1=5

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

1 4 2 3 6

Метод Прима

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

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

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

Заполним таблицу весами ребер, которые соединяют рассматриваемые вершины.

Метод построения:

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