Исследовательская работа "Поиск кратчайшего пути"

СОДЕРЖАНИЕ

ВВЕДЕНИЕ ……………………………………………………………………………….3

РАЗДЕЛ 1. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ ГРАФОВ …………………………………5

1. Основные понятия теории графов ......…………………...……...…………5
2. Характеристика Эйлеровых графов …………………………...…………...7
3. Поиск кратчайшего расстояния в графе (Алгоритм Дейкстри)…………..8

РАЗДЕЛ 2. МАРШРУТЫ НИЖНЕГОРСКОГО РАЙОНА ……………………..……10

1. Маршруты Нижнегорского района …..…..……………………………….10
2. Исследование маршрутов Нижнегорского района ……..………………..11

ЗАКЛЮЧЕНИЕ ………………………………………………………………………….17

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ …………………………………….19

ВВЕДЕНИЕ

Графы - это замечательные математические объекты, с помощью, которых можно решать математические, экономические и логические задачи. Также можно решать различные головоломки и упрощать условия задач по  физике, химии, электронике, автоматике. Графы используют при составлении карт и генеалогических древ. Графами являются блок-схемы программ для ЭВМ, сетевые графики строительства, где вершины – события, означающие окончания работ на некотором участке, а ребра, связывающие эти вершины, - работы, которые возможно начать по совершении одного события и необходимо выполнить для  совершения следующего. Одними из самых распространённых графов являются схемы линий метрополитена.

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

Актуальность темы заключается в том, что теория графов в настоящее время является интенсивно развивающимся разделом дискретной математики. Это объясняется тем, что в виде графовых моделей описываются многие объекты и ситуации: коммуникационные сети, схемы электрических и электронных приборов, химические молекулы, отношения между людьми, всевозможные транспортные схемы и многое-многое другое. Очень важное для нормального функционирования общественной жизни. Именно этот фактор определяет актуальность их более подробного изучения.  

Цель работы – исследование транспортных путей Нижнегорского района.

Задачи работы:

1. Рассмотреть все маршруты Нижнегорского района.

2. По данным маршрутов составить новые маршруты.

3. Показать являются ли новые маршруты Эйлеровыми графами.

4. Построить матрицу смежности для новых маршрутов.

5. Найти кратчайшие расстояния от пгт.Нижнегорского до населенных пунктов.

Объектом исследования является карта транспортных путей Нижнегорского района.

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

Применяемые методы: поиск источников информации, наблюдение, сравнение, анализ, математическое моделирование.

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

При работе использовал ряд литературных источников: специальная литература по теории графов, познавательную литературу, различные научно-популярные, образовательные, специализированные журналы.

РАЗДЕЛ 1

ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ ГРАФОВ

1.1. Основные понятия теории графов        

Граф представляет собой непустое множество точек и множество отрезков, оба конца которых принадлежат заданному множеству точек. (Рис.1.1.)

Рис.1.1.

Вершина графа — точка, где могут сходиться/выходить рёбра и/или дуги.                                                                  

Ребро графа — ребро соединяет две вершины графа.

Степень вершины - количество рёбер, выходящих из вершины графа.

 Вершина графа, имеющая нечётную степень, называется нечетной, а чётную степень – чётной.

Если направление связи имеет значение, то линии снабжают стрелками, и в этом случае граф называется ориентированным графом, орграфом. (Рис.1.2.)

Рис.1.2.

Взвешенный граф — граф, каждому ребру которого поставлено в соответствие некое значение (вес ребра). (Рис.1.3.)

Рис. 1.3.

Графы, в которых построены все возможные ребра, называются полными графами. (Рис.1.4.)

Рис. 1.4.    

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

Матрица смежности – это матрица, элемент M[i] [j] которой равен 1, если существует ребро из вершины i в вершину j, и равен 0, если такого ребра нет (Рис.1.5. для графа на рис.1.1).            

1.2. Характеристика Эйлеровых графов

Граф, который можно нарисовать, не отрывая карандаша от бумаги, называется эйлеровым. (рис.1.6.)

Такими графы названы в честь учёного Леонарда Эйлера.

Закономерность 1.

Невозможно начертить граф с нечетным числом нечетных вершин.
Закономерность 2.  

Если все вершины графа четные, то можно не отрывая карандаш от бумаги («одним росчерком»), проводя по каждому ребру только один раз, начертить этот граф. Движение можно начать с любой вершины и закончить его в той же вершине.
Закономерность 3.

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

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

Рис.1.6.

1.3. Поиск кратчайшего расстояния в графе (Алгоритм Дейкстри)

Задача: задана сеть дорог между городами, часть которых могут иметь одностороннее движение. Найти кратчайшие расстояния от заданного города до всех остальных городов (рис.1.7).

Та же задача: дан связный граф с N вершинами, веса ребер заданы матрицей W. Найти кратчайшие расстояния от заданной вершины до всех остальных.

Алгоритм Дейкстры (E.W. Dijkstra, 1959):

1. Присвоить всем вершинам метку ∞.

2. Среди нерассмотренных вершин найти вершину j с наименьшей меткой.

3. Для каждой необработанной вершины i: если путь к вершине i через вершину j меньше существующей метки, заменить метку на новое расстояние.

4. Если остались необработанны вершины, перейти к шагу 2.

5. Метка = минимальное расстояние.

Рис.1.7.

Рис.1.8. Решение задачи

РАЗДЕЛ 2

МАРШРУТЫ НИЖНЕГОРСКОГО РАЙОНА

2.1. Маршруты Нижнегорского района

Нижнегорский район находится в степной части на севере АР Крым. В состав Нижнегорского района входят пгт.Нижнегорский и 59 населенных пунктов.

