XIV Международный конкурс научно-исследовательских и творческих работ учащихся
Старт в науке
Теория графов в городской среде. Создание маршрута по рекам Санкт-Петербурга и сборка прототипа беспилотного транспорта для его прохождения.
Автор работы награжден дипломом победителя II степени
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
Введение
Изучая окружающий нас мир, математика рассматривает не только его объекты, но связи между ними. Эти связи называют соответствиями или отношениями. Для построения соответствий и описания этих отношений можно использовать специальные рисунки – графы.
Граф, о котором я хочу рассказать, это не тот важный господин в шляпе с пером, острой шпагой, красивым замком и верными слугами. Наш граф состоит из точек и линий. Графы используются в физике, химии, электронике, строительстве, медицине и многих других науках. В виде графов можно представить карту железных дорог, схему метро, молекулы и даже отношения между людьми [2].
Чтобы решить какую-то задачу, часто бывает полезно нарисовать картинку по условию. Я тоже люблю так решать задачи: рисую на бумаге точки, которые изображают интересующие меня объекты, и соединяю эти точки линиями, которые показывают отношения между ними. Делаю это, чтобы по картинке было легче понять задачу и представить ход её решения.
Интересно, можно ли составить экскурсионный маршрут по рекам Санкт-Петербурга, чтобы каждый участок проходить по одному разу.
Гипотезы:
Карту рек можно представить в виде схемы графа;
Графы можно использовать для решения разных задач.
Цель проекта: изучение основных понятий теории графов, построение графа обхода маршрута по рекам Санкт-Петербурга и сборка прототипа беспилотного транспортного средства.
Объект исследования: теория графов.
Предмет исследования: маршрут обхода графа.
В ходе проекта я планирую решить задачи:
Изучить основные понятия теории графов;
Разобрать примеры задач с графами;
Рассмотреть варианты применения теории графов в городской среде;
Построить граф обхода маршрута экскурсии по рекам;
Собрать прототип беспилотного транспортного средства, движущегося по части маршрута.
Для достижения цели буду использовать теоретические методы, такие как сбор материала и анализ предметной области, и экспериментальный, - придумаю задачу по обходу маршрута, решу её с помощью теории графов и соберу прототип экологического беспилотного транспортного средства, движущегося по одному любому ребру в графе.
ГЛАВА 1. Основные понятия теории графов.
Граф, вершина, ребро и степень вершины.
Г раф – математический объект, состоит из точек и линий, соединяющих некоторые пары точек. Эти точки называются вершинами, а линии называются рёбрами. Важно, что в понятии графа, говориться не о прямых отрезках, а о любых линиях [1]. Эти линии могут быть извилистыми или кривыми. Две вершины, которые соединены ребром, называются смежными. Две вершины могут быть соединены несколькими линиями. Если допустить, что две вершины соединены именно отрезками, то изобразить несколько соединений для двух вершин было бы невозможно, поскольку на рисунке такие отрезки совпадали бы.
Рисунок 1. Рисунок 2.
Путь – последовательность вершин, в которой каждая вершина соединена со следующей вершиной ребром [6]. На рисунке 1 красными стрелками показан путь от вершины 1 к вершине 3 через вершину 4. Ориентированным (или орграфом) называется граф, в котором все ребра имеют направление, указывающее, какая из вершин ребра является начальной, а какая – конечной (см. рисунок 1). Неориентированный граф – граф, в котором у ребер нет направлений (см. рисунок 2). Количество линий (рёбер), выходящих из точки (вершины графа) называется степенью связанности вершины или степенью вершины. Вершина называется чётной, если степень вершины у неё чётная, и нечётной, если степень у неё нечётная. На рисунке 3 показана нечётная вершина со степенью связанности 3, на рисунке 4 – чётная вершина со степенью связанности 4.
Рисунок 3. Рисунок 4.
С дворянским титулом «граф» наш граф связывает общее древнее происхождение от греческого слова «графио» - пишу [5]. И он имеет славных родственников: география – землеописание, биография – жизнеописание, картография – картоописание, графит – стержень для письма, автограф – собственноручная подпись, фотография – запись изображения и так далее.
Эйлеров путь в графе
На реке Прегель расположен город Калининград (бывший Кенигсберг). Река омывает два острова, которые соединены между собой и с берегами мостами. Конечно, старых мостов сейчас уже нет и память о них осталась только на карте города. Однажды один житель Кенигсберга спросил у своего знакомого, можно ли пройти по всем мостам, побывать на каждом только один раз и вернуться к тому месту откуда началась прогулка.
Эта загадка заинтересовала многих горожан, но разгадать её никто не смог. Вопрос вызвал заинтересованность ученых многих стран. Решить задачу удалось математику Леонарду Эйлеру. Для этого он превратил карту в граф. Вершинами этого графа стала суша, а ребрами стали мосты (см. рисунок 5).
Рисунок 5.
При решении задачи про мосты Кенигсберга Эйлеру удалось сформулировать свойства графов [5]:
Нарисовать граф, начав движение с одной вершины и окончив в той же вершине, дважды не проводя по одному и тому же ребру, и не отрывая карандаша от бумаги возможно в том случае, если все вершины графа чётные.
Если есть граф с двумя нечётными вершинами, то его вершины тоже можно соединить одним росчерком. Для этого нужно начать с одной вершины с нечётной степенью, а закончить на другой второй нечётной вершине.
Если есть граф с числом нечётных вершин больше двух, то такой граф невозможно начертить одним росчерком.
Если применять эти свойства к задаче о мостах, то можно увидеть, что все вершины исследуемого графа нечётные, значит, этот граф нельзя соединить одним росчерком, т.е. невозможно пройти по всем мостам один раз и закончить путь в том месте, где он был начат.
Если граф имеет путь, содержащий все рёбра графа по одному разу, то такой путь называется Эйлеровым путем в графе.
Задачи по теории графов
Теперь предлагаю разобрать задачи, которую я составила для своих однокласников. Для решения нарисуем подходящую картинку графа.
Задача. Встретились Винни-Пух, Пятачок, Кролик и Иа-Иа. При встрече каждый из друзей пожал лапу каждому. Сколько лапопожатий было сделано?
Решение. Нарисуем подходящий граф (см. рисунок 6). Четыре вершины – четыре друга Винни-Пух, Пятачок, Кролик и Иа-Иа. Лапопожатия – это ребра этого графа. У каждой вершины в этом графе степень равна – 3.
Рисунок 6.
Аккуратно подсчитаем количество линий-лапопожатий. Их шесть.
Из этой задачи мы можем сделать несложное, но полезное утверждение. Сумма степеней всех вершин графа равна удвоенному числу рёбер графа. Давайте разберем, почему это так. Одним концом ребро выходит из одной вершины, другим – из другого. Значит вклад в общее число степеней от одного ребра равен двум – из-за двух концов. Таким образом, сумма степеней вершин – это количество концов у ребер, а в их в два раза больше, чем самих рёбер. В нашем графе шесть рёбер и сумма степеней вершин тогда равна 12 = 3+3+3+3 или 12 = 6*2. Как следствие можно сделать наблюдение, что сумма степеней всех вершин графа – чётное число. Эту и другие занимательные задачи для моих одноклассников можно увидеть в ПРИЛОЖЕНИИ 1.
Следующая задача поможет нам понять можно ли нарисовать фигуру, не отрывая карандаша от бумаги, используя свойства графа, описанные Эйлером.
Задача на нахождение Эйлерова пути. Попробуйте нарисовать закрытый конверт, не отрывая карандаша от бумаги (см. рисунок 7).
Рисунок 7.
Решение. Если мы в местах пересечения линий обозначим вершины графа (а их будет 5), то мы увидим, что в данном графе четыре вершины с нечётной степенью. Значит такой граф нельзя нарисовать одним росчерком пера.
К ак исправить ситуацию? Вспомним, что если в графе будет не более двух нечётных вершин, то его вершины тоже можно соединить одним росчерком. Для этого нужно начать с одной нечётной вершины, а закончить на второй нечётной вершине. Тогда, если мы добавим еще одну вершину и от неё направим по одному ребру к двум верхним нечётным вершинам, то степень их изменится, и они станут чётными.
Рисунок 8
Теперь в графе будет только две нечётные вершины – нижние. И значит его можно нарисовать, не отрывая карандаша от бумаги. Вид графа представлен на рисунке 8.
ГЛАВА 2. ПРАКТИЧЕСКАЯ ЧАСТЬ. Теория графов в городской среде.
Партнёры проекта
В этом проекте у меня появилась новая задача – взаимодействие с партнёрами. В качестве партнёров, мне повезло работать с настоящими экспертами, которые знают, как применять теорию графов на практике:
Васильев Алексей, директор департамента по коммуникациям с корпоративными заказчиками, ВКОНТАКТЕ Групп;
Кулинич Ирина, функциональный архитектор, руководитель группы аналитиков, компания OZON Holdings PLC;
Музыченко Яна, заместитель директора физико-технического мегафакультета, доцент, ведущий инженер, университет ИТМО.
Анализ социального взаимодействия в классе 3.7 ИТШ 777
Алексей Васильев рассказал, что графы могут применяться для анализа социального взаимодействия внутри какой-либо группы, обнаружения неявных связей, составления расписания и так далее. Механизм теории графов активно используют в социальных сетях, например, в такой как ВКОНТАКТЕ.
Чтобы проверить это на практике, я провела опрос среди учеников класса (см. рисунок 9) и обработала его результаты с помощью теории графов. Каждому ученику нашего класса я поставила в соответствие вершину графа, ребро графа показывает взаимодействие между детьми.
С амыми популярными детьми в классе по результатам опроса являются:
Пивоваров Даниил (среди
мальчиков) – степень вершины 12;
Гусева Александра (среди
девочек) – степень вершины 18.
Рисунок 9. Пример анкеты.
Эти данные можно использовать для обнаружения лидеров общественных мнений, для выбора детей в совет класса или назначения старосты класса, для выстраивания системы оповещения внутри класса. Фотоотчет процесса анкетирования приведен в ПРИЛОЖЕНИИ 2.
Сделаем вывод: представление информации в виде графа является простым моделированием, позволяет быстро анализировать и делать выводы.
Варианты использования графов в городской среде.
Ирина Кулинич рассказала, что понятие центра графа появилось в связи с задачами оптимального размещения пунктов массового обслуживания, таких как больницы, школы, банки, пожарные части, почтамты и т.п., когда важно минимизировать наибольшее расстояние от любой точки населенного пункта до ближайшего пункта обслуживания.
Также компании OZON ежедневно планирует тысячи доставок товаров по пунктам выдачи и по адресам покупателей. Для решения этой задачи используется теория графов и алгоритм для нахождения кратчайшего пути.
Рассмотрим, например, задачу организации автомобильного движения в городе. Схему организации движения автотранспорта представит ориентированный граф, если вершинами графа считать перекрестки дорог, а его ребрам сопоставить дороги, соединяющим перекрестки. Две вершины может соединять одно ребро, если движение по дороге одностороннее, или два ребра, если движение двустороннее [7]. Построенный таким образом простой орграф может быть полезен, например, при составлении оптимальных маршрутов проезда по городу. Кроме того, можно строить развлекательные маршруты по городу для того, чтобы обойти все достопримечательности по одному разу или для того, чтобы определить сколько существует доступных маршрутов (см. задачу из ПРИЛОЖЕНИЯ 1).
Сделаем вывод: графы имеют большое практическое применение в городской среде.
Составление и анализ графа маршрута по рекам Санкт-Петербурга.
Я живу в Санкт-Петербурге и решила придумать такую экскурсию по водным путям города, чтобы на его достопримечательности, расположенные на набережных, не пришлось смотреть дважды. А чтобы не вредить окружающей среде и не мешать жителям города, моя экскурсия будет водной – на электрической лодке! Эта экскурсия необычная, так как с воды город выглядит не так, как когда по нему гуляешь пешком или ездишь на автобусе.
Чтобы составить маршрут я взяла карту города и придумала, будто реки – это ребра графа, а вершины – это точки, в которых реки соединяются, и лодка будет менять направление движения (см. рисунок 10). Я знаю, чтобы на маршруте не было повторений, нужно построить такой граф, в котором число нечётных вершин было не больше двух. Многие реки города – это протоки, которые вытекают из Невы и впадают в Неву. Я поняла, что в этих местах вершины графа ставить нельзя, потому что они все получаются нечётные и тогда их будет слишком много.
Рисунок 10. Изображение графа с маршрутом по рекам Санкт-Петербурга
Как я рассуждала при построении графа:
Вершины – это места соединения рек;
Ребра – крупные реки;
После построения графа анализировала число нечётных вершин;
Далее или добавляла рёбра и вершины или, наоборот, удаляла лишние нечётные вершины и смежные ребра.
Итоговый граф маршрута экскурсии представлен на рисунке 11, он получился из графа, изображенного на рисунке 10 путем удаления двух нечётных вершин (обведены красным). Итоговый граф содержит две нечётные вершины со степенями 3 и 5 соответственно, и четыре чётные вершины.
Рисунок 11. Изображение графа с маршрутом экскурсии по рекам Санкт-Петербурга, содержащего Эйлеров путь.
Для итоговой проверки своего графа, я пользовалась сайтом https://graphonline.ru/. На рисунке 12 представлен итоговый граф, отрисованный в программе. Он нарисован по-другому, хотя оба графа устроены одинаково. Такие графы называются изоморфными [4].
Рисунок 12. Изображение окончательного варианта графа на Graph Online.
Сделаем вывод: построенный граф содержит Эйлеров путь [8]. Представление карты рек в виде графа позволило построить маршрут экскурсии по рекам Санкт-Петербурга и обойти все рёбра без повторения.
ГЛАВА 3. Прототип беспилотного экологического транспорта
Для экскурсии по рекам Санкт-Петербурга я придумала использовать автономный экологически чистый транспорт – лодку на электродвигателе, которая сама, без капитана и рулевого, будет перевозить туристов по маршруту в виде графа. Такая лодка не загрязняет окружающую среду, не производит парниковых газов, минимизирует риск разлива жидкого топлива на поверхность реки и уровень шума, а также сохраняет возможность социального дистанцирования во время пандемии.
Чтобы убедиться, что такая лодка сможет двигаться сама, я решила построить прототип беспилотного транспортного средства и проверить, сможет ли он самостоятельно ориентироваться в пространстве и не сбиться с маршрута.
Основные детали прототипа
Я люблю собирать из LEGO и у нас дома есть конструктор LEGO Mindstorms, поэтому прототип я собирала из него.
Основные детали – тележка с колесами и двумя электрическими моторами, два понижающих редуктора, датчик движения по линии LineLeader-v2, микрокомпьютер EV3 для обработки сигналов с датчика и управления моторами. Внешний вид основных деталей, узлов и самого прототипа представлен в ПРИЛОЖЕНИИ 3.
Описание способа ориентации, примененного в прототипе
Для ориентации в пространстве и для движения прототипа по маршруту использован сканирующий датчик. Мой прототип полностью автономен и способен самостоятельно дистанционно и бесконтактно определять нужное направление движения. Это простой и надежный способ навигации, не требующий устройства каких-либо направляющих конструкций и не зависящий от доступности сотовой и спутниковой связи.
Созданный прототип движется по линии, используя сигналы с установленного на нем датчика движения по линии LineLeader-v2. Этот датчик содержит 8 сенсоров, каждый из которых умеет измерять яркость отраженного света и так различать темную линию на светлом фоне (или наоборот). Для точного измерения датчик следует установить под прямым углом к поверхности на расстоянии 0,5 см.
П ри движении вдоль нанесенной на поверхность линии датчик с помощью сенсоров определяет, в каком направлении линия отклоняется, и передает микрокомпьютеру EV3 команды для управления моторами и корректировки движения (см. рисунок 13). Сведения о направлении отклонения поступают с сенсоров, часть которых «теряют» отклонившуюся в сторону линию, зато другие ее обнаруживают. Рисунок 13. Принцип действия датчика
Этапы создания прототипа
1 ЭТАП – сборка из LEGO тележки с двумя электрическими сервомоторами, которые независимо вращают два из четырех колес.
2 ЭТАП – крепление к тележке датчика движения по линии LineLeader-v2.
3 ЭТАП – подключение моторов и датчика к микрокомпьютеру EV3, крепление микрокомпьютера на тележке.
4 ЭТАП – калибровка датчика, чтобы он умел различать цвет линии и цвет остальной поверхности.
5 ЭТАП – проверка движения прототипа по маршруту и внесение изменений в конструкцию тележки.
Испытание прототипа
Для настройки работы микрокомпьютера EV3 используется программное обеспечение LEGO Mindstorms EV3 Home Edition. Датчик движения по линии LineLeader-v2 может быть добавлен в эту программу и для него уже написаны алгоритмы калибровки и следования по линии (см. рисунок 14).
Рисунок 14. Фрагмент существующей программы следования по линии
Поэтому после сборки прототипа нужно загрузить эти две программы в память микрокомпьютера и по очереди их выполнить:
Запустить программу калибровки, дождаться звукового сигнала и текстового приглашения к измерению фона. Затем установить датчик над фоновой поверхностью и нажать управляющую кнопку микрокомпьютера. После повторного звукового сигнала и текстового приглашения к измерению цвета линии надо разместить датчик над линией и снова нажать управляющую кнопку микрокомпьютера.
Установить прототип поверх линии, указывающей маршрут движения, и запустить программу движения. Прототип начнет двигаться вдоль линии, повторяя ее отклонения.
Рисунок 15. Фотографии прототипа в ходе калибровки и проведения испытаний
В ходе испытаний прототипа подтверждено, что он способен автономно двигаться по определенному маршруту, считывая его дистанционно с использованием датчиков (см. рисунок 15).
Мой эксперт по этой части работы, Музыченко Яна, подтверждает, что датчики, основанные на контроле физических параметров среды, остаются одним из наиболее достоверных источников информации для систем искусственного интеллекта.
Сделаем вывод: принцип навигации, учитывающий данные с большего числа датчиков и в большей степени обеспечивающий безопасность движения, может применяться и для средних, и для крупных беспилотных транспортных средств, например, для беспилотного экологического транспорта для проведения экскурсий.
Ограничения конструкции прототипа
При испытании первой конструкции прототипа выяснилось, что скорость движения прототипа настолько высока, что сигналы с датчика движения по линии не успевают обрабатываться микрокомпьютером. Прототип ехал слишком быстро и не успевал поворачивать вслед за линией. Решение подсказал мой брат, занимающийся в кружке робототехники, - во второй конструкции мы установили редуктор. Теперь при движении прототип успевает уследить за поворотом линии, но движется медленнее.
Перспективы развития прототипа
Сейчас прототип демонстрирует возможность движения только по одному любому ребру. Обход всего маршрута не предусматривается. Дальнейшее развитие прототипа подразумевает создание алгоритма и разработка программы для движения по Эйлеровому пути в графе.
Заключение
Многие объекты, возникающие в жизни человека, и связи между ними могут быть представлены в виде рисунка – смоделированы при помощи графа.
С помощью проекта удалось познакомится с начальными понятиями теории графов, с различными приёмами доказательств, понятиями необходимых и достаточных условий, построить реальные модели.
По результатам проекта, я сделала такие выводы:
Граф – это замечательный инструмент моделирования. С помощью графов можно научится сводить решение задач, связанных с отношениями и соответствиями, к построению и анализу простейших графовых моделей.
Графы имеют очень широкое применение в городской среде: с их помощью выбирают наиболее выгодное расположение важных зданий, графами представляют схемы метро, рассчитывают оптимальный или кратчайший маршрут.
Из LEGO можно делать простые беспилотные прототипы сложных устройств. Я думаю, что такое конструирование в форме познавательной игры хороший способ развития технического и конструкторского мышления.
Все важные изобретения необходимо делать, заботясь об окружающей среде. Ответственность за экологию несёт каждый.
Я подтвердила гипотезы и выполнила задачи. Мне понравилось, что в своей работе получилось изучить тему, а потом применить полученные знания на практике: построить граф маршрута, проанализировать его и провести эксперимент с прототипом экологического транспорта.
Литература
Математика, которая нравится. А.П. Бегун, К.Л. Трошин
Издательство «РАЗ-ДВА-ТРИ», 2020.
Незнайка в стране графов. О.И. Мельников, ЛЕНАНД, 2020.
Теория графов. https://foxford.ru/wiki/informatika/teoriya-grafov
Теория графов. Основные понятия и виды графов.
https://skysmart.ru/articles/mathematic/osnovnye-ponyatiya-teorii-grafov
Графы и области их применения. https://school-science.ru/4/7/33615
10 анимированных алгоритмов на графах.
https://techrocks.ru/2020/09/15/10-graph-algorithms/
Лекция 10. Теория графов. http://vuz.exponenta.ru/pdf/L10.html
Программирование задач на графах, Эйлеровы и Гамильтоновы пути.
http://catalog.studentochka.ru/60043.html
ПРИЛОЖЕНИЕ 1. Математический практикум. Занимательные задачи по теории графов.
1 . ЗАДАЧА О РУКОПОЖАТИЯХ: Встретились Винни-Пух, Пятачок, Кролик и Иа-Иа. При встрече каждый из друзей пожал лапу каждому. Сколько лапопожатий было сделано?
2. ЗАДАЧА О НАХОЖДЕНИИ МАРШРУТОВ: Винни-Пух любит ходить в гости к своему другу Пятачку, любимые тропинки Винни-Пуха показаны на карте. Сколько существует различных путей от дома Винни-Пуха до дома Пятачка?
3. КАКУЮ ФИГУРУ НЕЛЬЗЯ НАРИСОВАТЬ, НЕ ОТРЫВАЯ РУКИ ОТ БУМАГИ И НЕ ПРОВОДЯ ПО ЛИНИИ ДВАЖДЫ? И ПОЧЕМУ?
А) Б) В)
СОВЕТЫ К ЗАДАЧАМ
Нарисуйте граф лапопожатий. Вершины это 4 друга.
Нарисуйте граф дорог. Вершины этого графа домики, памятные места и перекрестки, рёбра - тропинки, соединяющие эти вершины.
Представьте фигуры в виде графов и посчитайте количество чётных и нечётных вершин.
РЕШЕНИЕ ЗАДАЧ
Решение. Нарисуем подходящий граф. Четыре вершины – четыре друга Винни-Пух, Пятачок, Кролик и Иа-Иа. Лапопожатия – это ребра этого графа. Соединим каждую вершину с каждой и аккуратно подсчитаем количество линий-лапопожатий. Их шесть.
Р ешение. Представим граф в виде дерева [3], которое растет вниз. Начнем с вершины, которая соответствует домику Винни-Пуха. От домика Пуха у нас три возможности продолжить путь: через домик Иа-Иа, Дуб и Опушку. От домика Иа у нас две возможности продолжить путь: через домик Совы и домик Кролика. От них приходим в домик Пятачка. И так далее. Используя построенное дерево, можно найти все маршруты от Пуха до Пятачка. Наше дерево имеет семь листьев. Значит возможны семь различных маршрутов.
Решение. Фигуру А можно нарисовать, так как 2 вершины нечётные. Фигуру Б можно нарисовать, так как все вершины чётные. Фигуру В нельзя нарисовать, так как три вершины нечётные.
ПРИЛОЖЕНИЕ 2. Проведение опроса для анализа социального взаимодействия в классе 3.7. ИТШ 777
Рисунок 1. Проведение тестирования в классе
ПРИЛОЖЕНИЕ 3. Прототип беспилотного экологического транспорта
Рисунок 1. Внешний вид прототипа
Рисунок 2. Внешний вид тележки со снятым микрокомпьютером
Рисунок 3. Датчик движения по линии и детали его крепления к тележке (вид снизу, со стороны сенсоров)
Рисунок 4. Понижающий редуктор