«Экскурсионный маршрут по Лунинскому району с помощью теории графов»

Презентация к экскурсионному маршрутуPPTX / 3.32 Мб

/data/files/c1717340897.pptx (Презентация к экскурсионному маршруту)МУНИЦИПАЛЬНОЕ БЮДЖЕТНОЕ ОБЩЕОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ СРЕДНЯЯ ОБЩЕОБРАЗОВАТЕЛЬНАЯ ШКОЛА №1 Р. П. ЛУНИНО ИМЕНИ АРТАМОНОВА Н. С.

Районная научно-практическая конференция школьников

«Старт в науку»

Секция «Математика»

«Составление экскурсионного маршрута по р. п. Лунино с помощью теории графов»

Подготовил:

Ибрагимов Саламбек Бекханович

учащийся 8 «А» класса

МБОУ СОШ №1 р. п. Лунино

им. Артамонова Н. С.

Пензенская обл., р.п. Лунино,

ул. Мясникова,42, 442730

Пензенская обл., Лунинский район,

с. Липовка, ул. Садовая,15, 442725

Руководитель:

Натолина Елена Сергеевна,

учитель математики

МБОУ СОШ №1 р. п. Лунино

им. Артамонова Н. С.

Пензенская обл., р.п. Лунино,

ул. Мясникова,42, 442730

89374217306

1

Содержание

Введение...................................................................................................................3

Глава 1. Основные понятия теории графов...........................................................5

Глава 2. Применение теории графов.....................................................................8

2.1 Достопримечательности р.п. Лунино..............................................................8

2.2 Экскурсионный маршрут................................................................................10

Заключение.............................................................................................................15

Библиографический список..................................................................................17

2

Введение

Наш мир полон не только букв и цифр, но и самых разных изображений.

