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

Нажмите для полного просмотра!

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

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

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

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

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

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

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

Содержание ▲

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

Слайды и текст этой презентации

Слайд 1

Описание слайда:

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

Слайд 2

Описание слайда:

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

Слайд 3

Описание слайда:

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

Слайд 4

Описание слайда:

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

Слайд 5

Описание слайда:

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

Слайд 6

Описание слайда:

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