IV Международный конкурс научно-исследовательских и творческих работ учащихся

Старт в науке

ГРАФЫ И ОБЛАСТИ ИХ ПРИМЕНЕНИЯ

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

Ефремова С.Д. 1

---

1МБОУДО «ДДТ «Дриада» г.Снежногорска Мурманской области

Хиневич Е.С. 1

---

1МБОУДО «ДДТ «Дриада» г.Снежногорска Мурманской области

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

1.3 MB

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

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

«В математике следует помнить не формулы, а процесс мышления…»

Е. И. Игнатьев

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

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

Цель определила следующие задачи:

познакомиться с историей теории графов;

изучить основные понятия теории графов и основные характеристики графов;

показать практическое применение теории графов в различных областях знаний;

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

Объект исследования: сфера деятельности человека на предмет применения метода графов.

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

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

Методы исследовательской работы:

В ходе нашего исследования были использованы такие методы, как:

1) Работа с различными источниками информации.

2) Описание, сбор, систематизация материала.

3) Наблюдение, анализ и сравнение.

4) Составление задач.

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

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

ГЛАВА I. ТЕОРЕТИЧЕСКИЙ ОБЗОР МАТЕРИАЛА ПО ТЕМЕ ИССЛЕДОВАНИЯ

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

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

В математике определение графа дается так:

Термин «граф» в математике определяется следующим образом:

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

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

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

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

Рис. 2 Вершина графа

Нуль-граф – это граф, состоящий только из изолированных вершин, не соединенных ребрами.

Полный граф – это граф, каждая пара вершин которого соединена ребром. N-угольник, в котором проведены все диагонали, может служить примеров полного графа.

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

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

Если граф связанный, но не содержит циклов, то такой граф называетсядеревом.

1.  
   Характеристики графов

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

Длина кратчайшей цепи из вершин a и b называется расстоянием между вершинами a и b.

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

Максимально возможное расстояние между двумя любыми вершинами графа называется диаметром графа.

Раскраска графов и применение.

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

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

Только в 1879 году данная задача была опубликована в первом томе «Трудов Королевского географического общества» известным английским математиком Артуром Кэли. Так она получила широкую известность.

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

В 1976 году эта задача была решена при использовании компьютера двумя американскими математиками Кеннетом Аппелем и Вольфгантом Хакеном. Для ее решения все карты были поделены на 2000 типов. Для компьютера была создана программа, которая исследовала все типы с целью выяления таких карт, для раскрашивания которых будет недостаточно четырех красок. Только три типа карт компьютер исследовать не смог, поэтому математики изучали их самостоятельно. В результате было установлено, что для раскрашивания всех 2000 типов карт будет достаточно 4 красок. Им было объявлено о решении проблемы четырех красок. В этот день почтовое отделение при университете, в котором работали Аппель и Хакен на всех марках ставило штемпель со словами: «Четырех красок достаточно».

Можно представить задачу о четырех красках несколько иначе.

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

Эйлеровы и Гамильтоновы графы

В 1859 году английским математиком Уильямом Гамильтоном была выпущена в продажу головоломка – деревянный додекаэдр (двенадцатигранник), двадцать вершин которого были обозначены гвоздиками. Каждая вершина имела название одного из крупнейших городов мира – Кантон, Дели, Брюссель, и т.д. Задача заключалась в нахождении замкнутого пути, который проходит по ребрам многогранника, побывав в каждой вершине только один раз. Для отмечания пути использовался шнур, который цепляли за гвоздики.

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

На реке Прегель расположен город Калининград (бывший Кенигсберг). Река омывала два острова, которые между собой и с берегами были соединены мостами. Старых мостов сейчас уже нет. Память о них осталась только на карте города.

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

При решении задачи про мосты Кенигсберга Эйлеру удалось сформулировать свойства графов.

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

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

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

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

Если граф имеет цикл (не обязательно простой), содержащий все рѐбра графа по одному разу, то такой цикл называется Эйлеровым циклом. Эйлерова цепь (путь, цикл, контур) — цепь (путь, цикл, контур), содержащая все рѐбра (дуги) графа по одному разу.

ГЛАВА II. ОПИСАНИЕ ИССЛЕДОВАНИЯ И ЕГО РЕЗУЛЬТАТЫ

2.1. Этапы проведения исследования

Для проверки гипотезы исследование включало три этапа (таблица 1):

Этапы исследования

Таблица 1.

2.2. Области практического применения графов

