Исследовательская работа графы и их применение. Исследовательская работа на тему «Графы»1.ppt - Исследовательская работа на тему "Графы"

Титов Максим

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

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

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

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

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

Скачать:

Предварительный просмотр:

ВВЕДЕНИЕ ……………………………………………………………………………….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 г.

Чтобы посмотреть презентацию с картинками, оформлением и слайдами, скачайте ее файл и откройте в PowerPoint на своем компьютере.
Текстовое содержимое слайдов презентации: Исследовательская работаГрафы вокруг нас.Выполнила: Абросимова Елена ученица 8 «А» класса МАОУ Домодедовской СОШ №2Руководитель: Генкина Н.В.

Выяснить особенности применения теории графов при решении математических, логических и практических задач.Цель исследовательской работы:
Изучить теорию графов;Решить задачи с помощью графов;Рассмотреть применение теории графов в различных областях науки;Создать с помощью теории графов маршруты и задачи;Выяснить наличие знаний о графах у учеников 7 классов.Задачи:

Граф-?
Леонард Эйлер Первый кто развил теорию графов, был немецкий и русский математик Леонард Эйлер (1707-1783). Нет науки, которая не была бы связана с математикой

Задача о Кёнигсбергских мостах
Представим задачу в виде графа где острова и берега - точки, а мосты -ребра.
Задачи. №1Мальчики 10«Б» класса Андрей, Витя, Сережа, Валера, Дима при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу). Сколько всего рукопожатий было сделано?
№2 Задача о перестановке четырех коней. Напишите алгоритм перестановки жёлтых коней на место красных коней и красных коней на место жёлтых коней.
Теория графов в различных областях науки. Теория графов в различных областях науки. Собственные разработки Маршрут по домодедовским церквям.
Маршрут автобуса для пенсионеров.
Задача №1.
Ответ:
Задача №2.
Маршрут по Дворцовым Питерским мостам. Исследование:
«Графы и их применение» Л. Ю. Березина.«Знаменитейший ученый муж» изд. Калейдоскоп «Кванта» «Леонард Эйлер» В. Тихомиров«Топология графов» В. Болтянский«Современная школьная энциклопедия. Математика. Геометрия» изд. «Москва Олма Медиа Групп»Граф (математика) - Википедия ru.wikipedia.orgГрафы. Применение графов к решению задач festival.1september.ruГРАФЫ sernam.ruГрафы | Социальная сеть работников образования nsportal.ruГрафы / Математика studzona.comГрафы и их применение в решении задач sch216.narod.ruГрафы 0zd.ruИсточники: Спасибо за внимание.

Муниципальное автономное общеобразовательное учреждение
Домодедовская средняя общеобразовательная школа №2
Исследовательская работа.
«Графы вокруг нас».
Выполнила: Абросимова Е. С. ученица 8 «А» класса.
Руководитель: учитель математики Генкина Н.В.
2014 год.
План:
Вступление.
Гипотеза.
Актуальность темы.
Теория.
Практическое приложение.
Собственные разработки.
Исследование.
Заключение.
Вступление:
Теория графы заинтересовала меня своей возможностью помогать в решении различных головоломок, математических и логических задач. Так как я готовилась к математической олимпиаде, то теория графов была неотъемлемой частью в моей подготовке. Углубившись в эту тему, я решила понять, где ещё встречаются графы в нашей жизни.
Гипотеза:
Изучение теории графов может помочь в решении различных головоломок, математических и логических задач.
Актуальность темы:
Теория графов в настоящее время является интенсивно развивающимся разделом математики. Это объясняется тем, что в виде графовых моделей описываются многие объекты и ситуации, что очень важно для нормального функционирования общественной жизни. Именно этот фактор определяет актуальность их более подробного изучения. Поэтому тематика данной работы достаточно актуальна.
Теория:
Теория графов - раздел математики, изучающий свойства графов. В математической теории граф - это совокупность непустого множества вершин и наборов пар вершин (связей между вершинами). Математические графы с дворянским титулом «граф» связывает общее происхождение от латинского слова «графио» - пишу. Граф называется полным, если каждые две различные вершины его соединены одним и только одним ребром.
Объекты представляются как вершины, или узлы графа, а связи - как дуги, или рёбра. Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах. Степенью вершины называется число ребер графа, которым принадлежит эта вершина.
При изображении графов на рисунках чаще всего используется следующая система обозначений: вершины графа изображаются точками или, при конкретизации смысла вершины, прямоугольниками, овалами и др., где внутри фигуры раскрывается смысл вершины (графы блок-схем алгоритмов). Если между вершинами существует ребро, то соответствующие точки (фигуры) соединяются отрезком или дугой. В случае ориентированного графа дуги заменяют стрелками, или явно указывают направленность ребра. Есть и планарный граф - это граф, который можно изобразить на рисунке без пересечения. В том случае, если граф не содержит циклов (путей однократного обхода рёбер и вершин с возвратом в исходную вершину), его принято называть «деревом». Важные виды деревьев в теории графов - бинарные деревья, где каждая вершина имеет одно входящее ребро и ровно два выходящих, или является конечной - не имеющей выходящих рёбер. Основные понятия теории графов. Маршрут графа – последовательность чередующихся вершин и ребер. Замкнутый маршрут – маршрут, в котором начальная и конечная вершины совпадают. Простая цепь – маршрут, в котором все ребра и вершины различны. Связный граф – граф, в котором каждая вершина достижима из любой другой.
Терминология теории графов поныне не определена строго.
Первый кто развил теорию графов, был немецкий и русский математик Леонард Эйлер (1707-1783). Который известен своей старинной задачей о кёнигсбергских мостах, которую решил в 1736 году. Эйлер математик и механик, внёсший фундаментальный вклад в развитие этих наук. Вся жизнь Л. Эйлера была связана с научной деятельностью и не только связанной с графами. Он говорил: «Нет науки, которая не была бы связана с математикой». Почти полжизни провёл в России, где внёс существенный вклад в становление российской науки. В дальнейшем над графами работали Кениг (1774-1833), Гамильтон (1805- 1865), из современных математиков - К. Берж, О. Оре, А. Зыков.