Это и картины, и всевозможные фотографии (начиная с кадров из отпуска и

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

троллейбусные маршруты.

Современная комбинаторика – это красивейший, бурно развивающийся

раздел математики, богатый яркими результатами и нетривиальными

приложениями в алгебре, геометрии, анализе и т.д., см. хотя бы [4], [3], [7].

Одна из центральных глав в комбинаторике – теория графов [5], [6].

Удивительная простота графа нашла применение во многих областях. Они

позволяют решить множество интересных задач, и им посвящен отдельный

раздел современной математики «Теория графов».

Это и обуславливает актуальность выбранной темы.

В 2020 году страна отмечала 75 лет Победы советского народа в Великой

Отечественной Войне и окончание Второй Мировой Войны. Свой вклад в победу в этой войне внесли и наши земляки - жители р. п. Лунино.

В связи с такими знаменательными датами передо мной стала задача

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

поможет математика и ее раздел «Теория графов».

Гипотеза: составить путь прохождения достопримечательностей р. п. Лунино, не проходя по ним дважды.

3

Графом в математике называется конечная совокупность точек,

именуемых вершинами; некоторые из них соединены друг с другом линиями,

называемых ребрами графа [9, c.85]. Графы используют при составлении карт и генеалогических древ. Графами являются блок-схемы программ для ЭВМ, сетевые графики строительства. Одними из самых распространённых графов являются схемы линий метрополитена или электропередач.

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

применения теории графов для составления экскурсионного маршрута по

достопримечательностям р. п. Лунино.

В связи с поставленной целью появляются следующие задачи нашей

работы:

• ознакомиться с основными положениями теории графов;

• составить граф достопримечательностей р. п. Лунино;

• изучить заданный граф;

• составить путь прохождения заданного графа:

4

Глава 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 можно разбить на непересекающиеся подмножества

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

5

связными между собой, а вершины различных множеств – несвязны. Тогда все

выделенные таким образом подграфы называют компонентами связности графа G. При этом связный граф имеет одну компоненту связности [4, c.8].

Доказано, что в конечном связном графе всегда можно построить

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

Ребро (v, u) связного графа G называется мостом, если после его удаления

G станет несвязным и распадется на два связных графа G’ и G’’.

Граф называется гамильтоновым, если для каждой вершины графа

найдется маршрут начинающейся и заканчивающей в этой вершине и

проходящий через все вершины только один раз. Такой маршрут называется

гамильтоновым циклом.

Гамильтоновы графы применяются для моделирования многих

практических задач, например, служат моделью при составлении расписания

движения поездов. Основой всех таких задач служит классическая задача

коммивояжера: коммивояжер должен совершить поездку по городам и

вернуться обратно, побывав в каждом городе ровно один раз, сведя при этом

затраты на передвижения к минимуму.

Графическая модель задачи коммивояжера состоит из гамильтонова

графа, вершины которого изображают города, а ребра — связывающие их

дороги. Кроме того, каждое ребро оснащено весом, обозначающим

транспортные затраты, необходимые для путешествия по соответствующей

дороге, такие, как, например, расстояние между городами или время

движения по дороге. Для решения задачи необходимо найти гамильтонов

цикл минимального общего веса.

К сожалению, эффективный алгоритм решения данной задачи пока не

известен. Для сложных сетей число гамильтоновых циклов, которые

необходимо просмотреть для выделения минимального, непомерно огромно.

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

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

Для полных графов поиск гамильтоновых циклов осуществляется с

помощью алгоритма ближайшего соседа:

1. Выбрать исходную вершину и включить её в маршрут.

2. Выбрать вершину ближайшую к данной по весу, включить её в маршрут.

3. Выбрать не использованные вершины ближайшую к последней, включить её в маршрут.

6

4. Вернуться к шагу 2 если не использованы все вершины.

5. Включить в маршрут исходную вершину [9, c.75]..

Гамильтонова цепь – это цепь, которая проходит через все вершины по

одному разу без возвращения в начальную вершину. Рёбра при этом могут быть

пройдены не все [2, c.23].

Все изложенные понятия помогут нам правильно составить граф по

достопримечательностям р. п. Лунино и положительно ответить на вопрос

гипотезы.

7

Глава 2. Применение теории графов

2.1 Достопримечательности р. п. Лунино

Исторических мест, посвященных победе в Великой Отечественной

войне, в р. п. Лунино я выбрал 5 достопримечательностей.

А именно:

Памятная стела с именами лунинцев, погибших на фронтах Великой Отечественной войны,

Мемориал Великой Отечественной войны (на ул. Белинской),

Братская могила,

Самолет МиГ-15 Героя Советского Союза Н. С. Артамонова,

Мемориал Великой Отечественной войны (на ул. Юбилейная)

Памятная стела с именами лунинцев, погибших на фронтах Великой Отечественной войны

8

Мемориал Великой Отечественной войны (на ул. Белинской)

Братская могила

9

Самолет МиГ-15 Героя Советского Союза Н. С. Артамонова

Мемориал Великой Отечественной войны (на ул. Юбилейная)

10

2.2 Экскурсионный маршрут

Определившись с памятными местами в Лунино, нанесем на карту

выбранные памятники и соединим их по дорогам.

Памятная стела с именами лунинцев, погибших на фронтах Великой Отечественной войны,

Мемориал Великой Отечественной войны (на ул. Белинской),

Братская могила,

Самолет МиГ-15 Героя Советского Союза Н. С. Артамонова,

Мемориал Великой Отечественной войны (на ул. Юбилейная)

11

Составление графа.

Рисунок 2.8

Построенный граф назовем G.

Граф G является неполным. Проведем недостающие ребра и

получим полный граф G1 (рис. 2.9).

Рисунок 2.9

Полный граф — простой неориентированный граф, в котором каждая

пара различных вершин смежна.

Исходный граф 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 распадается на два

G1 {v1} и G2 {v2 v3 v4 v5}

Граф G является конечным (т.к. число вершин конечно). Заданный граф не

является ориентированным (т.к. вершины не упорядочены).

Граф G является связным.

Существует замкнутый путь по ребрам графа

{v2v3 v4 }, {v3 v4 v5}, {v2v 4 v5 }.

По данному графу можно заметить, что составить гамильтонов цикл не

получится, так как вершина v1 имеет степень 1, значит, можно, либо выйти из

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

12

Составим всевозможные пути:

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 (а, б, в, г, д)

Для выполнения поставленной задачи я изучил различные пути

передвижения для посещения памятных мест и пришел к следующим выводу:

один из удобных для меня вариантов является маршрут, цепь которого представлена следующим образом v1, v2, v3, v4, v5 (рис. 2.11, а). Заданный мною маршрут будет являться открытым, так как его концевые точки не совпадут. Маршрут будет являться цепью, потому, что ни одно ребро не повторилось.

Заданный мною экскурсионный маршрут построился таким образом:

Памятная стела с именами лунинцев, погибших на фронтах Великой Отечественной войны,

Мемориал Великой Отечественной войны (на ул. Белинской),

Братская могила,

Самолет МиГ-15 Героя Советского Союза Н. С. Артамонова,

Мемориал Великой Отечественной войны (на ул. Юбилейная)

14

Заключение

Теория графов тесно связана с нашей жизнью, но мы этого часто даже не

замечаем: различные маршруты (от дома до школы, походы по магазинам,

экскурсии по городу и др.), составление генеалогического дерева, маршруты

автобусов и троллейбусов, карты городов и др.

Теория графов и связанные с ним методы исследований в настоящее время

является интенсивно развивающимся разделом дискретной математики. Язык

графов прост, понятен и нагляден.

В ходе написания исследовательской работы я рассмотрел лишь

некоторые вопросы по теории графов, подробно познакомился с

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

Теорию графов можно применять не только при составлении

экскурсионных маршрутов, но и при распределении автозаправок, станций

скорой помощи, наиболее удобных и экономичных маршрутов транспорта.

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

Хочется пожелать всем не забывать подвиг наших дедов и прадедов в

Великой Отечественной Войне!

Данную тему можно развивать. Можно, применив теорию графов,

составить кратчайшие и удобные маршруты по другим

достопримечательностям, например, города Пенза.

15

Библиографический список

1. Альсина К. Карты метро и нейронные сети .Теория графов/ К.

Альсина// Мир математики/ К. Альсина. — Де Агостини, 2015. — 140 с.

2. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И.

Лекции по теории графов. М.: Наука, 1990. 384с. (Изд.2, испр. М.: УРСС, 2009.

392 с.)

3. Лекции по теории графов/Емеличев В. А., Мельников О. И.,

Сарванов В. И., Тышкевич Р. И. – М.: Наука,.Гл. ред. физ.-мат. лит., 1990. –

384с

4. Оре О., Теория графов./ О. Оре — М.: Наука, 1968. —336с.

5. Савин, А. Графы/ А. Савин//Квант №6. – 1994. – ноябрь/декабрь –

С.32

6. Савин А.П. Графы// Энциклопедический словарь юного математика/

Сост. А.П. Савин.- М.: Педагогика, 1989. – 352стр.

7. Уилсон Р. Введение в теорию графов/ Р. Уилсон. - Пер с англ. М.:

Мир, 1977. — 208с

8. Харари Ф. Теория графов/ Ф. Харари. – М.: Мир, 1973. – 300с.

9. Элементы математики в задачах (с решениями и комментариями). Ч.

I / Т. И. Голенищева-Кутузова, А. Д. Казанцев, Ю. Г. Кудряшов и др.—

М.:МЦНМО, 2010.—248 с.

16