Графы и информация

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

Например, если нужно закодировать некоторое число сообщений в виде определенных последовательностей нулей и единиц различной длины. Код считается наилучшим, для заданной вероятности кодовых слов, если средняя длина слов наименьшая в сравнении другими распределениями вероятности. Для решения такой задачи Хаффман предложил алгоритм, в котором, код представляется деревом-графом в рамках теории поиска. Для каждой вершины предлагается вопрос, ответом на который может быть либо, «да», либо «нет» – что соответствует двум ребрам, выходящим из вершины. Построение такого дерева завершается после установления того, что требовалось. Это может применяться в интервьюировании нескольких человек, когда заранее неизвестен ответ на предыдущий вопрос, план интервью представляется в виде двоичного дерева.

Графы и химия

Еще А. Кэли рассмотрел задачу о возможных структурах насыщенных (или предельных) углеводородов, молекулы которых задаются формулой:

CnH_2n+2

Все атомы углеводорода 4-хвалентны, все атомы водорода 1-валентны. Структурные формулы простейших углеводородов показаны на рисунке.

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

Графы и биология

Процесс размножения бактерий – это одна из разновидностей ветвящихся процессов, встречающихся в биологической теории. Пусть каждая бактерия по истечению определенного времени или погибает, или делится на две. Следовательно, для одной бактерии мы получим двоичное дерево размножения ее потомства. Вопрос задачи заключается в следующем, какое количество случаев содержит k потомков в n-м поколение одной бактерии? Данное соотношение в биологии носит название процесс Гальтона-Ватсона, которое обозначает необходимое количество нужных случаев.

Графы и физика

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

Итак, все выше сказанное подтверждает практическую ценность графов.

Математика интернета

Интернет – всемирная система объединенных компьютерных сетей для хранения и передачи информации.

Сеть интернет можно представить в виде графа, где вершины графа – это интернет сайты, а ребра – это ссылки (гиперссылки), идущие с одних сайтов на другие.

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

Веб-граф разрежен. Он содержит всего лишь в несколько раз больше ребер, чем вершин.

Несмотря на разреженность, интернет очень тесен. От одного сайта до другого по ссылкам, можно перейти за 5 – 6 кликов (знаменитая теория «шести рукопожатий»).

Как мы знаем, степень графа – это число ребер, которым принадлежит вершина. Степени вершин веб-графа распределены по определенному закону: доля сайтов (вершин) с большим количеством ссылок (ребер) мала, а сайтов с малым количеством ссылок – велика. Математически это можно записать так:

где – доля вершин определенной степени, – степень вершины, – постоянная, независящая от числа вершин веб-графа, т.е. не меняется в процессе добавления или удаления сайтов (вершин).

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

Интернет как целое устойчив к случайным атакам на сайты.

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

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

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

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

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

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

г. Мурманск с помощью графа.

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

В качестве примера рассмотрим типичный случай прибытия в Мурманск из аэропорта в первый раз. Планируется посетить следующие достопримечательности:

1. Морской православный храм Спас-на-водах;

2. Свято-Никольский собор;

3. Океанариум;

4. Памятник коту Семену;

5. Атомный ледокол Ленин;

6. Парк Огни Мурманска;

7. Парк Долина Уюта;

8. Кольский мост;

9. Музей истории Мурманского морского пароходства;

10. Площадь Пяти углов;

11. Морской торговый порт

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

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

Достопримечательности на карте (слева) и полученный граф (справа) показаны на соответствующем рисунке ПРИЛОЖЕНИЯ №1. Таким образом, новоприбывший вначале проедет около Кольского моста(и, при желании может пересечь его туда - обратно); затем отдохнет в Парке Огни Мурманска и Долине Уюта и отправится дальше. В итоге оптимальный маршрут составит:

8. Кольский мост6. Парк Огни Мурманска7. Парк Долина Уюта2. Свято-Никольский собор10. Площадь Пяти углов5. Атомный ледокол Ленин9. Музей истории Мурманского морского пароходства11. Морской торговый порт1. Морской православный храм Спас-на-водах4. Памятник коту Семену3. Океанариум.

С помощью графа можно также визуализировать схему проведения соцопросов. Примеры представлены в ПРИЛОЖЕНИИ №2. В зависимости от данных ответов опрашиваемому задают разные вопросы. Например, если в социологическом опросе №1 опрашиваемый считает математику важнейшей из наук, у него спросят, уверенно ли он чувствует себя на уроках физики; если же он считает иначе, второй вопрос будет касаться востребованности гуманитарных наук. Вершинами такого графа являются вопросы, а ребрами – варианты ответов.

