Велотранспортная сеть города Перми – взгляд на практическое применение теории графов

• Авторы
• Руководители
• Файлы работы
• Наградные документы

Сажин А.Е. 1

---

1МАОУ "СОШ № 132" г Перми

Евдокимова С.В. 1

---

1МАОУ "СОШ № 132" г. Перми

Работа в формате PDF

1.4 MB

Автор работы награжден дипломом победителя II степени

Диплом школьникаСвидетельство руководителя

Введение

Наш мир полон не только букв и цифр, но и самых разнообразных изображений. Это и картины, и фотографии, и произведения искусств различных стилей, а также многочисленные схемы. Например, схемы движения транспорта – это всего лишь линии с точками, рядом с которыми подписаны названия остановок. Подобные схемы из точек и линий называются графами. [CITATION Мирматематики \l 1049 ]

Графы часто представляют собой прекрасные примеры математических моделей. Несмотря на простоту графов, с их помощью можно описывать и изучать интересные реальные ситуации.
Графы – пример использования математики в повседневной жизни. Они помогают увидеть, что математика постоянно присутствует в окружающем нас мире. [CITATION Мирматематики \l 1049 ]

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

Цель моей исследовательской работы

Исследование велотранспортной сети города Перми с точки зрения теории графов.

Задачи моей исследовательской работы

Познакомиться с основными понятиями теории графов.

Узнать, где в повседневной жизни используются графы.

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

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

Знакомство с графами

Его величество граф

Графом называется конечное множество точек, некоторые их которых соединены линиями. Точки называются вершинами графа, а соединяющие линии – рёбрами. Каждое ребро соединяет ровно две вершины. [CITATION Гуровиц \l 1049 ]

Рис. 1 Примеры графов

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

Вершины, которые соединены ребром, называются его концами. Если вершина является концом ребра, то говорят, что ребро выходит из вершины. Число ребер, выходящих из вершины, называется степенью вершины. Вершина степени 0 называется изолированной, вершина степени 1 – висячей. [CITATION занимательныхзадачах \l 1049 ]

Лемма о рукопожатиях. Сумма степеней вершин графа равна удвоенному числу ребер.

Следствие. В любом графе число вершин нечетной степени четное.

Граф, у которого каждая пара вершин соединена ребром, называется полным графом. Противоположностью полному графу является пустой граф. Граф, который не имеет ни одного ребра, называется пустым. [CITATION занимательныхзадачах \l 1049 ]

На рисунке представлены примеры полного и пустого графов.

Рис. 2 Полный и пустой граф

Граф называется связным, если от любой его вершины можно по ребрам перейти к любой другой. В противном случае граф называется несвязным. Говорят, что две вершины графа принадлежат одной компоненте, если от одной из них до другой можно перейти по ребрам графа. Каждая компонента является связным графом. [CITATION занимательныхзадачах \l 1049 ]

Граф, вершины которого можно разбить на два множества таким образом, что каждое ребро будет соединять вершины из разных множеств, называется двудольным. [CITATION занимательныхзадачах \l 1049 ]

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

Рис. 3 Полные двудольные графы

Одинаковые графические схемы могут описывать совершенно различные задачи, изучение этих схем позволяет найти решение для множества задач одновременно. Точки графа могут соединяться линиями произвольной формы. Главное – отобразить отношения, связи и взаимодействия, а не построить точную сеть линий и точек. [CITATION Мирматематики \l 1049 ]

Три графа, представленные на рисунке, - это три разных представления одного и того же графа.

Рис. 4 Разные представления одного графа

Приведем еще несколько определений, которые нам потребуются в исследовании.

Маршрутом в графе называется такая последовательность чередующихся вершин и ребер графа, что каждое ребро соединяет вершины последовательности, между которыми оно находится. Маршрут, в котором все ребра различные, называется цепью. [CITATION занимательныхзадачах \l 1049 ]

Циклы – это очень простые маршруты, проходящие через все вершины, начальная и конечная точка которых совпадают. [CITATION Мирматематики \l 1049 ]

Кёнигсбергские мосты