Задача о кёнигсбергских мостах.
Бывший Кенигсберг (ныне Калининград) расположен на реке Прегель. В пределах города река омывает два острова. С берегов на острова были перекинуты мосты. Старые мосты не сохранились, но осталась карта города, где они изображены. Кенигсбергцы предлагали приезжим следующую задачу: пройти по всем мостам и вернуться в начальный пункт, причём на каждом мосту следовало побывать только один раз.
Этой карте можно поставить в соответствие неориентированный граф - это упорядоченная пара, для которой выполнены определенные условия, где вершинами будут являться части города, а рёбрами - мосты, соединяющие эти части между собой. Эйлер доказал, что задача не имеет решения. В Калининграде (Кенигсберге) помнят о задаче Эйлера. И именно поэтому, граф, который можно нарисовать, не отрывая карандаша от бумаги, называется эйлеровым, а такие контуры образуют так называемые уникурсальные графы.
Теорема: для уникурсального графа число вершин нечётного индекса равно нулю или двум.
Доказательство: Действительно, если граф уникурсален, то у него есть начало и конец обхода. Остальные вершины имеют чётный индекс, так как с каждым входом в такую вершину есть и выход. Если начало и конец не совпадают, то они являются единственными вершинами нечётного индекса. У начала выходов на один больше, чем входов, а у конца входов на один больше, чем выходов. Если начало совпадает с концом, то вершин с нечётным индексом нет. ЧТД.

Свойства графа (Эйлер): Если все вершины графа четные, то можно одним росчерком (т.е. не отрывая карандаша от бумаги и не проводя дважды по одной и той же линии) начертить граф. При этом движение можно начать с любой вершины и окончить в той же вершине. Граф с двумя нечетными вершинами тоже можно начертить одним росчерком. Движение надо начинать от любой нечетной вершины, а заканчивать на другой нечетной вершине. Граф с более чем двумя нечетными вершинами невозможно начертить одним росчерком.
Практическое приложение:
Графы – замечательные математические объекты, с их помощью можно решать очень много различных, внешне не похожих друг на друга задач.
В спортивном зале собрались Витя, Коля, Петя, Сережа и Максим. Каждый из мальчиков знаком только с двумя другими. Кто с кем знаком.
Решение: Построим граф.
Ответ: Витя знаком с Колей и Сережей, Сережа с Витей и Петей, Петя с Сережей и Максимом, Максим с Петей и Колей, Коля с Петей и Максимом.
Мальчики 10 «б» класса Андрей, Витя, Сережа, Валера, Дима при встрече обменялись рукопожатиями (каждый пожал руку другому по одному разу). Сколько всего рукопожатий было сделано? Решение:Пусть каждому из пяти молодых людей соответствует определенная точка на плоскости, названная первой буквой его имени, а производимому рукопожатию - отрезок или часть кривой, соединяющая конкретные точки - имена.
Если подсчитать число ребер графа, изображенного на рисунке, то это число и будет равно количеству совершенных рукопожатий между пятью молодыми людьми. Их 10.
Задача о перестановке четырех коней. Напишите алгоритм перестановки жёлтых коней на место красных коней и красных коней на место жёлтых коней. Конь перемещается за один ход буквой «Г» в горизонтальном, либо в вертикальном положении. Конь может перепрыгивать через стоящие на его пути другие фигуры, но может ходить только на свободные поля.
Решение. Каждой клетке доски сопоставим точку на плоскости, и если из одной клетки можно попасть в другую ходом коня, то соединим соответствующие точки линией, получим граф.
Написание алгоритма перестановки коней становится очевидным.

