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

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

2 Основные определения Остовное дерево – это подграф, не содержащий циклов, включающий все вершины исходного графа, а сумма длин ребер которого минимальна. Цикломатическое число – показывает сколько ребер надо удалить, чтобы в нем не осталось ни одного цикла. Алгоритмы построения метод Крускаламетод Прима γ=n-m+1 Куленчик О.Н.

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

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

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

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

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

8 Ответ: полученное остовное дерево V2V3V4V5V6 V V2125- V3234 V434 V54 Метод построения: Берем последний min вес, он равен 4 и относится к вершине V6 что вершину V6 надо соединить в V3, т.к. первый раз 4, в этом столбце, появилось напротив вершины V3. Все оставшиеся вершины соединяются по этому же принципу. Куленчик О.Н.