Презентация "Графы и деревья""

МБОУ «Пекшинская СОШ»

Графы и деревья

Автор:

Васин Д.Ю.,

учитель информатики и ИКТ

Графы и деревья

Модели, которые мы выбираем…

Модель:

объект, который отражает существенные признаки изучаемого объекта, процесса или явления.

предметные

информационные

Образные модели

Знаковые модели

Визуализация

различные формы

анимация

Формализация

формальные языки

необходимость моделей и пути построения

Схема метро

Схема железнодорожных станций

• Изображение железных дорог на географических картах;
• Схемы авиалиний
• Схемы метро
• Иерархия объектов (например структура школы)
• Файлы системы компьютера

Цель: разработать и реализовать справочную информационную систему по теории графов

Задачи:

1) Изучить и проанализировать теорию графов и деревьев;

2) исследовать применение теории графов в школе;

История графов

Леонард Эйлер

(1707-1783)

V-R+G=2

- Формула Эйлера

V – число вершин

R – число рёбер

G – число граней

Задача о Кенигсбергских мостах

Есть такой город Калининград, раньше он назывался Кенигсберг. Через город протекает река Преголя, она делится на два рукава и огибает остров. В 18 веке в городе было семь мостов, расположенных так, как показано на рисунке сверху. Рассказывают, что однажды житель города спросил у своего знакомого, сможет ли он пройти по всем мостам так, чтобы на каждом из них побывать только один раз и вернуться к тому месту, откуда началась прогулка? Многие горожане заинтересовались этой задачей. Однако, придумать решение никто не смог. Потом этот вопрос привлек внимание ученых разных стран. Разрешить проблему удалось знаменитому математику Леонарду Эйлеру. Причем, он решил не только эту конкретную задачу, но придумал общий метод решения подобных задач.

Решая задачу про Кенигсбергские мосты, Эйлер установил, в частности, следующие три СВОЙСТВА графа:

1) Если все вершины графа четные, то можно одним росчерком (то есть рисуя непрерывно и не проводя дважды по одной и той же линии) начертить граф

2) Граф с двумя нечетными вершинами тоже можно начертить одним росчерком. Движение нужно начинать от любой нечетной вершины, а заканчивать на другой нечетной вершине. Проверьте это свойство на практике.

3) Граф с более, чем двумя нечетными вершинами, невозможно начертить одним росчерком.

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

Задача Коммивояжёра

Задача Коммивояжёра — важная задача транспортной логистики, отрасли, занимающейся планированием транспортных перевозок. Коммивояжёру, чтобы распродать нужные и не очень нужные в хозяйстве товары, следует объехать n пунктов и в конце концов вернуться в исходный

пункт. Требуется определить наиболее выгодный маршрут объезда. В качестве меры выгодности маршрута (точнее говоря, невыгодности) может служить суммарное время в пути, суммарная стоимость дороги, или, в простейшем случае, длина маршрута.

Оптимальный маршрут коммивояжёра через 15 крупнейших городов Германии. Указанный маршрут является самым коротким из всех возможных

Двоичное дерево

Родовое генеалогическое дерево

В городе проводилось совещание врачей. От каждой поликлиники были приглашены 4 врача. Каждый из приглашенных работал в 2 поликлиниках и представлял на этом совещании обе поликлиники. Любая возможная комбинация двух поликлиник имело на этом совещании одного и только одного представителя. Сколько поликлиник в городе? Сколько врачей было приглашено на совещание?

Применение графов для решения логических задач

Ответ: 5 поликлиник;

10 врачей.

Выводы:

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

Спасибо за внимание!