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

Август 26, 2022

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

Содержание

2. Основные определения Остовное дерево – это подграф, не содержащий циклов, включающий все вершины исходного графа, а
3. Метод Крускала Ребра исходного графа записываются в порядке возрастания их весов, каждая вершина графа помещается в
4. Пример. Пусть дан граф (взвешенный, неориентированный). Необходимо построить остовное дерево методом Крускала. Подсчитаем цикломатическое число γ=n-m+1
5. Ответ: полученное остовное дерево 1 4 2 3 5 6 Куленчик О.Н.
6. Метод Прима В этом методе первоначально выбирается любая вершина для начального рассмотрения ее по отношению к
7. Пусть дан граф (взвешенный, неориентированный). Необходимо построить остовное дерево методом Прима. На первом шаге минимальный вес
9. Скачать презентацию

Слайд 2

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

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

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

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

метод Прима

γ=n-m+1

Куленчик О.Н.

Слайд 3

Метод Крускала
Ребра исходного графа записываются в порядке возрастания их весов, каждая

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

Куленчик О.Н.

Слайд 4

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

Крускала.

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

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

γ=10-6+1=5

Куленчик О.Н.

Слайд 5

Ответ: полученное остовное дерево
1
4
2
3
5
6
Куленчик О.Н.

Слайд 6

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

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

Куленчик О.Н.

Слайд 7

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

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

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

Куленчик О.Н.

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

Содержание

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

Метод КрускалаРебра исходного графа записываются в порядке возрастания их весов, каждая

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

Ответ: полученное остовное дерево142356Куленчик О.Н.

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

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

Похожие презентации

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

Метод Крускала
Ребра исходного графа записываются в порядке возрастания их весов, каждая

Ответ: полученное остовное дерево
1
4
2
3
5
6
Куленчик О.Н.

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