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

Презентация:



Advertisements
Похожие презентации
Введение в теорию графов. ЗАДАЧА ПРОКЛАДКИ КОММУНИКАЦИЙ
Advertisements

Теория графов. Теория графов – обширный самостоятельный раздел дискретной математики. Используется при проектировании компьютерных сетей, трубопроводов,
Построение остовного (покрывающего) дерева графа Преподаватель «И и ИКТ» ГБОУ лицея 1557 Куленчик Олеся Николаевна.
Алгоритмы Прима и Крускала построения остовного связного дерева минимального веса Гуляева Татьяна Викторовна учитель информатики и математики МБОУ СОШ.
Теория графов. Теория графов – обширный самостоятельный раздел дискретной математики. Используется при проектировании компьютерных сетей, трубопроводов,
Графы Кенигсбергские мосты К XVIII веку через реку, на которой стоял город Кенигсберг (ныне Калининград), было построено 7 мостов, которые связывали.
Графы Введение в теорию графов Решение задач Алгоритм Крускала.
Введение в теорию графов 11 класс Профиль Учитель информатики Тивякова Л.А., к учебнику Н.Д.Угриновича.
ТЕОРИЯ ГРАФОВ ЗАДАЧА КОММИВОЯЖЕРА Гамильтоновы графы применяются для моделирования многих практических задач. Основой всех таких задач служит классиче.
Остовные деревья Лекция 4. Задача «Минимальное остовное дерево» Дано: Граф G, веса c: E(G) R. Найти остовное дерево в G наименьшего веса или определить,
Презентация по Информатике Тема: «Графы» Выполнил: Бычков Георгий.
Графы Лекция 2. Графы Неориентированным графом (графом) называется тройка (V, E, ), где V и E конечные множества и {X V : | X | = 2}. Ориентированным.
Построение минимального остовного дерева. Алгоритм Краскала Подготовила ученица 10-А класса ЭМЛ Огурцова Валерия.
Теория графов Основные определения. Задание графов Графический способ – Привести пример графического задания графа, состоящего из вершин А, В и С, связанных.
Матроиды Лекция 12. Введение Даны система множеств (E, F ), то есть конечное множество E, F 2 E и стоимостная функция c : F R, найти элемент из F, стоимость.
Сетевое планирование. Теория графов. Граф Граф это совокупность непустого множества вершин и множества пар вершин. Граф это совокупность непустого множества.
Эйлеровы графы. Гамильтоновы графы G.
Автоматизированное построение математических моделей систем по эквивалентным схемам Вышегородцев М. Е. Научный руководитель, д. т. н., профессор : Устюгов.
Информационные модели на графах Болгова Н.А.- Учитель информатики МБОУ СОШ с УИОП с.Тербуны.
Графы Степень вершины Подсчет числа ребер графа. Разминка… Вставьте недостающие слова в предложения (граф, титул, ребро, вершина) Всем известно, что слово.
Транксрипт:

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

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

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

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

Введем цикломатическое число γ - показывает, сколько ребер графа надо удалить, чтобы в нем не было циклов: γ = R-V+1 Для нашего случая получаем цикломатическое число γ = = 4 Задание: постройте остовные связные деревья графа G и просчитайте вес каждого графа Например, получили следующие деревья с весом 135, 130, 100, 135 соответственно.