Усадьба Хакенбуш.
Эту замечательную игру придумал математик Джон Конвей. Для игры используется картинка с "усадьбой Хакенбуш" (смотрите ниже). За один ход игрок стирает один любой отрезок картинки, ограниченный точками или одной точкой, если отрезок это петля. Если после удаление этой линии, часть линий оказывается не связанной с рамкой, то она удалятся тоже. На рисунке пример, где удалятся линия, выделенная зеленым цветом, и вместе с ней удаляются линии дыма, выделенные красным. Игрок, который удаляет последний элемент картинки выигрывает.

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

Задача:
Можно ли обойти все данные комнаты, пройдя через каждую дверь ровно один раз и выйти на улицу через комнату 1 или 10? С какой комнаты надо начинать?

Решение:
1) Пусть комнаты – вершины графа, а двери – ребра. Проверим степени вершин:

2)Только две вершины имеют нечетную степень. Начать движение можно из комнаты 10, а закончить в комнате 8, либо наоборот.
3) Но, чтобы выйти на улицу (из комнаты 10), надо начинать из комнаты 8. В этом случае пройдём все двери один раз и попадём в комнату 10, но окажемся внутри комнаты, а не снаружи:

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

В химии и биологии,

В природоведении,

В проектировании интегральных схем и схем управления,

В истории.

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

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

Также меня вдохновило решение интересных задач, и поэтому я создала свои собственные.
Задача:
Шел урок. Во время урока Маша передала записку Кате. Как составить граф, чтобы записка дошла до Полины. При условиях, что нельзя передавать записку по диагонали, и чтобы граф не пересекался с маршрутом (графом) учительницы.

Задача:
На луг пастух вывел 8 овец. Через некоторое время появился волк, который прикинулся овцой. Как пастуху выявить волка, если каждая овца знакома лишь с двумя другими.
Ответ:

Задача:
Как обойти Дворцовые мосты ни проходя ни по одному мосту дважды. Одной из задач создания такого маршрута было условие, что по одной дороге нельзя проезжать дважды. Это условие можно выполнить, опираясь на теорему Эйлера.

После составления карт и задач, я решила провести исследование и понять, как другие люди пользуются наукой графы.
Исследование о наличии знаний у учеников 7 классов по теории графов:
ВОПРОСЫ:
Играли ли вы в игру нарисовать фигуру по цифрам?
lefttop00
Играли ли вы в игру нарисовать одним росчерком конверт?

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

Заключение:
После того, как я провела эту исследовательскую работу, я изучила более подробно теорию графов, доказала свою гипотезу: «Изучение теории графов может помочь в решении различных головоломок, математических и логических задач», рассмотрела теорию графов в разных областях науки и составила свой собственный маршрут и свои три задачи. Но делая эту работу, я заметила, что многие люди фактически пользуются этой наукой, хотя не имеют о ней ни малейшего представления. Я изучила многое, но еще есть над чем работать.
Список литературы
Л. Ю. Березина «Графы и их применение: Популярная книга для школьников и преподавателей». Изд. Стереотип.- М.: Книжный дом «ЛИБРОКОМ», 2013.- 152 с.
«Знаменитейший ученый муж». Изд. Калейдоскоп «Кванта»
В. Тихомиров «Леонард Эйлер» (К 300-летию со дня рождения). Изд. «Квант»
В. Болтянский «Топология графов». Изд. «Квант»
«Современная школьная энциклопедия. Математика. Геометрия». Под ред. А.А.Кузнецова и М.В. Рыжакова. Изд. «М.: Олма Медиа Групп», 2010. – 816 с.
Цифровые ресурсы:
wikipedia.orgfestival.1september.rusernam.runsportal.rustudzona.comsch216.narod.ru0zd.ru

Российская научно-социальная программа для молодежи и школьников

«Шаг в будущее»

ХV Районная научно-практическая конференция «Шаг в будущее»

Графы и их применение

Исследовательская работа

МБОУ «Шелеховский лицей», 10 класс