Через Нижнегорский район проходят две трассы: 2Р58 и 2Р64. Существуют 8 маршрутов, следующие от А/С Нижнегорская до других населенных пунктов. В своей работе я буду рассматривать эти маршруты:

1 маршрут «Нижнегорск – Красногвардейск». Следует через: Нижнегорск – Плодовое – Митофановка – Буревестник – Владиславовка.

2 маршрут «Нижнегорск - Изобильное»: Нижнегорск – Семенное – Кирсановка – Лиственное – Охотское – Цветущее – Емельяновка – Изобильное.

3 маршрут «Нижнегорск - Великоселье»: Нижнегорк – Семенное – Двуречье – Акимовка – Лужки – Заливное – Степановка – Луговое – Чкалово – Великоселье.

4 маршрут «Нижнегорск – Белогорск (трасса 2Р64)»: Нижнегорск – Желябовка – Ивановка – Заречье – Серово – Садовое – Пены.

5 маршрут «Нижнегорск - Уваровка»: Нижнегорск – Семенное – Новоивановка – Уварвка.

6 маршрут «Нижнегорск - Любимовка»: Нижнегорск – Семенное – Двуречье – Акимовка – Лужки – Заливное – Степановка – Луговое – Коворово – Дворовое – Любимовка.

7 маршрут «Нижнегорск - Пшеничное»: Нижнегорск – Семенное – Двуречье – Акимовка – Лужки – Заливное – Степановка – Луговое – Коворово – Дворовое – Сливянка – Пшеничное.

8 маршрут «Нижнегорск – Зоркино (траса 2Р58)»: Нижнегорск – Разливы – Михайловка – Кунцево – Зоркино.

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

Маршруты  «Нижнегорск - Уваровка» «Нижнегорск - Любимовка» «Нижнегорск - Пшеничное» изменить нельзя, так как по пути их следования, автобусы заезжают во все населенные пункты, поэтому эти маршруты я рассматривать не буду.

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

2.2. Исследование маршрутов Нижнегорского района

1 маршрут: Нижнегорск – Красногвардейск.

Нижнегорск – 1

Плодовое – 2

Митрофановка – 3

Червоное – 6

Буревестник – 4

Новогригорьевка – 7

Владиславовка – 5

Не заезжает в пункт 6, 7. Добавим в маршрут эти населенные пункты.

Рис.2.1.

Граф не является Эйлеровым. Новый маршрут выглядит так: Нижнегорск – Плодовое – Митрофановка – Буревестник – Новогригорьевка – Владиславовка. Добавилось село Новогригорьевка.

2 маршрут: Нижнегорск – Изобильное.

Нижнегорск – 1

Семенное – 2

Кирсановка – 3

Лиственное – 4

Охотское – 5

Цветущее – 6

Емельяновка – 7

Изобильное – 8

Кулички – 9

Родники - 10

        Не заезжает в пункт 9,10. Добавим в маршрут эти населенные пункты.

Рис.2.2.

Граф не является Эйлеровым и связным, поэтому нельзя построить новый маршрут. Маршрут остается тот же.

3 маршрут: Нижнегорск - Великоселье

Нижнегорск – 1

Семенное – 2

Двуречье – 3

Акимовка – 4

Лужки – 5

Заливное – 6

Степановка – 7

Луговое – 8

Чкалово – 9

Великоселье – 10

Широкое - 11

Не заезжает в пункт 11. Добавим в маршрут этот населенный пункт.

Рис.2.3.

Граф не является Эйлеровым. Маршрут остается тот же.

4 маршрут: Нижнегорск - Белогорск (Трасса 2Р64)

Нижнегорск – 1                Косточковка - 12

Желябовка – 2                Фрунзе - 13

Ивановка – 3                        Приречное - 14

Заречье – 4                        Жемчужина - 15

Серово – 5                        

Садовое – 6                        

Пены – 7                        

Ломоносово – 8

Кукурузное – 9

Тамбовка – 10

Тарасовка - 11

Не заезжает в пункты 8-18. Добавим в маршрут эти населенные пункты.

Рис.2.4.

Граф не является Эйлеровым. Новый маршрут выглядит так: Нижнегорск – Желябовка – Ивановка – Заречье – Тамбовка – Тарсовка – Приречное – Жемчужина – Пены.

5 маршрут: Нижнегорск - Зоркино (Трасса 2Р58)

Нижнегорск – 1

Разливы – 2

Михайловка – 3

Кунцево – 4

Зоркино – 5

Уютное – 6

Нижинское – 7

Не заезжает в пункт 6,7. Добавим в маршрут эти населенные пункты.

Рис.2.5.

Граф не является Эйлеровым и связным, поэтому маршрут остается тот же.

ЗАКЛЮЧЕНИЕ

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

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

В процессе исследования была проделана следующая работа:

1. Проанализирована и проработана литература по теме исследования.

2. Рассмотрены и изучены различные  виды фракталов.

3. Представлена классификация фракталов.

4. Собрана коллекция фрактальных образов для первичного ознакомления с миром фракталов.

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

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

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

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. В.М. Бондарев, В.И. Рублинецкий, Е.Г. Качко. Основы программирования, 1998 г.

2. Н. Кристофидес. Теория графов: алгоритмический подход, Мир, 1978 г.

3. Ф.А. Новиков. Дискретная математика для программистов, Питер, 2001 г.

4. В.А. Носов. Комбинаторика и теория графов, МГТУ, 1999 г.

5. О. Оре. Теория графов, Наука, 1982 г.

6. www.codenet.ru

7. www.algolist.ru

8. www.wikipedia.ua