Разделы презентаций
- Разное
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Построение остовного (покрывающего) дерева графа
Содержание
- 1. Построение остовного (покрывающего) дерева графа
- 2. Основные определенияОстовное дерево – это подграф, не
- 3. Метод КрускалаРебра исходного графа записываются в порядке
- 4. Пример. Пусть дан граф (взвешенный, неориентированный). Необходимо
- 5. Ответ: полученное остовное дерево142356Куленчик О.Н.
- 6. Метод ПримаВ этом методе первоначально выбирается любая
- 7. Пусть дан граф (взвешенный, неориентированный). Необходимо построить
- 8. Ответ: полученное остовное деревоМетод построения:Берем последний min
- 9. Скачать презентанцию
Основные определенияОстовное дерево – это подграф, не содержащий циклов, включающий все вершины исходного графа, а сумма длин ребер которого минимальна.Цикломатическое число – показывает сколько ребер надо удалить, чтобы в нем не
Слайды и текст этой презентации
Слайд 2Основные определения
Остовное дерево – это подграф, не содержащий циклов, включающий
все вершины исходного графа, а сумма длин ребер которого минимальна.
Цикломатическое
число – показывает сколько ребер надо удалить, чтобы в нем не осталось ни одного цикла.Алгоритмы построения
метод Крускала
метод Прима
γ=n-m+1
Куленчик О.Н.
Слайд 3Метод Крускала
Ребра исходного графа записываются в порядке возрастания их весов,
каждая вершина графа помещается в одноэлементное подмножество. Просматривая ребра исходного
графа, делается вывод о включении, либо исключении ребра из остовного дерева. При этом, если ребро связывает вершины, принадлежащие разным подмножествам, то оно включается в остовное дерево, в противном случае ребро удаляется из рассмотрения.Куленчик О.Н.
Слайд 4Пример. Пусть дан граф (взвешенный, неориентированный). Необходимо построить остовное дерево
методом Крускала.
Подсчитаем
цикломатическое
число
γ=n-m+1
Проверка сошлась, надо было удалить 5 ребер
и мы их удалилиγ=10-6+1=5
Куленчик О.Н.
Слайд 6Метод Прима
В этом методе первоначально выбирается любая вершина для начального
рассмотрения ее по отношению к другим вершинам. После чего, выбирается
минимальный вес (с вершиной). Вершину с минимальным весом удаляем из дальнейшего рассмотрения и сносим ее на следующий уровень. Дальше мы начинаем рассматривать снесенную вершину относительно других, оставшихся вершин.Куленчик О.Н.
Слайд 7Пусть дан граф (взвешенный, неориентированный). Необходимо построить остовное дерево методом
Прима.
На первом шаге минимальный
вес был 1 и принадлежал
он вершине V2, поэтому мы ее выбираем и удаляем из дальнейшего рассмотрения.
На втором шаге мы рассматриваем вершину V2, т.к. ее
мы удалили, относительно оставшихся вершин. Причем
на втором шаге не только проставляем веса ребер, но и
сравниваем их с предыдущим уровнем. Если на
предыдущем уровне вес был меньше, то сносим min вес.
Заполним таблицу
весами ребер,
которые соединяют
рассматриваемые
вершины.
Куленчик О.Н.
Слайд 8Ответ: полученное остовное дерево
Метод построения:
Берем последний min вес, он равен
4 и относится к
вершине V6 что вершину V6 надо
соединить в V3,т.к. первый раз 4, в этом столбце, появилось напротив вершины V3. Все оставшиеся вершины соединяются по
этому же принципу.
Куленчик О.Н.