Руководитель: Копылова Н.П.

МБОУ «Шелеховский лицей»,

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

Научный руководитель:

Постников Иван Викторович,

младший научный сотрудник

Института систем энергетики им. Л.А. Мелентьева

Сибирского отделения Российской академии наук

г. Шелехов - 2012

Введение, задачи, цель…………………………………………………………… 3

Основная часть……………………………………………………………………. 4

Заключение……………………………………………………………………..... 10

Список литературы…………………………………………………………….... 11

Введение.

Родоначальником теории графов считается Леонард Эйлер. В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов. Толчок к развитию теория графов получила на рубеже XIX и XX столетий, когда резко возросло число работ в области топологии и комбинаторики, с которыми её связывают самые тесные узы родства. Как отдельная математическая дисциплина теория графов была впервые представлена в работе венгерского математика Кёнинга в 30-е годы XX столетия.

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

Дать определение графов и его составляющих

Рассмотреть некоторые виды графов и их свойства

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

Решить ряд прикладных задач с помощью графов

Определить области применения теории графов в окружающей действительности

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

Основная часть.

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

Точки иначе называют вершинами, отрезки – рёбрами графа.

Виды графов:

В общем смысле граф представляется как множество вершин, соединённых рёбрами. Графы бывают полными и неполными. Полный граф - это простой граф, каждая пара различных вершин которого смежна. Неполный граф – это граф, в котором хотя бы 2 вершины не смежны.

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

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

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

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

С вершинами графов связаны 4 теоремы, докажем их с помощью задач:

№1.Участники пионерского слёта, познакомившись, обменялись конвертами с адресами. Докажите, что:

1) всего было передано четное число конвертов;

2)число участников, обменявшихся конвертами нечетное число раз, четное.

Решение. Обозначим участников слёта А 1 , А 2 , А 3 …., А n – вершины графа, а ребра соединяют на рисунке пары вершин, изображающих ребят, которые обменялись конвертами:

1) Степень каждой вершины А j показывает количество конвертов, переданных участником А j своим знакомым, значит общее число переданных конвертов N равно сумме степеней всех вершин графа. N = степ. А 1 + степ. А 2 + … + степ. А n-1 + степ. А n , N = 2р (р – число ребер графа), то есть N – четное число. Из этого следует, что было передано четное число конвертов;

2) Мы доказали, что N – четное, а N = степ. А 1 + степ. А 2 + …. + степ. А n-1 + степ. А n , т.е N – количество участников. Мы знаем, что сумма нечетных слагаемых должна быть четной, а это возможно только в том случае, если число нечетных слагаемых четно. Значит, что число участников, которые обменялись конвертами нечетное число раз, четное.

В ходе решения задачи доказаны две теоремы.

В графе сумма степеней всех его вершин – число чётное, равное удвоенному числу рёбер графа. ∑ степ. А j = степ. А 1 + степ. А 2 + … + степ. А n = 2р, где р – число ребер графа Г, n – число его вершин.

Число нечётных вершин любого графа чётно.

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

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

Каждая вершина графа с девятью вершинами может иметь степень, равную 0, 1, 2, …, 7, 8. Предположим, что существует граф Г, все вершины которого имеют разную степень, т. е. каждое из чисел последовательности 0, 1, 2, …, 7, 8 является степенью одной и только одной из его вершин. Но этого не может быть. Действительно, если в графе есть вершина А со степенью 0, то в нем не найдется вершина В со степенью 8, так как эта вершина В должна быть соединена ребрами со всеми остальными вершинами графа, в том числе и с А. Иначе говоря, в графе с девятью вершинами не могут быть одновременно вершины степени 0 и 8. Следовательно, найдутся хотя бы две вершины, степени которых раны между собой.

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

Решение этой задачи почти дословно повторяется в ходе доказательства следующей теоремы (только число 9 приходится заменить произвольным натуральным числом n ≥ 2).

Во всяком графе с n вершинами, где n ≥ 2, всегда найдутся по меньшей мере две вершины с одинаковыми степенями.

№3. Девять человек проводят шахматный турнир в один круг. К некоторому моменту выясняется, что в точности двое сыграли одинаковое число партий. Докажите, что тогда либо в точности один участник еще не сыграл ни одной партии, либо в точности один сыграл все партии.

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

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

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

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

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

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

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

При решении этой задачи число 9 можно было заменить любым другим натуральным числом n › 2.

Из этой задачи можно вывести следующую теорему:

Если в графе с n вершинами (n 2) в точности две вершины имеют одинаковую степень, то в этом графе всегда найдётся либо в точности одна вершина степени 0, либо в точности одна вершина степени n-1.

