XIV Международный конкурс научно-исследовательских и творческих работ учащихся
Старт в науке
Составление экскурсионного маршрута с помощью теории графов
Автор работы награжден дипломом победителя II степени
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
Введение
Наш мир полон не только букв и цифр, но и самых разных изображений. Это и картины, и всевозможные фотографии (начиная с кадров из отпуска и заканчивая рекламными щитами), и произведения искусств различных стилей, а также многочисленные схемы. Часто мы встречаем автобусные маршруты, троллейбусные маршруты.
Современная комбинаторика – это красивейший, бурно развивающийся раздел математики, богатый яркими результатами и нетривиальными приложениями в алгебре, геометрии, анализе и т.д., см. хотя бы [4], [3], [7]. Одна из центральных глав в комбинаторике – теория графов [5], [6].
Удивительная простота графа нашла применение во многих областях. Они позволяют решить множество интересных задач, и им посвящен отдельный раздел современной математики «Теория графов».
Это и обуславливает актуальность выбранной темы.
В 2020 году страна отмечала 75 лет Победы советского народа в Великой Отечественной Войне и окончание Второй Мировой Войны. Значимый вклад в победу в этой войте внесли и наши земляки - жители г. Самара (г. Куйбышев в годы Великой Отечественной войны). Не зря наш город называли в то время запасной столицей.
В связи с такими знаменательными датами перед нами стала задача проехаться по памятным местам Самара, воздвигнутым в честь Великой Отечественной Войны. Для этого мы выбрали памятники, и уже были готовы отправиться в путь, но перед нами стал вопрос, а как проехать по данным достопримечательностям не проезжая дважды по выбранным местам и по одной и той же дороге. Оказалось, что для решения данного вопроса нам поможет математика и ее раздел «Теория графов».
Гипотеза: составить путь прохождения достопримечательностей города Самара, не проходя по ним дважды.
Графом в математике называется конечная совокупность точек, именуемых вершинами; некоторые из них соединены друг с другом линиями, называемых ребрами графа [9, c.85]. Графы используют при составлении карт и генеалогических древ. Графами являются блок-схемы программ для ЭВМ, сетевые графики строительства. Одними из самых распространённых графов являются схемы линий метрополитена.
Цель исследовательской работы: исследование возможности применения теории графов для составления экскурсионного маршрута по памятным местам г. Самара.
В связи с поставленной целью появляются следующие задачи нашей работы:
ознакомиться с основными положениями теории графов;
составить граф достопримечательностей города Самара;
изучить заданный граф;
составить путь прохождения заданного графа:
изготовить буклет.
Глава 1. Основные понятия теории графов
Графы возникли в восемнадцатом столетии, когда известный математик, Леонард Эйлер, пытался решить теперь уже классическую задачу о Кенигсбергских мостах. В то время в городе Кенигсберге было два острова, соединенных семью мостами с берегами реки Преголь и друг с другом так, как показано на рисунке 1.1.
Задача состоит в следующем: осуществить прогулку по городу таким образом, чтобы, пройдя ровно по одному разу по каждому мосту, вернуться в то же место, откуда начиналась прогулка. Решая эту задачу, Эйлер изобразил Кенигсберг в виде графа, отождествив его вершины с частями города, а ребра — с мостами, которыми связаны эти части.
Рисунок 1.1
Эйлеру удалось доказать, что искомого маршрута обхода города не существует.
Неориентированным графом G (V, E) называется совокупность двух множеств: не пустого множества V (множества вершин) и множества E - множество неупорядоченных пар элементов из V (множества ребер) [2, c.37].
Маршрутом в графе называется последовательность вершин и ребер v0, v1, v2, v3, …vn [1, c.120].
Длиной маршрута называется количества ребер в нем.
Маршрут, в котором все вершины различны, называется простой цепью.
Замкнутая простая цепь называется простым циклом.
Замкнутая цепь называется циклом [8, c.55].
Ориентированный граф или орграф называется граф, у которого множество ребер является множеством упорядоченных пар [2, c.55].
Еще один из выделяемых видов графов связан с возможностью попадания из одной его вершины в другую.
Две вершины называются связными, если существует маршрут между ними. Связность для вершин является бинарным отношением.
Неориентированный граф называется связным, если между любыми двумя вершинами есть маршрут.
Любой граф G можно разбить на непересекающиеся подмножества вершин по признаку связности. Вершины одного множества являются связными между собой, а вершины различных множеств – несвязны. Тогда все выделенные таким образом подграфы называют компонентами связности графа G. При этом связный граф имеет одну компоненту связности [4, c.8].
Доказано, что в конечном связном графе всегда можно построить ориентированный цикл, проходящий через каждое ребро по одному разу в двух направлениях. Такой цикл называют способом обхода графа и используют при решении многих прикладных задач. В частности разработаны специальные алгоритмы обхода ребер графа, которые можно использовать при решении задач вида «поиска выхода из лабиринта».
Ребро (v, u) связного графа G называется мостом, если после его удаления G станет несвязным и распадется на два связных графа G’ и G’’.
Граф называется гамильтоновым, если для каждой вершины графа найдется маршрут начинающейся и заканчивающей в этой вершине и проходящий через все вершины только один раз. Такой маршрут называется гамильтоновым циклом.
Гамильтоновы графы применяются для моделирования многих практических задач, например, служат моделью при составлении расписания движения поездов. Основой всех таких задач служит классическая задача коммивояжера: коммивояжер должен совершить поездку по городам и вернуться обратно, побывав в каждом городе ровно один раз, сведя при этом затраты на передвижения к минимуму.
Графическая модель задачи коммивояжера состоит из гамильтонова графа, вершины которого изображают города, а ребра — связывающие их дороги. Кроме того, каждое ребро оснащено весом, обозначающим транспортные затраты, необходимые для путешествия по соответствующей дороге, такие, как, например, расстояние между городами или время движения по дороге. Для решения задачи необходимо найти гамильтонов цикл минимального общего веса.
К сожалению, эффективный алгоритм решения данной задачи пока не известен. Для сложных сетей число гамильтоновых циклов, которые необходимо просмотреть для выделения минимального, непомерно огромно. Однако существуют алгоритмы поиска субоптимального решения. Субоптимальное решение необязательно даст цикл минимального общего веса, но найденный цикл будет, как правило, значительно меньшего веса, чем большинство произвольных гамильтоновых циклов.
Для полных графов поиск гамильтоновых циклов осуществляется с помощью алгоритма ближайшегососеда:
1. Выбрать исходную вершину и включить её в маршрут.
2. Выбрать вершину ближайшую к данной по весу, включить её в маршрут.
3. Выбрать не использованные вершины ближайшую к последней, включить её в маршрут.
4. Вернуться к шагу 2 если не использованы все вершины.
5. Включить в маршрут исходную вершину[9, c.75]..
Гамильтонова цепь – это цепь, которая проходит через все вершины по одному разу без возвращения в начальную вершину. Рёбра при этом могут быть пройдены не все [2, c.23].
Все изложенные понятия помогут нам правильно составить граф по достопримечательностям города Самара и положительно ответить на вопрос гипотезы.
Глава 2. Применение теории графов
2.1 Достопримечательности г. Самара
Исторических мест, посвященных победе в Великой Отечественной войне, в Самаре присутствует немало. Мы выбрали 5 достопримечательностей. А именно:
Вечный огонь и горельеф «Скорбящей Матери-Родине» на могиле неизвестного солдата.
Памятник несовершенным труженикам тыла
Памятник, посвященный памяти шоферов, погибших в годы Великой Отечественной войны
Фонтан «Парус»
Самолет- штурмовик Ил-2
Ф онтан «Парус»
В 1986 году, неподалеку от речного вокзала был открыт фонтан «Парус».
Фонтан был создан в честь 400-летия основания города. Высота «Паруса» составляет около 13 метров, а вес достигает 16 тонн. Одной из особенностей этого фонтана является количество струй, расположенных в нем. Считается, что 620 струй – по числу юнг, погибших в Великой Отечественной войне. Этот фонтан является эмблемой Самары и одним из символов города. Фонтан «Парус» расположен на Ленинградском спуске на Набережной реки Волги.
Вечный огонь и горельеф «Скорбящей Матери-Родине» на могиле неизвестного солдата.
На момент 30-летия с начала Великой Отечественной войны, 5 сентября 1971 года, был зажжен Вечный огонь монумента. Он горит в память о 225 тысячах уроженцах Куйбышева и Куйбышевской области, павших на поле боя, защищая свое отечество. Памятник расположен на площади Славы.
П амятник несовершеннолетним труженикам тыла
Данный памятник был построен благодаря обществу «Дети-фронту», которое появилось в 1992 году. Именно это общество стало инициатором открытия памятника детям, чей труд в годы Великой Отечественной войны был большим вкладом в общую победу. Памятник установлен на пересечении улиц Полины Осипенко и Ново-Садовой.
С амолет-штурмовик Ил-2
В начале 1970-х годов ветеранами авиационного завода было принято решение установить у проходной завода памятник, в виде боевого самолёта Ил-2. Но оказалось, что у завода, изготовившего в годы войны более 15000 самолётов Ил-2, нет ни одного экземпляра, а в ВВС он, конечно, давно снят с вооружения. Осенью 1970 года в болотах Мурманской области был обнаружен самолёт Ил-2. Просмотрев архивы, выяснилось, что самолет был сбит в марте 1943 года. Самолёт был доставлен в Куйбышев на авиационный завод, где старые рабочие по памятисобрали и отремонтировали все, что было нужно. Самолет был полностью отремонтирован и поставлен 7 мая 1975 года, а торжественное открытие состоялось 9 мая. Также, по некоторым источникам, эту боевую машину прозвали «Летающим танком». В данный момент самолет находится на пересечении проспекта Кирова с Московским шоссе.
Памятник, посвященный памяти шоферов, погибших в годы Великой Отечественной войны
З наменитый автомобиль ЗИС-5 был установлен на постамент 15 мая 1985.Автомобиль находился в ангаре транспортного цеха в нерабочем состоянии, его решено было восстановить и возвести на постамент к моменту 40-летия победы, в память о подвигах шоферов Великой Отечественной войны. Механики и водители транспортного цеха собирали машину после работы. Машину восстановили достаточно быстро, ведь у людей, восстанавливающих ее, были золотые руки и огромное желание увековечить память героев. Располагается памятник на пересечении улиц 22-ого Партсъезда и Красных Коммунаров.
2.2 Экскурсионный маршрут
О пределившись с памятными местами в Самаре, нанесем на карту выбранные памятники и соединим их по дорогам.
1-Фонтан «Парус»
2-Вечный огонь и горельеф «Скорбящей Матери-Родине» на могиле Неизвестного Солдата.
3-Памятник несовершеннолетним труженикам тыла.
4-Самолет-штурмовик Ил-2
5-Памятник, посвященный памяти шоферов, погибших в годы Великой Отечественной войны.
С оставление графа.
Построенный граф назовем G.
Граф G является неполным. Проведем недостающие ребра и получим полный граф G1(рис. 2.9).
Рисунок 2.8
Полный граф — простой неориентированный граф, в котором каждая пара различных вершин смежна.
И сходный граф G (рис. 2.8) состоит из 5 вершин (v1, v2 , v3, v4 , v5 ) и 6 ребер, которые отображают памятники и мемориалы посвященные Великой Отечественной Войне.
Рисунок 2.9
Вершина v1 имеет степень 1 (т.к. из нее выходит только одно ребро).
Вершина v2 имеет степень 3 (т.к. из нее выходит три ребра).
Вершина v3 имеет степень 2 (т.к. из нее выходит два ребра).
Вершина v4 имеет степень 3 (т.к. из нее выходит три ребра).
Вершина v5 имеет степень 2 (т.к. из нее выходит два ребра).
Ребро (v1 v2) является мостом, т.к. полученный граф G распадается на два и .
Граф G является конечным (т.к. число вершин конечно). Заданный граф не является ориентированным (т.к. вершины не упорядочены).
Граф G является связным.
Существует замкнутый путь по ребрам графа .
По данному графу можно заметить, что составить гамильтонов цикл не получится, так как вершина v1 имеет степень 1, значит, можно, либо выйти из вершины или войти. Следовательно, мы будем искать гамильтонову цепь (это цепь, которая проходит через все вершины по одному разу без возвращения в начальную вершину.).
Составим всевозможные пути:
1- v1,v2,v3,v4,v5 (рис.2.11 а ) 2- v1,v2,v4,v5,v3 (рис.2.11 б ) 3-v1,v2,v4,v3,v5 (рис.2.11 в ) 4- v5,v4,v3,v2,v1 (рис.2.11 г ) 5- v5,v3,v4,v2,v1 (рис.2.11 д )
Рисунок 2.11 (а, б, в, г, д)
Для выполнения поставленной задачи мы изучили различные пути передвижения для посещения памятных мест. В ходе выполнения поставленных задач, мы пришли к следующим выводам:
1) От Фонтана «Парус» (Речной Вокзал) до памятника «Вечный огонь и горельеф «Скорбящей Матери-Родине» на могиле неизвестного солдата» (Гостиница "Волга") – автобус 261 (3 км, приблизительно 18 мин)
2) От памятника «Вечный огонь и горельеф «Скорбящей Матери-Родине» на могиле неизвестного солдата» (Самарская Площадь) до «Памятника несовершеннолетним труженикам тыла» (Площадь Героев 21-ой Армии) - трамвай №20(2 км, приблизительно 24 минуты)
3) От памятника «Вечный огонь и горельеф «Скорбящей Матери-Родине» на могиле неизвестного солдата» (Гостиница "Волга") до памятника "Самолет-штурмовик Ил-2"(Московское шоссе) - автобус №261(13км, приблизительно 41 минута)
4) От памятника «Вечный огонь и горельеф «Скорбящей Матери-Родине» на могиле неизвестного солдата» (Гостиница "Волга") до памятника, посвященного памяти шоферов, погибших в годы Великой Отечественной войны (Метро Победа) - автобус №247(10 км, приблизительно 35 минут)
5) От «Памятника несовершеннолетним труженикам тыла» (Площадь Памяти) до «Самолет Ил-2» (Площадь авиаконструктора Ильюшина) – автобус №67(11 км, приблизительно 36 минут)
6) От «Самолет Ил-2»" (ул. Бубнова) до «Памятника, посвященного памяти шофёров ,погибших в годы Великой Отечественной войны» (Метро Победа) – маршрутка №205 (7 км, приблизительно 31 минута)
7) От памятника посвященного памяти шоферов, погибших в годы Великой Отечественной войны (Станция метро Победа) до памятника несовершеннолетним труженикам тыла (станция метро Алабинская) – метро (9 км, приблизительно 5 минут)
Изучив ближайшие остановки до выбранных нами памятных мест, и поработав с автобусными маршрутами, чтобы определиться какой маршрут подойдет именно нам, мы составили таблицу 2.1 «Маршрут городского транспорта», проехав по которому, можно посетить в г. Самара памятники, связанные с подвигом земляков во время Великой Отечественной войны.
Таблица 2.1
Маршрут городского транспорта
|
От вершины |
Остановка |
До вершины |
Остановка |
Маршрут |
|
v1 |
Речной Вокзал |
v2 |
Гостиница "Волга" |
Автобус №261 |
|
v2 |
Самарская Площадь |
v3 |
Площадь Героев 21-ой Армии |
Трамвай №20 |
|
v2 |
Гостиница "Волга" |
v4 |
Московское шоссе |
Автобус №261 |
|
v2 |
Гостиница "Волга" |
v5 |
Метро Победа |
Автобус №247 |
|
v3 |
Площадь Памяти |
v4 |
Площадь Авиаконструктора Ильюшина |
Автобус №67 |
|
v4 |
ул. Бубнова |
v5 |
Метро Победа |
Маршрутка №205 |
|
v5 |
Метро Победы |
v3 |
Метро Алабинская |
Метро |
Один из удобных для нас вариантов (без пересадок между вершинами и не пользуясь троллейбусом) является маршрут, цепь которого представлена следующим образом v1,v2,v3,v4,v5 (рис. 2.11 а).
Заданный нами маршрут будет являться открытым, так как его концевые точки не совпадут. Маршрут будет являться цепью, потому, что ни одно ребро не повторилось.
Заданный нами экскурсионный маршрут построился таким образом: «Фонтан «Парус», «Вечный огонь и горельеф «Скорбящей Матери-Родине» на могиле неизвестного солдата», «Памятник несовершеннолетним труженикам тыла», «Самолет Ил-2», «Памятник, посвященный памяти шофёров, погибших в годы Великой Отечественной войны».
А теперь подберем городские автобусы для удобного перемещения.
Маршрут поездок на автобусе:
- От Фонтана «Парус» (Речной Вокзал) до Памятника «Вечный огонь и горельеф «Скорбящей Матери-Родине» на могиле неизвестного солдата» (Гостиница "Волга") – автобус 261.
- От Памятника «Вечный огонь и горельеф «Скорбящей Матери-Родине» на могиле неизвестного солдата» (Самарская Площадь) до ,,Памятника несовершеннолетним труженикам тыла» (Площадь Героев 21-ой Армии) - трамвай №20.
- От «Памятника несовершеннолетним труженикам тыла» (Площадь Памяти) до «Самолет Ил-2» (Площадь авиаконструктора Ильюшина)–автобус 67.
- От «Самолет Ил-2»" (ул. Бубнова) до «Памятника, посвященного памяти шофёров ,погибших в годы Великой Отечественной войны» (Метро Победа). – маршрутка №205.
Экскурсионный маршрут по памятным местам города Самара удалось составить с помощью графов без прохождения выбранного памятника дважды.
Заключение
Теория графов тесно связана с нашей жизнью, но мы этого часто даже не замечаем: различные маршруты (от дома до школы, походы по магазинам, экскурсии по городу и др.), составление генеалогического дерева, маршруты автобусов и троллейбусов, карты городов и др.
Теория графов и связанные с ним методы исследований в настоящее время является интенсивно развивающимся разделом дискретной математики. Язык графов прост, понятен и нагляден.
В ходе написания исследовательской работы мы рассмотрели лишь некоторые вопросы по теории графов, подробно познакомились с достопримечательностями и автобусными маршрутами г Самара, составили граф по памятным местам, изучили полученный граф и нашли всевозможные пути прохождения данных вершин. Изучив составленные графы, выбрали наиболее короткий и удобный маршрут для посещения памятников, связанных с Великой Отечественной войной, которые находятся в г. Самара. Составили буклет экскурсионного маршрута по памятным местам г. Самара, связанным с Великой Отечественной войной.
Теорию графов можно применять не только при составлении экскурсионных маршрутов, но и при распределении автозаправок, станций скорой помощи, наиболее удобных и экономичных маршрутов транспорта. Мы надеемся, что достойное место займет созданный нами буклет «Экскурсионный маршрут по памятным местам в городе Самара 1941-1945»
Главным результатом нашей работы явилось создание с применением теории графов буклета «Экскурсионный маршрут по памятным местам г. Самара» (ПРИЛОЖЕНИЕ 1).
После того, как был составлен маршрут, мы прошли по нему все выбранные памятники города Самара. Каждый монумент вызывал чувство гордости за Родину, благодарность за подаренную нам жизнь перед каждым кто защитил нас, своих будущих потомков, от немецко-фашистских захватчиков.
Хочется пожелать всем не забывать подвиг наших дедов и прадедов в Великой Отечественной Войне!
Со своей работой я выступал на занятиях внеурочной деятельности в 9-х, 10-х и 11-х классах школы. Результаты работы используются моим руководителем и другими учителями при проведении занятий внеурочной деятельности, что подтверждается справкой школы (ПРИЛОЖЕНИЕ 2).
Данную тему можно развивать. Можно, применив теорию графов, составить кратчайшие и удобные маршруты по другим достопримечательностям г. Самара, например: «Исторические места г. Самара», «Парки г. Самара», «ВУЗы г. Самара» и др.
Библиографический список
Альсина К. Карты метро и нейронные сети .Теория графов/ К. Альсина// Мир математики/ К. Альсина. — Де Агостини, 2015. — 140 с.
Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990. 384с. (Изд.2, испр. М.: УРСС, 2009. 392 с.)
Лекции по теории графов/Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. – М.: Наука,.Гл. ред. физ.-мат. лит., 1990. – 384с
Оре О., Теория графов./ О. Оре — М.: Наука, 1968. —336с.
Савин, А. Графы/ А. Савин//Квант №6. – 1994. – ноябрь/декабрь – С.32
Савин А.П. Графы// Энциклопедический словарь юного математика/ Сост. А.П. Савин.- М.: Педагогика, 1989. – 352стр.
Уилсон Р. Введение в теорию графов/ Р. Уилсон. - Пер с англ. М.: Мир, 1977. — 208с
Харари Ф. Теория графов/ Ф. Харари. – М.: Мир, 1973. – 300с.
Элементы математики в задачах (с решениями и комментариями). Ч. I / Т. И. Голенищева-Кутузова, А. Д. Казанцев, Ю. Г. Кудряшов и др.—М.:МЦНМО, 2010.—248 с.
ПРИЛОЖЕНИЕ 1
Буклет «Экскурсионный маршрут по памятным местам г. Самара»
сторона 1
Буклет сторона 2
ПРИЛОЖЕНИЕ 2
Справка об использовании материалов исследовательской работы
в рамках внеурочных занятий в школе