Презентация на тему Теория графов:подграфы и деревья

Презентация на тему Презентация на тему Теория графов:подграфы и деревья, предмет презентации: Разное. Этот материал содержит 5 слайдов. Красочные слайды и илюстрации помогут Вам заинтересовать свою аудиторию. Для просмотра воспользуйтесь проигрывателем, если материал оказался полезным для Вас - поделитесь им с друзьями с помощью социальных кнопок и добавьте наш сайт презентаций ThePresentation.ru в закладки!

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

Слайд 1
Текст слайда:

Теория графов: подграфы и деревья

11 класс
Профиль
Учитель информатики Тивякова Л.А., к учебнику автора Угриновича Н.Д.


Слайд 2
Текст слайда:

Подграфы и деревья

Подграф графа G - граф, у которого все вершины и ребра принадлежат графу G.

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


Слайд 3
Текст слайда:

Подграфы и деревья

Дерево - это граф, в котором нет циклов (нельзя из некоторой вершины пройти по нескольким различным ребрам и вернуться в ту же вершину.

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


Слайд 4
Текст слайда:

Преобразование графа в остовное связное дерево минимального веса

Дан граф G – связный, взвешенный неориентированный граф (Rnm=Rmn).
Тогда получаем матрицу из весов 10 ребер


Слайд 5
Текст слайда:

Введем цикломатическое число γ - показывает, сколько ребер графа надо удалить, чтобы в нем не было циклов:
γ = R-V+1

Для нашего случая получаем цикломатическое число γ = 8-5+1 = 4

Задание: постройте остовные связные деревья графа G и просчитайте вес каждого графа

Например, получили следующие деревья с весом 135, 130, 100, 135 соответственно.


Обратная связь

Если не удалось найти и скачать презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:

Email: Нажмите что бы посмотреть 

Что такое ThePresentation.ru?

Это сайт презентаций, докладов, проектов, шаблонов в формате PowerPoint. Мы помогаем школьникам, студентам, учителям, преподавателям хранить и обмениваться учебными материалами с другими пользователями.


Для правообладателей

Яндекс.Метрика