XXV Международный конкурс научно-исследовательских и творческих работ учащихся
Старт в науке
Составление экскурсионного маршрута по музеям боевой славы Куйбышевского района г.о. Самары с помощью теории графов
Автор работы награжден дипломом победителя I степени
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
ВВЕДЕНИЕ
Теория графов стала в настоящее время простым, доступным и мощным средством решения вопросов, относящихся к широкому кругу проблем. Графы буквально вездесущи. В виде графов можно, например, интерпретировать схемы дорог и электрические цепи, географические карты и молекулы химических соединений, связи между людьми и группами людей. За последние четыре десятилетия теория графов превратилась в один из наиболее бурно- развивающихся разделов математики. Это вызвано запросами стремительно расширяющейся области приложений.
Даннаяработапосвященасоставлению экскурсионного маршрута по музеям боевой славы г.о. Самары с помощью теории графов. Что особенно актуально в настоящее время, так как президент Российской Федерации В.В. Путин объявил 2025 год - Годом защитника Отечества и 80-летия Победы в Великой Отечественной войне 1941-1945 годов.
Актуальностьданнойработыопределяется тем, что посещение музеев боевой славы школьниками способствует:
- во-первых, патриотическому воспитанию. Музеи помогают формировать у учащихся гражданско-патриотические качества, прививать любовь к родине и уважение к истории;
- во-вторых, расширению кругозора. Материалы музея не только дают знания об истории, но и способствуют развитию интереса к учебной деятельности;
- в-третьих, развитию поисковых и исследовательских навыков. Ученики могут использовать материалы музея для написания рефератов, докладов, сообщений по учебным предметам.
- в-четвертых, сохранению памяти. Музеи позволяют сохранять память о защитниках Отечества, заниматься исследовательской деятельностью, создавать небольшие фильмы о ветеранах;
- в-пятых, подготовке к службе в армии. Знание основ военного дела помогает молодым людям быстрее адаптироваться к суровым условиям армейской службы.
С помощью теории графов возможно составление наиболее актуального маршрута по музеям боевой славы.
Цельюданногоисследованияявляется составление экскурсионного маршрута по музеям боевой славы г.о. Самары с помощью теории графов.
Даннаяцельпредполагаетрешениеследующихзадач:
1. Изучить и проанализироватьтеорию графов
2. Выявить области практического применения графов
3. Составить оптимальный маршрут посещения музеев боевой славы Куйбышевского района с помощью графов.
Объектомисследованиявданнойработеявляетсяпрактическое применение графов в различных областях.
Предметисследованияявляетсясоставление экскурсионного маршрута по музеям боевой славы с помощью теории графов.
Методы исследования: поиск источников информации, наблюдение, сравнение, анализ, математическое моделирование.
Теоретическаязначимостьисследованиязаключаетсявтом, что его результаты могут быть использованы на уроках при решении разных задач, а также в различных областях науки и в современной жизни.
Практическаязначимостьобусловленатем,чтосоставленный экскурсионного маршрута по музеям боевой славы Куйбышевского района г. Самара будет полезен школьникам и всем желающим при посещениях музеев.
По структуре данная работа состоит из введения, трех параграфов, заключения и библиографического списка.
1.ТЕОРИЯ ГРАФОВ
В ходе изучения литературы по теме исследования нами были изучены следующие ресурсы:
-
obuchonok.ru — проект «Понятие и области применения графов». В нём рассматривается история возникновения графов, их виды, методы графового анализа и области применения.
-
infourok.ru — проект «Графы и их применение». В нём изучается история графов, их свойства и разновидности, рассматриваются примеры задач, которые можно решить с помощью графов.
-
nsportal.ru — индивидуальный учебный проект по теме «Графы и их применение». В нём рассматриваются возможности применения графов и их свойств к решению математических задач разного типа, а также показывается практическое применение графов в других сферах жизни человека.
-
урок.рф — проект «Графы и области их применения». В нём говорится о том, что графы играют важную роль в информатике, математике, логистике, экономике и научных исследованиях.
-
multiurok.ru — информационный проект «Графы и их применение». В нём рассказывается о том, как познакомиться с понятием «граф», его основными элементами, научиться составлять и читать графы по словесному описанию отношений между предметами и существами, а также исследовать роль графов в жизни.
Рассмотрим основные понятия теории графов.
Леонард Эйлер считается основателем теории графов и первым ввёл понятие графа. Он применил идеи теории графов при решении задачи о кёнигсбергских мостах в 1736 году.
Граф - математический объект, который изображает отношения между сущностями.
Граф состоит из вершин (объектов) и рёбер (связей). Вершины обычно обозначаются буквами или числами, а ребра – линиями, которые соединяют вершины.
Виды графов: Ориентированные графы
Характеризуются направленностью ребер. В таких графах каждое ребро имеет начальную и конечную вершину. Ориентированные графы применяются в задачах, где имеется направленность или зависимость между объектами. Например, они могут использоваться для моделирования сетей передачи данных, дорожной сети или в задачах планирования и оптимизации.
Рисунок 1
Неориентированные графы
В неориентированных графах ребра не имеют направления. Они состоят из вершин и неориентированных ребер, которые соединяют вершины. Неориентированные графы широко применяются в задачах, связанных с моделированием связей и отношений между объектами. Например, они могут использоваться для моделирования социальных сетей, транспортных сетей или сетей взаимодействия компьютеров.
Взвешенные графы
Взвешенные графы содержат численные значения, называемые весами, для каждого ребра. Эти веса могут отражать различные характеристики или стоимости связей между вершинами. Взвешенные графы применяются в задачах оптимизации, планирования маршрутов, логистики, анализа данных и других областях, где важно учитывать вариации весов связей при принятии решений.
Рисунок 2
Графы с мультиребрами и петлями
Графы с мультиребрами содержат несколько ребер, соединяющих одну и ту же пару вершин. Такие графы используются в задачах, где возможны несколько типов связей между объектами. Графы с петлями содержат ребра, соединяющие вершины сами с собой. Они применяются в теории графов для исследования самоподобных связей или циклических процессов.
Рисунок 3
Ациклические графы
Ациклические графы не содержат циклов, то есть пути, по которым можно пройти и вернуться в исходную вершину. Такие графы применяются в задачах, где важно избежать повторений или циклических зависимостей. Ациклические графы используются в программировании, базах данных, логистике и других областях.
Рисунок 4
В зависимости от задачи и требований, можно выбрать соответствующий вид графа и использовать его для эффективного решения поставленных задач. Графы обладают большим потенциалом и могут быть применены в разных областях, где необходимо моделирование и анализ связей между объектами.
Свойстваграфов.
-
Если все вершины графа четные, то можно одним росчерком (т.е. не отрывая карандаша от бумаги и не проводя дважды по одной и той же линии) начертить граф. При этом движение можно начать с любой вершины и окончить в той же вершине.
Граф,который можно нарисовать, неотрывая карандаша от бумаги, называется эйлеровым. Такими графы названы в честь учёного Леонарда Эйлера.
Рисунок 5
-
Граф с двумя нечетными вершинами тоже можно начертить одним росчерком. Движениенужноначинатьотлюбойнечетнойвершины,азаканчиватьнадругой нечетной вершине.
-
Граф с более чем двумя нечетными вершинами невозможно начертить одним росчерком.
-
Числонечетныхвершинграфавсегдачетное.
-
Если в графе имеются нечетные вершины, то наименьшее число росчерков, которыми можно нарисовать граф будет равно половине числа нечетных вершин этого графа.
Граф, который можно нарисовать, не отрывая карандаша от бумаги, называется эйлеровым. Такими графы названы в честь учёного Леонарда Эйлера.
2. ОБЛАСТИ ПРАКТИЧЕСКОГО ПРИМЕНЕНИЯ ГРАФОВ
Графы и информация
Теория информации широко использует свойства двоичных деревьев.
Например, если нужно закодировать некоторое число сообщений в виде определенных последовательностей нулей и единиц различной длины. Код считается наилучшим, для заданной вероятности кодовых слов, если средняя длина слов наименьшая в сравнении другими распределениями вероятности. Для решения такой задачи Хаффман предложил алгоритм, в котором, код представляется деревом-графом в рамках теории поиска. Для каждой вершины предлагается вопрос, ответом на который может быть либо, «да», либо «нет» – что соответствует двум ребрам, выходящим из вершины. Построение такого дерева завершается после установления того, что требовалось. Это может применяться в интервьюировании нескольких человек, когда заранее неизвестен ответ на предыдущий вопрос, план интервью представляется в виде двоичного дерева.
В Google графы использовали для ранжирования веб-страниц. Чтобы самый полезный сайт поставить на первое место, придумали алгоритм PageRank.
Каждый сайт был узлом, а ссылки на другие сайты внутри — связями. За счёт этого сайт, который ссылался на более достоверные источники, оказывался выше. Например, если одна из страниц ссылалась на сайт правительства Соединённых Штатов, а другая — на жёлтую прессу, вторая уходила вниз в поисковой выдаче.
Графы и химия
Некоторые области использования:
-
Представление структурных формул молекул. В органической химии используют молекулярные графы, в которых атомы представлены вершинами, а ковалентные химические связи - рёбрами.
-
Описание внутри- и межмолекулярных взаимодействий. Молекулярные графы играют важную роль в этом процессе, способствуют упорядочиванию молекулярных свойств и механизмов химических реакций.
-
Прогнозирование химических реакций. С помощью химических графов можно предсказывать химические превращения, пояснять сущность и систематизировать некоторые основные понятия химии.
-
Расчёт физико-химических свойств веществ. Графы также применяются для изучения изомеров органических соединений и некоторых других характеристик.
Таким образом, теория графов позволяет упростить решение многих химических задач, так как представление молекул в виде молекулярного графа придаёт им наглядность и простоту.
Например, еще А. Кэли рассмотрел задачу о возможных структурах насыщенных (или предельных) углеводородов, молекулы которых задаются формулой: CnH2n+2
Все атомы углеводорода 4-хвалентны, все атомы водорода 1-валентны. Структурные формулы простейших углеводородов показаны на рисунке.
Каждую молекулу предельного углеводорода можно представить в виде дерева. При удалении всех атомов водорода, атомы углеводорода, которые остались, образуют дерево с вершинами, степень которых не выше четырех. Значит, количество возможных искомых структур (гомологов данного вещества) равняется числу деревьев, степени вершин которых, не больше 4. Это задача сводится к задаче о перечислении деревьев отдельного вида. Д. Пойа рассмотрел эту задачу и ее обобщения.
Графы и биология
Некоторые области применения:
-
моделирование и визуализация процессов в биологических системах;
-
анализ проблемы индивидуальной нормы;
-
моделирование и анализ популяций и сложных сообществ.
Один из примеров использования графов в биологии — классификация животного мира, где вершины графа представляют собой члены рода, а связывающие их отрезки - отношения.
Процесс размножения бактерий – это одна из разновидностей ветвящихся процессов, встречающихся в биологической теории. Пусть каждая бактерия по истечению определенного времени или погибает, или делится на две. Следовательно, для одной бактерии мы получим двоичное дерево размножения ее потомства. Вопрос задачи заключается в следующем, какое количество случаев содержит k потомков в n-м поколение одной бактерии? Данное соотношение в биологии носит название процесс Гальтона-Ватсона, которое обозначает необходимое количество нужных случаев.
Графы и физика
Теория графов применяется в физике для изучения различных процессов и систем.
-
В физике конденсированных сред с помощью графов можно количественно изучить трёхмерную структуру сложных атомных структур.
-
В статистической физике графы используются для представления локальных связей между взаимодействующими частями системы, а также динамики физического процесса в таких системах.
-
Теория графов играет важную роль в электрическом моделировании сетевых структур, где веса графов связаны с сопротивлением сегментов провода.
-
Метод графов также используется при решении задач по физике. Он позволяет лучше уяснить приём решения задачи, наглядно представить процесс анализа задачи, последовательность действий при её решении, помогает в создании математической модели решения задачи.
Например, сложная утомительная задача для любого радиолюбителя – создание печатных схем (пластина диэлектрика – изолирующего материала и вытравленные дорожки в виде металлических полосок). Пересечение дорожек происходит только в определенных точках (местах установления триодов, резисторов, диодов и пр.) по определенным правилам. В результате перед ученым стоит задача вычертить плоский граф, с вершинами в узлах и ребрами – в дорожках.
Итак, все выше сказанное подтверждает практическую ценность графов.
3. СОСТАВЛЕНИЕ ОПТИМАЛЬНОГО МАРШРУТА ПОСЕЩЕНИЯ МУЗЕЕВ БОЕВОЙ СЛАВЫ
Указом президента Российской Федерации от 16.01.2025 № 28 "О проведении в Российской Федерации Года защитника Отечества", в целях сохранения исторической памяти, в ознаменование 80-летия Победы в Великой Отечественной войне 1941-1945 годов, в благодарность ветеранам и признавая подвиг участников специальной военной операции, 2025 год объявлен Годом защитника Отечества.
Год защитника Отечества в 2025 году – это не просто календарная дата, а символ национального единства и патриотизма. Это выражение глубокой признательности тем, кто защищал и продолжает защищать суверенитет и безопасность нашей страны. Это год, который напоминает нам о важности исторической памяти и о непреходящей ценности мира, который защищают наши защитники Отечества своей мужественностью и самоотверженностью.
Этот год станет данью уважения к ратному подвигу всех, кто сражался за Родину в разные исторические эпохи, а также нынешним героям – участникам специальной военной операции. Тематика года отражает приоритеты современной России, такие как патриотизм, преемственность поколений и уважение к защитникам Родины во все времена.
Поэтому посещение музеев боевой славы г.о. Самара учащимися образовательных учреждений в этом году актуально как никогда.
В первую очередь предлагаем рассмотреть данные музеи, расположенные в Куйбышевском районе г.о. Самара. В нашем районе расположены пять музеев боевой славы.
Рисунок -6
Рисунок -7
Рисунок -8
Рисунок -9
Таким образом, мы решили составить маршрут по следующим объектам:
1. Музей боевой славы городов-героев, Фасадная ул., 19
3. Музей боевой славы 62/8 Гвардейской Армии, Фасадная ул., 2А.
4. Музей боевой славы 46-го Гвардейского Таманского женского авиаполка лёгких ночных бомбардировщиков, улица 40 лет Пионерии, 16.
5. Музей Боевой и трудовой Славы поселка 113 км, Липяговская улица, 3А.
6. Музей боевой славы имени Героя Российской Федерации Виталия Викторовича Талабаева, ул. Академика Тихомирова, 2.
7. Музей боевой и трудовой славы истории совхоза Кряж, Центральная улица, 11А.
Все музеи изображены на карте города (рис.10).
Началом и окончанием нашего маршрута является Школа № 24 имени Героя Советского Союза М.И. Буркина, Пугачёвский тракт, 27А.
Рисунок-10
Рисунок-11
Рисунок -12
Данный маршрут представлен в виде неориентированного графа на рисунке 11 и в виде взвешенного графа на рисунке 12. Вес означает расстояние между пунктами. Данный граф можно представить в виде таблице 1.
Таблица 1 – Таблица, описывающая граф на рисунке 12
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
1 |
|
900 |
|
|
|
|
600 |
|
2 |
900 |
|
637 |
|
|
|
|
|
3 |
|
637 |
|
563 |
|
|
|
|
4 |
|
|
563 |
|
4200 |
|
|
|
5 |
|
|
|
4200 |
|
8400 |
|
|
6 |
|
|
|
|
8400 |
|
7720 |
|
7 |
600 |
|
|
|
|
7720 |
|
Из пункта 1 в пункты 2, 3 и 4 мы будем передвигаться пешком, а в пункты 5, 6. 7 и обратно в пункт 1 на автобусах. Из пункта 4 в пункт 5 на автобусе №76, из пункта 5 в пункт 6 на автобусе №17, из пункта, из пункта 6 в пункт 7 на автобусе №86, из пункта 7 в пункт 1 на автобусе №26.
Теперь поставим задачу нахождения оптимального, то есть кратчайшего пути посещения музеев. Для этого будем использовать алгоритм Дейкстры.
Алгоритм Дейкстры работает на ориентированных (с некоторыми дополнениями и на неориентированных) графах, и призван искать кратчайшие пути между заданной вершиной и всеми остальными вершинами в графе.
Как правило, граф обозначают как набор вершин и рёбер G = (V,E), где число рёбер может быть задано m, а вершин числом n.
Для каждого ребра в графе задан неотрицательный вес i, а также вершина, из которой осуществляется поиск оптимальных путей.
Алгоритм Дейкстры может найти кратчайший путь между вершинами s и t в графе, только если существует хотя бы один путь между этими вершинами. Если это условие не выполняется, то алгоритм отработает корректно, вернув значение "бесконечность" для пары несвязанных вершин.
Условие неотрицательности весов рёбер крайне важно и от него нельзя просто избавиться. Не получится свести задачу к решаемой алгоритмом Дейкстры, прибавив наибольший по модулю вес ко всем рёбрам. Это может изменить оптимальный маршрут.
Рисунок 13
Исходя из рисунка 13, используя алгоритм Дейкстры мы должны выбирать путь с наименьшими весами. Из пункта 6 выгоднее поехать в пункт 1, но тогда не получится посетить пункт 7. Получается, что пеший маршрут изначально выбран оптимально, а пункты 5, 6, 7 с учетом их отдаленности и необходимости посещения всех пунктов по другому посещать нецелесообразно. Поэтому маршрут на рисунке 12 признается оптимальным. Пеший маршрут составит 2,1 км, автобусный 26,32 км. По времени на посещении всех музеев уйдет полный рабочий день с 9ч до 17ч. Данный граф будет являтся Эйлеровым.
Таким образом в течении рабочего дня учащиеся могут посетить 6 музеев боевой славы Куйбышевского района г.о. Самара.
В дальнейшем исследование мы планируем построить графы маршрута по военным музеям всего г.о. Самара.
ЗАКЛЮЧЕНИЕ
В результате проведенного исследования мы пришли к следующим выводам, что теория графов тесно связана с нашей жизнью, но мы этого часто даже не замечаем: различные маршруты (от дома до школы, походы по магазинам, экскурсии по городу и др.), составление генеалогического дерева, маршруты автобусов и троллейбусов, карты городов и др.
Теория графов и связанные с ним методы исследований в настоящее время является интенсивно развивающимся разделом дискретной математики. Язык графов прост, понятен и нагляден.
В ходе написания исследовательской работы мы рассмотрели лишь некоторые вопросы по теории графов, подробно познакомились с достопримечательностями и автобусными маршрутами Куйбышевского района г Самара, составили граф по музеям боевой славы, изучили полученный граф и нашли всевозможные пути прохождения данных вершин. Изучив составленные графы, выбрали наиболее короткий и удобный маршрут для посещения музеев, связанных с Великой Отечественной войной, которые находятся в нашем районе. Составили буклет экскурсионного маршрута по музеям боевой славы Куйбышевского района г Самара, связанным с Великой Отечественной войной.
Теорию графов можно применять не только при составлении экскурсионных маршрутов, но и при распределении автозаправок, станций скорой помощи, наиболее удобных и экономичных маршрутов транспорта.
Главным результатом нашей работы явилось создание с применением теории графов буклета «экскурсионного маршрута по музеям боевой славы Куйбышевского района г.о. Самары с помощью теории графов»
БИБЛИОГРАФИЧЕСКИЙСПИСОК:
1. Годунова, Е. К. Введение в теорию графов. Индивидуальные задания / Е.К. Годунова. - М.: Прометей, 2016. - 927 c.
2. ГРАФЫ И ОБЛАСТИ ИХ ПРИМЕНЕНИЯ. URL: https://school-science.ru/4/7/33615 Электронный ресурс. (дата обращения 10.03.2025).
3. URL: www.obuchonok.ru Электронный ресурс. (дата обращения 20.03.2025).
4. URL: www. infourok.ru Электронный ресурс. (дата обращения 20.03.2025).
5. URL: www. nsportal.ru Электронный ресурс. (дата обращения 20.03.2025).
6. URL: www. урок.рф Электронный ресурс. (дата обращения 21.03.2025).
7. URL: www. multiurok.ru Электронный ресурс. (дата обращения 22.03.2025).