Графы и их применение. Создание маршрута по историческим местам города Новосибирска. Квест-экскурсия.

Графы и их применение. Создание маршрута по историческим местам города Новосибирска. Квест-экскурсия.

Учитель Щукина А.г.

г. Новосибирск

2022 - 2023

Введение . Актуальность проекта .

Гипотеза исследования

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

Цель:

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

Задачи исследования:

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

Теория графов

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

(15 апреля 1707 г. – 18 сентября 1783 г.)

Основные понятия теории графов

Вершины графа

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

Рёбра графа

3

5

182

3

158

127

3

Владимир, 1108

Москва, 1147

Переславль Залесский, 1152

дуга

ребро

Взвешенный граф

В

петля

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

А

С

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

Орентированый граф

Гамильтонов граф — граф, содержащий гамильтонов путь. Гамильтоновым путём является путь, который проходит через каждую вершину графа ровно по одному разу; то есть простой цикл, в который входят все вершины графа

Задачи на вычерчивание фигур одним росчерком.

4 основных правила для решения этих задач

Алгоритм решения таких задач

5

4

4

3

Задача. Деревья на даче.

У нас на дачном участке растут 15 деревьев

Берёза выше дуба, груша2 ниже груши1, слива выше ели, но ниже яблони(мол), кедр выше пихты, дуб выше рябины, вишня выше яблони, яблоня(мол) ниже яблони, берёзка ниже рябины, но выше груши1, пихта выше ореха, ранетка выше вишни, но ниже груши2, ель выше кедра, ранетка выше вишни, но ниже груши2.

• Берёза
• Дуб
• Рябина
• Берёзка
• Груша 1
• Груша 2
• Ранетка
• Вишня
• Яблоня(старая)
• Яблоня (молоденькая)
• Слива
• Ель
• Кедр
• Пихта
• Орех

Расположите деревья от самого низкого к самому высокому.

Созвездия на небе

Чтобы выделить отдельные  созвездия  из общего «звездного хаоса», первые астрономы условно соединили наиболее яркие звёзды линиями (построили графы).

Социометрия

Социометрия  — теория измерения межличностных отношений

Если ты не понял новую тему, кого бы ты попросил бы объяснить тебе эту тему еще раз?

Тебе предстоит собрать команду из трех одноклассников, чтобы выступить в спортивных соревнованиях «Веселые старты». Кого ты бы взял в команду?

Построение маршрута по интересным местам Новосибирска

С помощью сайта

https://graphonline.ru/ построила Гамельтонов путь

Граф содержит Гамильтонов путь: 1⇒2⇒3⇒4⇒5⇒6⇒7⇒8⇒9⇒10⇒11⇒12⇒13

55,8 км

Заключение

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

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

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

Заключение

Логистика

Социометрия

Электронные сети

Химические малекулы

Схема городского транспорта

Гипотеза исследования

Гипотеза исследования

Задачи поставленные мной выполнены в полном объёме. Гипотеза нашла своё подтверждение.

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

Перспективы проекта:

Прототип

Экскурсионный беспилотный автомобиль

Источники информации

• https:// urok.1sept.ru/articles/690580 История возникновения теории графов.  Леонард Эйлер и задача о Кёнигсберских мостах.
• https:// www.sites.google.com/a/labore.ru/teoria-grafov/vvedenie-v-teoriu/1 теория графов
• https:// gigabaza.ru/doc/84940-pall.html Социометрический метод исследования малой группы.

программы

• Работа с графами онлайн. Визуализация графа, поиск кратчайшего пути и многое другое. https://graphonline.ru/

https://graphonline.ru/? graph=wKIjdJDSZMxqfglgZZcst граф достопримечательностей

https://graphonline.ru/? graph=dfNxFvPbKPVRhQOWZZcst граф помощи

https://graphonline.ru/? graph=SkXuLZmzzZBdlsCSZZcst граф спорта

• Яндекс Карта Новосибирск
• Яндекс Картинки
• Microsoft Office (powerpoint, word)