Теория графов появилась благодаря одной занимательной задаче, которую решил Леонард Эйлер. История гласит, что в 1736 году великий математик остановился в Кёнигсберге (в настоящее время Калининград). Город был разделен рекой на части, которые были соединены мостами. [CITATION Мирматематики \l 1049 ]

Рис. 5 Кёнигсбергские мосты

Задача состояла в том, чтобы ответить на вопрос, можно ли пройтись по всем кенигсбергским мостам так, чтобы побывать на каждом из них один и только один раз. Эйлер доказал, что задача неразрешима, сведя карту к графу, на котором участки суши изображались точками, а мосты - линиями. [CITATION Барр \l 1049 ]

Рис. 6 Кёнигсбергские мосты

Эйлер обнаружил общий закон, справедливый для всех таких графов. Закон состоит в следующем. В каждой вершине графа сходится несколько линий (в нашем случае - мостов). Если число таких линий нечетно, то вершина называется нечетной, если четно, то она называется четной. Эйлеру удалось доказать, что у графа может быть лишь четное число нечетных вершин (либо их вовсе нет). Обход, при котором каждая линия проходилась бы только один раз, можно совершить лишь в случае, когда либо нет ни одной нечетной вершины, либо когда таких вершин две. В случае задачи о кенигсбергских мостах граф содержал 4 нечетные вершины, так что обход был невозможен. [CITATION Барр \l 1049 ]

При наличии двух нечетных вершин обход следует начинать в одной из них, а заканчивать в другой. Если у графа нет нечетных вершин, то обход можно начинать с любой вершины и в ней же заканчивать. [CITATION Простаянаукадлядетей \l 1049 ]

Простая разновидность данной ситуации встречается в задачах, где нужно совершить обход «одним росчерком пера», то есть не отрывая ручки от бумаги и не проводя дважды один и тот же отрезок. [CITATION Простаянаукадлядетей \l 1049 ]

Графы вокруг нас

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

Социальный граф

Социальный граф – это граф взаимоотношений между различными людьми, организациями или группами. Один из вариантов социального графа – это «граф знакомств» или «граф друзей». В компании людей знакомство или дружба – это взаимное свойство. Поэтому можно считать, чтоб люди – это вершины графа, а дружба между ними – это ребро.

В качестве примера я нарисовал свой граф знакомств.

Рис. 8 Мой граф знакомств

В 1967 году Стэнли Милгрэм провел эксперимент, подтвердивший концепцию «маленького мира». Несколько человек попросили передать письмо определенным людям по цепочке через своих знакомых. В большинстве случаев сообщение удалось передать получателю за шесть шагов. Этот эксперимент проводился неоднократно, и всякий раз число звеньев в подобных цепочках оказывалось очень малым (пять, шесть, восемь). Так возникла теория «шести рукопожатий». [CITATION Мирматематики \l 1049 ]

Социальные графы широко применяются в наши дни в SMM. SMM – это продвижение товаров и услуг в социальных сетях.

Транспортный граф

Один из самых распространенных графов, с которым мы сталкиваемся в повседневной жизни – это транспортный граф. Это и схемы метро, и карты железнодорожных дорог, и схемы автобусных маршрутов. Ребрами в таких графах являются улицы или дороги, вершинами – остановки или населенные пункты.

Графы помогают наглядно представить схемы общественного транспорта, что облегчает планирование поездок. Графы, изображающие транспортные сети, должны быть очень четкими, чтобы на них можно было увидеть не только возможные маршруты, но и переходы между станциями. [CITATION Мирматематики \l 1049 ]

Рис. 9 Схема метро Санкт-Петербурга

Турнирный граф

Для описания всевозможных соревнований используются турнирные графы. Например, футбольные соревнования шести команд можно наглядно представить в виде графа. Команды можно обозначить буквами A, B, C, D, E, F. Через некоторое время после начала соревнований окажется, что некоторые из команд уже сыграли друг с другом [CITATION Оре15 \l 1049 ]

A с C, D, F

B с C, E, F

C с A, B

D с A, E, F

E с B, D, F