Эйлеров путь в графе - это путь, проходящий по всем рёбрам графа и притом только по одному разу.

№4. Как вы помните, охотник за мертвыми душами Павел Иванович Чичиков побывал у известных вам помещиков по одному разу у каждого. Он посещал их в следующем порядке: Манилова, Коробочку, Ноздрева, Собакевича, Плюшкина, Тентетникова, генерала Бетрищева, Петуха, Констанжогло, полковника Кошкарева. Найдена схема, на которой Чичиков набросал взаимное расположение имений и проселочных дорог, соединяющих их. Установите, какое имение кому принадлежит, если ни по одной из дорог Чичиков не проезжал более одного раза.

Решение. По схеме видно, что путешествие Чичиков начал с имения Е, а кончил имением О. Замечаем, что в имения В и С ведут только по две дороги, поэтому по этим дорогам Чичиков должен был проехать. Отметим их жирной линией. Определены участки маршрута, проходящие через А: АС и АВ. По дорогам АЕ, АК и АМ Чичиков не ездил. Перечеркнем их. Отметим жирной линией ЕD; перечеркнем DК. Перечеркнем МО и МН; отметим жирной линией МF; перечеркнем FO; отметим жирной линией FH, HK и КО. Найдем единственно возможный при данном условии маршрут.

Подведем первый итог: задача решена в ходе преобразования картинки. С рисунка остается только считать ответ: имение Е принадлежит Манилову, D – Коробочке, С – Ноздреву, А – Собакевичу, В – Плюшкину, М – Тентетникову, F – Бетрищеву, H – Петуху, K – Констанжогло, O - Кошкареву.

№5. У Ирины 5 подруг: Вера, Зоя, Марина, Полина и Светлана. Она решила двух из них пригласить в кино. Укажите все возможные варианты выбора подруг. Какова вероятность, что Ирина пойдёт в кино с Верой и Полиной?

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

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

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

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

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

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

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

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

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

Рисунок

Грани () и () являются соседями, а грани () и () соседями не являются.

Ребро () является мостом, соединяющим циклы - перегородкой.

Простой цикл, ограничивающий грань - граница грани.

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

Всякое представление графа либо не имеет бесконечной грани,

либо имеет только одну.

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

Формула Эйлера

Для всякого плоского представления связного плоского графа без перегородок число вершин (в), число ребер (р), и число граней с учетом бесконечной (г) связаны соотношением: в – р + г =2.

Предположим, что граф А –связный плоский граф без перегородок. Для его плоского произвольного представления определим алгебраическое значение суммы в – р + г. Затем, данный граф преобразуем в дерево, которое содержит все его вершины. Для этого удалим некоторые ребра графа, разрывая при этом поочередно все его простые циклы, но так, чтобы граф остался связным и без перегородок. Обратим внимание, что при данном удалении одного ребра уменьшается число граней на 1, т.к. при этом либо 2 цикла преобразуются в 1, либо один простой цикл просто пропадает. Из этого следует, что значение разности р – г при этом удалении остается неизменным. Те ребра, которые мы удаляем, выделены пунктиром.

В получившемся дереве число вершин обозначим – вд, ребер – рд, граней – гд. Отматим равенство р – г = рд – гд. В дереве одна грань, значит р – г = рд – 1. Изначально мы задали условие, что при удалении ребер число вершин не меняется, т.е. в = вд. Для дерева справедливо равенство вд – рд = 1. Отсюда следует рд = в – 1, т.е р – г = в – 2 или в – р + г = 2. Формула Эйлера - доказана.

Кёнигсберг

Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам (через реку Преголя), не проходя ни по одному из них дважды? Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически, во время прогулок. Но никому это не удавалось, однако не удавалось и доказать, что это даже теоретически невозможно.

На упрощённой схеме части города (графе) мостам соответствуют линии (дуги графа), а частям города - точки соединения линий (вершины графа). В ходе рассуждений Эйлер пришёл к следующим выводам:

Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа должно быть чётно. Не может существовать граф, который имел бы нечётное число нечётных вершин.

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

Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.

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

На карте старого Кёнигсберга был ещё один мост, появившийся чуть позже, и соединявший остров Ломзе с южной стороной. Своим появлением этот мост обязан самой задаче Эйлера-Канта.

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

Заключение:

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

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

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

Список литературы:

1. «Графы и их применение» Л. Ю. Березина, издательство «Просвещение», Москва, 1979 г.

2. «Алгебра 9 класс» под редакцией С. А. Теляковского, издательство «Просвещение», Москва, 2010 г.