НПК "Шаг в будущее" "Графы".

МБОУ «Онохойская средняя школа №1»

Практическое применение графов

Выполнил: Мамедова Наталья

ученица 10 класса

Руководитель:

Буркова И.П. учитель математики

пос. Онохой

2018

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

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

  Цель : познакомится с теорией графов, показать ее практическую направленность и применение в жизни, научиться решать задачи с помощью графов.

Задачи :

1.Познакомиться с историей возникновения графов.

2.Изучить различные виды графов и их элементы.

3.Рассмотреть примеры применения графов в современном мире.

4.Показать графы на картах Заиграевского района

5.Рассмотреть Эйлеров цикл на примере мостов г.Улан-Удэ

Методы исследования :

• аналитический (изучение и использование научно-публицистических и учебных изданий, метод сопоставления);
• практический

Методы исследования:

аналитический – анализ литературных и научных источников и материалов;

практический – на основе собственных исследований.

Объект исследования: теория графов и ее приложение.

Предмет исследования: задачи с использованием графов при решении, карты.

Что такое граф

Графом называется конечное множество точек, некоторые из которых соединены линиями. Точки называются вершинами графа, а соединяющие линии – рёбрами .

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

Чётная степень

: Ст.А = 1, Ст.Б = 2, Ст.В = 3, Ст.Г= 2, Ст.Д= 0.

Нечётная степень

Виды графов и их элементы .

Нулевой граф

Полные графы.

Неполный граф

Задача 5. (ЕГЭ)

Велосипедист собирается проехать из пункта A в пункт E, в который ведут 3 маршрута: через B, через C, через D. Расстояния в километрах показаны на схеме. Известно, что если ехать через B, то средняя скорость будет равна 16 км/ч, если ехать через D, то средняя скорость будет равна 18 км/ч, а если ехать через C, то средняя скорость будет равна 20 км/ч. Исходя из этих данных, велосипедист выбрал маршрут так, чтобы доехать до E за наименьшее время.

Сколько минут он планирует пробыть в пути?

Решение :

• (15 + 25) : 16 = 2часа 30мин – время в пути ABE
• (19 + 17) : 18 = 2 часа – время в пути ADE
• (11 + 34) : 20 = 2часа 15мин – время в пути AСE
• 2ч
• 2 (ч) = 120 (мин)

Граф, в котором две любые вершины соединены ровно одним простым путём, является деревом

Задача №968 (учебник И.И.Зубарева, А.Г.Мордкович 5 класс)

Сколько двузначных чисел можно составить из цифр 0,2,4,6,8

(рубрика «Развития внимательности и сообразительности»

Графы вокруг нас.

Лабиринт - это граф. А исследовать его - это найти путь в этом графе.

Графы вокруг нас.

На рисунке приведена часть генеалогического дерева знаменитого дворянского рода Л. Н. Толстого. Здесь его вершины – члены этого рода, а связывающие их отрезки – отношения родственности, ведущие от родителей к детям.

Графы и биология

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

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

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

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

Жители города предлагали приезжим следующую задачу: пройти по всем мостам и вернуться в начальный пункт, причём на каждом мосту следовало побывать только один раз.

Мосты Заиграевского района

Графы на картах Заиграевского района

Задача о Кёнигсбергских мостах и она же, но в Улан-Удэ

Заключение

Я выполнила свою основную цель – проверила и доказала соответствие мостов нашего города Эйлерову

циклу. Показала граф на карте Заиграевского района. Построила Эйлеров граф по мостам города Улан-Удэ.

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

Некоторые задачи школьного курса

Аркадий, Борис. Владимир, Григорий и Дмитрий при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу). Сколько всего рукопожатий было сделано?

Эйлеров цикл

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

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

Алгоритм

Алгоритм составления графов для систематизации материала.

• Утвердить основные пункты – будущие вершины графа (темы, которые могли бы быть вынесены в конспект как основные мысли, или как главные пункты в развёрнутом плане)
• Утвердить промежуточные точки – по ним будут построены рёбра (тезисные утверждения конспекта или подпункты развёрнутого плана)
• Установить чёткую взаимосвязь и отношения между утверждениями- вершинами.
• Рассмотреть принадлежность промежуточных пунктов к отношениям между основными вершинами.
• Поместить вершины относительно их взаимосвязей
• Связать их рёбрами, опираясь на промежуточные точки, пометить указанные точки на рёбрах.
• Добавить необходимые направления в полученный граф – сделать его направленным.

Граф для систематизации материала по теме «Дроби»