F с A, B, D, E

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

Рис. 10 Турнирный граф

Каждую совокупность игр любого турнира можно представить соответствующим графом.[CITATION Оре15 \l 1049 ]

Генеалогические деревья

Дерево – это очень простой граф, все вершины которого соединены так, что отсутствуют циклы. В дереве можно проложить маршрут между любыми двумя вершинами. [CITATION Мирматематики \l 1049 ]

Рис. 12 Граф-дерево

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

В прошлом генеалогические деревья изображались в виде настоящих деревьев с ветвями и листьями. Сегодня, благодаря использованию графов, генеалогические деревья стали более понятными. [CITATION Мирматематики \l 1049 ]

Рис. 13 Моё генеалогическое древо

Велотранспортная сеть в теории графов

Велосипед – элемент современной транспортной сети

Развитие велодвижения стоит на повестке дня во многих городах нашей страны. Возможность езды на велосипеде – это преимущество для городов. В Европе велотранспортная инфраструктура хорошо развита, в нашей же стране она еще только создается.

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

В современном мире велотранспорт включается в схемы транспортного планирования и даже в общую стратегию развития города.

Определяют ряд основных требований к велосипедной инфраструктуре:

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

Прямолинейность и непрерывность. Велосипедист должен иметь возможность доехать до точки назначения по наиболее прямому и короткому пути. Это требование делает велосипед конкурентоспособным видом транспорта на небольших дистанциях.

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

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

Удобство. Удобные велодорожки – те, которые позволяют ехать, не напрягаясь и получать удовольствие от езды. Это в первую очередь касается качества дорожного покрытия и состояния дорог. [CITATION Велотрансп \l 1049 ]

Велотранспортная сеть

Велотранспортная сеть – это набор взаимосвязанных, безопасных и прямолинейных веломаршрутов, покрывающий всю заданную территорию или город. Качественный веломаршрут – это непрерывный путь, соответствующий указанным выше критериям: безопасный, прямолинейный, входящий в связную сеть, удобный и привлекательный. [CITATION Велотрансп \l 1049 ]

Связность сети – одно из основных и очевидных требований к велотранспортной сети. Без связности не существует сети как таковой, есть лишь набор отдельных маршрутов. Чем больше маршрутов соединены между собой и чем больше у велосипедистов выбор возможных вариантов, тем лучше сеть. Для велосипедистов связность – ощутимое свойство: она определяет границы, которых они могут достичь, двигаясь по маршруту. [CITATION Велотрансп \l 1049 ]

Для примера – карта велодорожек Лондона представляет собой связную сеть из маршрутов, общей протяженностью 220 км.

Рис. 15 Карта велодорожек Лондона

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

Пермский велотранспортный граф

Первые велосипедные дорожки в городе Перми появились в 2009 году. Но и на сегодняшний день, согласно Приложению к Программе комплексного развития транспортной инфраструктуры города Перми на 2020-2022 годы, велодорожек в нашем городе насчитывается всего 14.

Перечень существующих велодорожек (велопешеходных дорожек,

велополос) на автомобильных дорогах города Перми

Попробуем представить велодорожки города Перми в виде графа. Для этого обозначим границы каждой из 14 дорожек буквами A, B, C т.д. – это будут вершины графа. Для того чтобы правильно обозначить границы дорожек, воспользуемся картой, так как некоторые велодорожки начинаются на одной улице, но в разных местах (например, 12 и 13 велодорожки). Значит, их границы нужно обозначать разными буквами – вершинами графа. А некоторые велодорожки пересекаются, но по таблице этого не видно (например, дорожки 2 и 12, дорожки 3 и 9). Если две дорожки пересекаются не на границах, а в середине маршрута, то точки пересечения также обозначим буквами. Тогда такая велодорожка будет представлять маршрут из двух рёбер нашего транспортного графа.

Карту велодорожек города Перми можно найти на городском портале «Управляем вместе». [CITATION Управляемвместе \l 1049 ]

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

Рис. 17 Фрагмент карты велодорожек г. Перми

В результате анализа карты можно составить следующую таблицу:

