IX Международный конкурс научно-исследовательских и творческих работ учащихся
Старт в науке
Маршрут осмотра достопримечательностей микрорайона «Родники» города Новосибирска с помощью графа
Автор работы награжден дипломом победителя II степени
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
1. Введение
Наша семья проживает в микрорайоне «Родники» два года. Этот район красивый, в нем много достопримечательностей. Если к нам приедут гости, то им захочется посмотреть достопримечательности нашего микрорайона. Возникает проблема: «Как разработать такой маршрут?». С такой же проблемой сталкиваются, например, риэлторы по продажам квартир. Они возят потенциальных покупателей квартир в этом районе и должны выбирать наиболее короткий и удобный маршрут, чтобы показать интересные места нашего района, а также необходимую инфраструктуру.
Разработать такой маршрут можно используя графическую схему - граф. Поэтому цель моей проектной работы, следующая:
Цель: создать удобный маршрут осмотра достопримечательностей микрорайона «Родники» города Новосибирска с помощью графа.
Задачи проекта:
1. изучить понятие графа и элементы теории графов; понятие масштаба;
2. познакомиться с решением задач на обход фигуры одним росчерком;
3. разобраться с решением задачи о Кёнигсбергских мостах;
4. составить граф достопримечательностей микрорайона «Родники»;
5. найти удобный маршрут осмотра достопримечательностей микрорайона «Родники» города Новосибирска с использованием графа.
6. собрать информацию по истории названия улиц и строительства микрорайона.
7. создать макет «карта-граф микрорайона»
Методы исследования:
• Наблюдение
• Анализ и синтез
• Сравнение
• Обобщение
• Определение понятий
• Геометрические построения
• Макетирование
2. Основная часть
2.1. Теоретическая часть
2.1.1. Понятие графа. Элементы теории графов.
В 1736 году в Петербурге Леонард Эйлер сформулировал теорию графов.
Э йлер Леонард (1707—1783), математик, физик, механик, астроном.
Родился 15 апреля 1707 г. в Базеле (Швейцария).
В 1726 г. по приглашению Петербургской академии наук приехал в Россию и был назначен адъюнктом по математике. Эйлеру принадлежит более 865 исследований по самым разнообразным и труднейшим вопросам. Скончался Эйлер 18 сентября 1783 г. в Петербурге.
Граф – это набор точек, которые называются вершинами графа и набор соединяющих эти точки дуг или отрезков, которые называются ребрами графа.
Использование теории графов при решении математических задач очень помогает, так как позволяет наглядно показать решение. Графы также могут использоваться, не только в математических задачах, но и при решении других логических задач, где есть необходимость наглядно представить планы или схемы действий. Это могут быть задачи из областей экономики, управления или программирования. Графы используют для составления блок-схем программ, помогают наглядно представить решение экономических задач, применяются при составлении разнообразных планов и схем действий в различных ситуациях и т.п.
Будем считать, что если две вершины графа соединены ребром, то только одним, и нет «петель», то есть рёбер, начало и конец которых совпадают. Такие графы называются простыми графами, и мы будем рассматривать, в основном, только простые графы.
Порядком (или степенью) вершины графа называется количество рёбер, исходящих из этой вершины. Вершина называется чётной, если из неё выходит чётное число рёбер, и нечётной, если из неё выходит нечётное число рёбер. Приведем некоторые примеры графов:
На рисунке 1 изображён граф, имеющий изолированную вершину, её порядок равен 0, и две вершины порядка 1. Отметим, что этот граф не связен.
На рисунке 2 изображён связный граф, на котором нет циклов. Такие графы называются деревьями.
На рисунке 3 у графа уже есть цикл. Он также является связным.
На рисунке 4 граф тоже является связным, а так как любые две его вершины соединены ребром, то его называют полным.
Полным является и граф на рисунках 3. А ещё графы на рисунках 3 и 4 называют плоскими правильно нарисованными графами, так как его рёбра не пересекаются во внутренних точках. Заметим, что правильно нарисованный плоский граф разбивает плоскость на несколько частей.
Свойство графов:
1. Граф, имеющий более двух вершин нечётной степени, невозможно начертить одним росчерком (не отрывая ручки от бумаги и не проводя никакое ребро дважды).
2. Сумма степеней вершин графа равна удвоенному количеству его рёбер.
3. В графе количество вершин нечётной степени чётно.
4. В любом связанном графе можно удалить некоторое количество ребер так, что граф станет деревом.
5. В дереве любые две вершины соединены ровно одним путём.
6. В дереве нельзя вернуться в исходную вершину, двигаясь по ребрам и проходя по одному ребру не более одного раза.
7. В дереве есть вершина, из которой выходит только одно ребро.
Также ещё есть некоторые понятия такие как:
Эйлеров путь или Эйлерова цепь в графе — это путь, проходящий по всем рёбрам только один раз.
Эйлеров цикл — это эйлеров путь, который является циклом (замкнутым путём), проходящий через каждое ребро графа только по одному разу.
Эйлеров граф — это граф, созданный с помощью эйлерова цикла.
Например, в задачах на обход фигуры одним росчерком можно использовать понятие графа.
Задача: можно ли обвести фигуру на рисунке 5 одним росчерком?
Рис.5
На рисунке 5 изображена фигура, которую можно рассматривать в виде графа. У нее 1 и 3 вершины имеют 3 ребра (их можно назвать нечетными), а 2 и 4 вершины имеют 2 ребра (их можно назвать четными). Эту задачу можно легко решить, если знать некоторые правила графа. Так как, если в фигуре не более 2 двух нечётных вершин, тогда ее можно обвести одним росчерком.
Эту задачу можно решить так: из 1 вершины идём к 3 вершине, а от 3 вершины ко 2 вершине, из 2 вершины идём к 1 вершине и из 1 вершины идём к 4 вершине, а от 4 вершины идем к 3 вершине.
В данной задаче нами описан Эйлеров путь или Эйлерова цепь. Описанный Эйлеров путь является замкнутым и называется Эйлеровым циклом, так как он проходит через каждое ребро графа только по одному разу. Этот Эйлеров цикл, мы также можем называть эйлеров граф.
Задача о Кёнигсбергских мостах.
Рассмотрим задачу о Кёнигсбергских мостах. В этой задаче предлагается пройти по всем семи мостам за один обход (рис. 6). Многие пытались решить эту задачу как теоретически, так и практически. Однажды её предложили решить выдающемуся математику Леонарду Эйлеру. И в итоге, он смог найти правило, пользуясь которым, легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них.
рис. 6 рис. 7
Эйлер обобщил постановку задачи о кенигсбергских мостах и нашел критерий нахождения на графе замкнутого маршрута, содержащего все ребра. Требование связности графа очевидно: если имеется изолированная часть графа, то ее не достигнешь и не пройдешь. Значит, чтобы пройти через вершину, зайти по одному ребру и выйти по-другому – нужны два ребра, значит, если ребер нечетное количество, то из вершины нет выхода. Следовательно, число ребер, проходящих через вершину, должно быть обязательно четным. Если отбросить условие возвращения в исходную вершину, то можно допустить наличие двух вершин, из которых выходит нечетное количество ребер. В этом случае начинать движение следует с одной из этих двух вершин, а заканчивать – в другой. У графа не может быть ровно одной нечетной вершины, а если у него нет нечетных вершин, то обход можно начинать с любой вершины и в ней же заканчивать.
Вернемся к графу с кенигсбергскими мостами (рис.7). Здесь при каждой из четырех вершин нечетное число ребер, так что нет не только эйлерова цикла, но и пути из одной вершины в другую, проходящего по всем ребрам графа, поэтому граф обойти нельзя. Итак, задача для данного расположения семи мостов неразрешима.
2.1.2. Понятие масштаба.
Для нахождения расстояния по карте надо понимать понятие масштаба. Масштаб показывает во сколько раз длина отрезка на рисунке меньше длины соответствующего отрезка на местности. Например, запись 1: 7000 означает, что в 1 см на карте содержится 7000 см на местности.
2.2. Практическая часть
2.2.1. Граф для достопримечательностей микрорайона «Родники».
Определим самые интересные места нашего микрорайона «Родники»:
ФЦ (Фехтовальный Центр), С (Сквер на Свечникова), ЛД (Ледовый дворец «Родники»), Х (Храм во имя святого апостола Андрея Первозванного), Ш (Средняя общеобразовательная школа МАОУ СОШ № 211 имени Леонида Ивановича Сидоренко).
Изобразим их кружками с обозначениями на графе. Соединим вершины линиями, соответствующими автомобильным дорогам, учитывая карту местности нашего района (рис. 9). Граф связный, он имеет 13 вершин (8 нечетных вершин 3 степени и 5 четных вершин: 3 вершины 2 степени и 2 вершины 4 степени). Объезд невозможен за один раз, не проезжая по одной дороге дважды, так как в графе 8 нечетных вершин. Поэтому этот граф не будет являться эйлеровым.
рис.8
Карта микрорайона «Родники»
рис.9
2.2.2. Удобный маршрут осмотра достопримечательностей микрорайона «Родники».
Я проживаю в микрорайоне «Родники» около фехтовального центра. Поэтому, если к нам приедут гости, то удобнее для нас начинать маршрут осмотра микрорайона из этой точки. Для этого рассматриваются такие варианты обхода графа, чтобы выехать из вершины ФЦ, проехать по дорогам один раз через какие-либо вершины, включая вершины С, ЛА, Х, Ш, и вернуться в начальную вершину ФЦ около нашего дома.
Рассмотрим все возможные варианты обходов при таких условиях, то есть, составляя эйлеровы графы. Работая с картой микрорайона (рис.9), с графом на рис. 8 и используя дерево возможных вариантов, получаем 9 таких замкнутых обходов. Чтобы подсчитать все варианты, для наглядности был сделан макет (Приложение 1). Каждый путь можно провести с помощью цветной нити. Сравнивая длины использованных нитей, можно определить наиболее короткий маршрут.
Маршрут 1.
На рис. 10 граф имеет 5 вершин (5 четных). Объезд по вершинам возможен, если мы начнем с любой вершины. Например: от вершины ФЦ (Фехтовальный Центр) к вершине С (Сквер на Свечникова), затем к вершине ЛА (Ледовый арена «Родники»), далее к вершине Х (Храм во имя святого апостола Андрея Первозванного), потом к вершине Ш (МАОУ СОШ № 211 имени Л.И. Сидоренко) и вернуться к вершине ФЦ (Фехтовальный Центр). Граф 1 можно н азвать эйлеровым циклом.
рис.10 рис.11
Используя карту и масштаб 1:7000, вычисляем длину маршрута 1, она приблизительно будет составлять 5430 метров.
Обход этого маршрута можно сделать как по часовой стрелке, так и против часовой стрелки. ФЦ-С-ЛА-Х-Ш-ФЦ или ФЦ-Ш-Х-ЛА-С-ФЦ.
Маршрут 2.
На графе (рис. 12) так же 6 вершин (6 четных). Например: от вершины ФЦ - Ш - Х - ЛА - С - ФЦ. Это доказывает, что объезд по вершинам возможен и граф 2 (рис. 12) также является эйлеровым циклом. Можно сделать обход и в другом направлении.
рис.12 рис.13
Используя карту и масштаб 1:7000, вычисляем длину маршрута 2, она приблизительно будет составлять 6780 метров.
Маршрут 3.
На графе (рис. 14) так же 6 вершин (6 четных). Например: от вершины ФЦ - Ш – С – ЛА - Х - ФЦ. Это доказывает, что объезд по вершинам возможен. Граф тоже является эйлеровым циклом. Можно сделать обход и в другом направлении.
рис.14 рис.15
Используя карту и масштаб 1:7000, вычисляем длину маршрута 3, она приблизительно будет составлять 6780 метров.
Маршрут 4.
На графе (рис. 16) 5 вершин (5 четных). Например: от вершины ФЦ - С - ЛА - Х - Ш - ФЦ. Это доказывает, что объезд по вершинам возможен. Граф тоже является эйлеровым циклом. Можно сделать обход и в другом направлении.
рис. 16 рис.17
Используя карту и масштаб 1:7000, вычисляем длину маршрута 4, она приблизительно будет составлять 6530 метров.
Маршрут 5.
На графе (рис. 18) так же 6 вершин (6 четных). Например: от вершины ФЦ - Ш - Х - ЛА - С - ФЦ. Это доказывает, что объезд по вершинам возможен. Граф также является Эйлеровым циклом. Можно сделать обход и в другом направлении.
рис.18 рис.19
Используя карту и масштаб 1:7000, вычисляем длину маршрута 5, она приблизительно будет составлять 6420 метров.
Чтобы быстрее объехать достопримечательности микрорайона «Родники» необходимо воспользоваться наиболее коротким 1 маршрутом.
Так же ещё можно поставить задачу. В которой будет требоваться найти примерное время экскурсии. Возьмём наш удобный маршрут, допустим, что машина едет около 40 км/ч. А так как у нас есть скорость и расстояние пути, то можно найти примерное время. Чтобы объехать весь маршрут, то нужно потратить 8 минут. Так как нужно будет ещё посмотреть на каждую достопримечательность, то это займёт ещё некоторое время. Поэтому можно предположить, что на каждую достопримечательность потратим примерно 15 минут.
5*15+8 = 83 мин = 1ч 23мин
Таким образом, экскурсия может составить около полутора часов.
3.Заключение
В этой проектно-исследовательской работе, я изучил понятия графа и масштаба, а также задачу про кёнигсбергские мосты и задачи про фигуры одним росчерком. И с помощью полученных знаний составил маршрут осмотра достопримечательностей микрорайона «Родники». Сделал макет «карта-граф микрорайона» для наглядного подсчета возможных вариантов обхода, для сравнения длин маршрутов (Приложение 1). Я узнал историю создания нашего микрорайона, а также, в честь кого были названы улицы и различные объекты (Приложение 2). Я считаю, что моя цель достигнута. В следующей работе постараюсь узнать о графах намного больше.
Вывод: теорию графов можно использовать для планирования и оптимизации маршрута гостей и туристов, осматривающих достопримечательности определенной местности, а также в работе риелторов. Использование теории графов позволяет значительно сократить время необходимое для движения между определенными точками.
4.Рефлексия
Делать данный проект было познавательно и увлекательно. У меня появилась возможность более детально изучить район, в котором мы живём. При приезде родственников и знакомых к нам в гости я смогу рассказать об истории появления нашего микрорайона, показать интересные места, рассказать о новосибирцах, чьими именами названы улицы, провести экскурсию по району. Название улиц помогает сохранить память о людях, которые защищали наши жизни в чрезвычайных ситуациях, а также отстаивали честь нашей Родины в военных действиях. Также, я по-новому смог взглянуть на возможности математики в нашей повседневной жизни.
4.Список источников информации
1. А.А. Гусев Математический кружок 7 класс, издательство Мнемозина, 2015 г., стр. 37-42
2. О.Б. Гладких, О.Н. Белых Основные понятия теории графов. Учебное пособие, 2008 г.
3. https://2gis.ru/novosibirsk/geo/141398913319008?m=82.942797%2C55.110781%2F15.23&ruler
4. http://www.decoder.ru/list/all/topic_117/
Приложение 1
Приложение 2
Краткие сведения по истории развития микрорайона «Родники»
Строительство микрорайона началось в 1990 году, а первый дом по адресу ул. Тюленина 1 был сдан в 1991 году. Но в конце 90-х годов 20 века из-за финансовых трудностей строительство было остановлено и продолжено по изменённому плану. На сегодняшний день микрорайон «Родники» состоит из улиц Гребенщикова, Краузе, Тюленина, Немыткина, Мясниковой, Свечникова, Кочубея и Красный проспект. Также на улице Тюленина построена школа №211 имени Л.И. Сидоренко, в которой мы учимся.
У лица Краузе и улица Гребенщикова носят имена пожарных. Служащие специализированной ПЧ по тушению крупных пожаров ФПС Новосибирской области: Вячеслав Федорович Краузе и Андрей Витальевич Гребенщиков. Они трагически погибли 24 октября 1999 года при ликвидации пожара в доме № 11 по улице 25 лет Октября.
Улица Тюленина названа в честь Героя Советского Союза Сергея Тюленина, члена штаба организации «Молодая гвардия», погибшего от рук фашистов 31 января 1943г. (1925-1943)
Улица Немыткина названа в честь Героя России, старшего лейтенанта Михаила Немыткина, героически погибшего в бою, во время войны в Чечне 18 апреля 1995г. (1970-1995)
Улица Мясниковой названа в честь Народной артистки СССР, солистки Новосибирского театра оперы и балета и почетного гражданина Новосибирска, знаменитой оперной певицы Лидии Владимировной Мясниковой. (1911-2005)
Улица Свечникова названа в честь директора Новосибирского завода химконцентратов Эрика Николаевича Свечникова, по инициативе которого было начато строительство микрорайонов «Снегири» и «Родники».
Улица Кочубея названа в честь казака Ивана Антоновича Кочубея в 1918 году, организовавшего партизанский отряд, который сражался с белогвардейцами. (1893-1919).
Этот памятник в виде зенитной установки «Катюша» поставлен в сквере на улице Свечникова.
Ш
кола №211 названа в честь Леонида Ивановича Сидоренко - депутата Законодательного собрания Новосибирской области, руководителя строительной компании «Энергомонтаж», построившая микрорайон «Родники».
Красный проспект (до 1920 года — Николаевский проспект) — центральная магистраль Новосибирска. Его протяжённость около семи километров. Начинается от набережной реки Оби в том месте, где реку пересекает Транссибирская железнодорожная магистраль, проходит по территории города с юга на север. В 2018 году открыли новую дорогу в микрорайоне Родники, которая является продолжением Красного проспекта.