2.3. Применение теории графов при решении задач

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

Задача №1.

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

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

Ответ: 10 рукопожатий (каждая линия означает одно рукопожатие).

Задача №2.

У моей бабушке в деревне, возле дома растут 8 деревьев: тополь, дуб, клен, яблоня, лиственница, береза, рябина и сосна. Рябина выше лиственницы, яблоня выше клена, дуб ниже березы, но выше сосны, сосна выше рябины, береза ниже тополя, а лиственница выше яблони. В какой последовательности расположатся деревья по высоте от самого высокого к самому низкому.

Решение:

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

Ответ: клен, яблоня, лиственница, рябина, сосна, дуб, береза и тополь.

Задача №3.

У Мамы есть 2 конверта: обычный и авиа, и 3 марки: квадратная, прямоугольная и треугольная. Сколькими способами Мама может выбрать конверт и марку, чтобы отправить письмо Папе?

Ответ: 6 способов

Задача №4.

Между населенными пунктами A, B, C, D, E построены дороги. Нужно определить длину кратчайшего пути между пунктами А и Е. Передвигаться можно только по дорогам, длина которых указана на рисунке.

Ответ: 6

Задача №5.

Тремя одноклассника – Максим, Кирилл и Вова решили заняться спортом и прошли отбор спортивные секции. Известно, что в баскетбольную секцию претендовал 1 мальчик, а в хоккей хотели играть трое. Максим пробовался только в 1 секцию, Кирилл отбирался во все три секции, а Вова в 2. Кого из мальчиков в какую спортивную секцию отобрали?

Решение: Для решения задачи применим графы

Баскетбол Максим

Футбол Кирилл

Хоккей Вова

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

Задача №6.

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

1. Преподаватель ОБЖ согласен дать только последний урок;

2. Преподаватель географии может дать либо второй, либо третий урок;

3. Математик готов дать либо только первый, либо только второй урок;

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

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

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

1. 1) физика 2. 1) математика 3. 1) математика

2) математика 2) физика 2) география

3) география 3) география 3) физика

4) ОБЖ 4) ОБЖ 4) ОБЖ

Заключение

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

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

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

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

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

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

Березина Л. Ю. «Графы и их применение» – М.: «Просвещение», 1979

Гарднер М. «Математические досуги», М. «Мир», 1972

Гарднер М. «Математические головоломки и развлечения», М. «Мир», 1971

Горбачев А. «Сборник олимпиадных задач» – М. МЦНМО, 2005

Зыков А. А. Основы теории графов. — М.: «Вузовская книга», 2004. — С. 664

Касаткин В. Н. «Необычные задачи математики», Киев, «Радяньска школа», 1987

Математическая составляющая / Редакторы-составители Н.Н. Андреев, С.П. Коновалов, Н.М. Панюшкин. – М.: Фонд «Математические этюды» 2015 г. – 151 с.

Мельников О. И. «Занимательные задачи по теории графов», Мн. «ТетраСистемс»,2001

Мельников О.И. Незнайка в стране графов: Пособие для учащихся. Изд. 3-е, стереотипное. М.: КомКнига, 2007. — 160 с.

Олехник С. Н., Нестеренко Ю. В., Потапов М. К. «Старинные занимательные задачи», М. «Наука», 1988

Оре О. «Графы и их применения», М. «Мир», 1965

Харари Ф. Теория графов / Пер.с англ. и предисл. В. П. Козырева. Под ред. Г. П. Гаврилова. Изд. 2-е. - М.: Едиториал УРСС, 2003. - 296 с.

ПРИЛОЖЕНИЕ №1

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

г. Мурманск с помощью графа.

Оптимальный маршрут составит:

8. Кольский мост6. Парк Огни Мурманска7. Парк Долина Уюта2. Свято-Никольский собор10. Площадь Пяти углов5. Атомный ледокол Ленин9. Музей истории Мурманского морского пароходства11. Морской торговый порт1. Морской православный храм Спас-на-водах4. Памятник коту Семену3. Океанариум.

ПУТЕВОДИТЕЛЬ ПО ДОСТОПРИМЕЧАТЕЛЬНОСТЯМ МУРМАНСКА

ПРИЛОЖЕНИЕ №2

Социологические опросы № 1, 2