Тогда транспортный граф, изображающий сеть велодорожек города Перми, можно представить, например, так:

Рис. 19 Транспортный граф велодорожной сети города Перми

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

21 вершина графа имеют степень 1. Вершина F, соответствующая ул. Ленина) имеет степень 3, вершина Y (пересечение ул. Мира и Советской Армии) имеет степень 2, вершина V (пересечение ул. Чернышевского и Южной дамбы) имеет степень 2, вершина C (ул. Макаренко) имеет степень 4.

Пять велодорожек представляют собой обособленные маршруты, соединяющие две точки – начало и конец велодорожки. Велодорожки нашего города не образуют целостную сеть и из них нельзя построить непрерывный маршрут. Посмотрим на карту и убедимся, что это действительно так [CITATION Управляемвместе \l 1049 ]:

Рис. 20 Карта велодорожек г Перми

По карте видно, что даже центральные районы нашего города не соединены между собой велодорожками.

Анализируя граф велодорожек города Перми, можно сделать вывод, что пермская велотранспортная сеть не удовлетворяет основному требованию – связности.

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

Велодорожка № 1 (ПНИТИ – ул. Хлебозаводская), велодорожка № 13 (Бульвар Гагарина – ул. Глуховской), велодорожки № 5 и № 7 (ул. Мира)

Велодорожка №1 проходит по улице Героев Хасана от ПНИТИ до ул. Хлебозаводской. Мне, как школьнику, показалась совершенно не востребованной, так как она проходит мимо различных промышленных предприятий и офисов. Но для взрослых работающих людей она была бы удобна, если бы была соединена с какими-нибудь другими маршрутами.

Я проанализировал карту, сопоставил ее со своим графом велодорожек и понял, что было бы удобно добавить еще две велодорожки: по ул. Героев Хасана от ПНИТИ (вершина А моего графа) до ул. Чкалова (назовем эту вершину АА), а потом по ул. Чкалова от ул. Героев Хасана (вершина АА) до бульвара Гагарина, где находится вершина S моего графа.

Также мне показалось удобным соединить велодорожку № 1 с велодорожкой № 5, которая проходит по улице Мира от ул. Карпинского до ул. Советской Армии. Если считать, что вершина АА и ребро B-AA у нас уже есть, то достаточно соединить велодорожкой (ребром) вершины графа AA и X (соответствует точке на ул. Мира, пересечение с ул. Карпинского). А так как у нас велодорожка № 5 соединена с велодорожкой №7, то получится, что мы связали три компоненты нашего графа в одну, тем самым увеличив количество возможных веломаршрутов, проходящих через вершины нашего графа. На рисунке новые велодорожки я обозначил красным цветом.

Рис. 21 Велодорожки № 1, 13, 5, 7, объединенные в одну компоненту связности новыми велодорожками

Велодорожка № 6 (ул. Куфонина – ул. Зои Космодемьянской), велодорожка № 14 (ул. Свиязева – ул. Д. Давыдова)

Велодорожка № 6 проходит по проспекту Парковый от ул. Куфонина до ул. Зои Космодемьянской. Это оказался очень востребованный маршрут, по которому перемещаются и школьники, и студенты, и взрослые люди всех возрастов. Эта велодорожка немного не доходит до Балатовского парка, в котором всегда много велосипедистов.

Я бы предложил соединить велодорожку № 6 с велодорожкой № 14, проходящей по шоссе Космонавтов и заканчивающейся у спортивного комплекса имени Сухарева. Для этого нужно построить велодорожку на ул. Зои Космодемьянской от пересечения с проспектом Парковым (вершина P нашего графа) до улицы Подлесной (назовем эту вершину PP). Далее сделать велодорожку по улице Подлесная до пересечения ее с шоссе Космонавтов (назовем эту вершину RR), а также соединить велодорожкой вершину RR и существующую вершину R (пересечение шоссе Космонавтов с улицей Д. Давыдова).

Таким образом, построив три велодорожки, мы можем связать два коротких несвязных маршрута:

Рис. 22 Велодорожки № 6 и 14, объединенные в одну компоненту связности новыми велодорожками

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

Велодорожка № 2 (ул. Макаренко – ул. Ушинского), велодорожка № 8 (ул. Макаренко – ул. Юрша), велодорожка № 12 (бульвар Гагарина – ул. Уинской), велодорожка № 10 (пл. Карла Маркса – Южная дамба) и велодорожка № 11 (ул. Чернышевского – бульвар Гагарина)

Велодорожки № 2, 8 и 12 оказались очень востребованы у молодежи: тут находится несколько высших и средних специальных учебных заведений и их общежитий. Я изучил карту и решил, что будет удобно соединить эти дорожки с дорожками № 10 и 11, идущими к центру города. Для этого достаточно построить всего одну велодорожку, идущую по бульвару Гагарина от Южной дамбы (вершина W нашего графа) до улицы Макаренко (вершина C графа). Таким образом, еще две компоненты нашего графа свяжутся в одну компоненту связности:

Рис. 23 Велодорожки № 2, 8, 12,10, 11, объединенные в одну компоненту связности новыми велодорожками

Новый граф состоит из 8 вершин и 7 рёбер, и видно, что по этому графу можно построить несколько маршрутов.

Велодорожка № 3 (ул. Парковая – пл. Гайдара) и велодорожка № 9 (ул. Окулова – ул. Ленина)

Велодорожка № 3 - самая длинная дорожка нашего города, проходящая через его центр. Это очень популярный маршрут для прогулок, здесь катается очень много детей. С точки зрения привлекательности – это один из лучших маршрутов нашего города. В перспективе, мне кажется, его можно объединить с велодорожками 2, 8, 12, 10 и 11, которые мы рассматривали выше. Для того чтобы понять, как это лучше сделать, требуется более глубокий анализ транспортных потоков, так как проектируемые велодорожки будут проходить через центр города, где не всегда имеются широкие улицы и тротуары.

Велодорожка № 4 (ул. Торговая – ул. Сысольская)

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

Будущий граф велодорожек города Перми

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

Рис. 24 Будущий граф велодорожек города Перми

Согласно Генеральному плану города Перми [ CITATION Ген21 \l 1049 ], в перспективе велотранспортная сеть нашего города должна все-таки стать связной.

Рис. 25 Схема велодорожек города Перми в Генеральном плане города

Но Генеральный план развития города показывает стратегию развития на 15-25 лет. Я в своей работе предложил решения на ближайшую перспективу.

Выводы

1. Во время выполнения своей работы я познакомился с основными понятиями теории графов и узнал историю возникновения теории графов.

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

3. В своей работе я ознакомился с теорией построения современной велотранспортной сети. Развитие велотранспорта – общемировой тренд. Во многих странах уже появилось понимание того, что необходимо развивать велосипедный транспорт. Многие российские города тоже начали двигаться в этом направлении. Я узнал, что есть определенные стандарты, которым должна соответствовать велотранспортная сеть современного города.

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

5. Я проехал на велосипеде по всем существующим велодорожкам города, определило, какие маршруты востребованы у велосипедистов, какие наиболее привлекательны для прогулок.

6. Во время своих прогулок на велосипеде я понял, как велодорожки располагаются на карте города и придумал, как можно соединить некоторые из них. Я нарисовал новый граф велотранспортой сети, добавив в него несколько рёбер – велодорожек. Новый граф стал более связным.

Заключение:

Удивительная красота графов заключается в их простоте – они состоят лишь из точек и линий, соединяющих эти точки. Но по-настоящему удивительно то, чего можно достичь с помощью анализа этих точек и линий. [CITATION Мирматематики \l 1049 ]

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

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

Реальный мир сложен, на события и явления влияет множество фактов, но иногда искусство упрощения, умение устранить второстепенные детали и заострить внимание на наиболее важном – лучший способ разобраться в сути проблемы. Теория графов – еще одно подтверждение того, как важно уметь видеть лишь основное и необходимое в сложном мире. [CITATION Мирматематики \l 1049 ]

Список литературы и источников