Исследовательская работа ученицы 8 класса Элементы теории графов и их примение

XVIII муниципальный конкурс исследовательских работ учащихся
Управление образования администрации Карагайского муниципального района
МОУ «Карагайская средняя общеобразовательная школа №2»

Направление: естественно-математическое






"Элементы теории графов и их применение"


Автор: Попова Алина Андреевна,
ученица 8б класса
Руководители: Волегова Елена Павловна, учитель математики









Карагай – 2016
Оглавление
13 TOC \o "1-3" \h \z \u 1413 LINK \l "_Toc443056022" 14Введение 13 PAGEREF _Toc443056022 \h 1431515
13 LINK \l "_Toc443056023" 14Историческая справка 13 PAGEREF _Toc443056023 \h 1441515
13 LINK \l "_Toc443056024" 14Основные понятия 13 PAGEREF _Toc443056024 \h 1451515
13 LINK \l "_Toc443056025" 14Деревья 13 PAGEREF _Toc443056025 \h 1461515
13 LINK \l "_Toc443056026" 14Задача про Кенигсбергские мосты 13 PAGEREF _Toc443056026 \h 1471515
13 LINK \l "_Toc443056027" 14Графы изоморфные и плоские 13 PAGEREF _Toc443056027 \h 1481515
13 LINK \l "_Toc443056028" 14Задачи на применение теории графов 13 PAGEREF _Toc443056028 \h 1491515
13 LINK \l "_Toc443056029" 14Заключение 13 PAGEREF _Toc443056029 \h 14121515
13 LINK \l "_Toc443056030" 14Библиографический список. 13 PAGEREF _Toc443056030 \h 14131515
13 LINK \l "_Toc443056031" 14Приложения 13 PAGEREF _Toc443056031 \h 14141515
13 LINK \l "_Toc443056032" 141.Виды графов. 13 PAGEREF _Toc443056032 \h 14141515
13 LINK \l "_Toc443056033" 142. Путь. Простой путь 13 PAGEREF _Toc443056033 \h 14151515
13 LINK \l "_Toc443056034" 143.Связные и несвязные графы 13 PAGEREF _Toc443056034 \h 14151515
13 LINK \l "_Toc443056035" 144. Граф - дерево 13 PAGEREF _Toc443056035 \h 14151515
13 LINK \l "_Toc443056036" 145.Мосты Кенигсберга 13 PAGEREF _Toc443056036 \h 14161515
13 LINK \l "_Toc443056037" 146.Изоморфные графы 13 PAGEREF _Toc443056037 \h 14161515
13 LINK \l "_Toc443056038" 147.Плоские и полные графы 13 PAGEREF _Toc443056038 \h 14161515
13 LINK \l "_Toc443056039" 148.Подсчет количества отправленных SMS-сообщений 13 PAGEREF _Toc443056039 \h 14171515
13 LINK \l "_Toc443056040" 149.Количество различных способов пообедать 13 PAGEREF _Toc443056040 \h 14171515
13 LINK \l "_Toc443056041" 1410. Графы к задаче для 2 класса 13 PAGEREF _Toc443056041 \h 14171515
13 LINK \l "_Toc443056042" 1411. Граф к задаче про шахматы 13 PAGEREF _Toc443056042 \h 14171515
15
Введение
На уроке математики в 5 классе, помню, мы решали задачу на определение количества возможных чисел, которые можно составить из пяти различных цифр без повторения. Я попыталась перебрать все возможные числа, но поняла, что это может занять достаточно много времени. Учитель же предложил нарисовать что-то вроде схемы, состоящей из точек и отрезков, исходящих из этих точек. С помощью этой схемы мы достаточно быстро сумели подсчитать количество всевозможных чисел. Учитель назвал полученную схему графом. Она сказала, что существует целая теория графов, которая позволяет решать большой круг задач. В дальнейшем все чаще на уроках мы встречали такие задачи. Даже участвуя в различных математических конкурсах и олимпиадах, я часто сталкиваюсь с теорией графов. Мне стало очень интересно, что это за теория, и какие задачи можно решать, пользуясь ей. Поэтому для своей исследовательской работы я и выбрала тему "Элементы теории графов и их применение".
Цель моей работы: познакомиться с основными положениями теории графов и рассмотреть применение теории к решению задач.
Для этого необходимо решить следующие задачи:
Изучить определение и некоторые свойства графа.
Познакомиться с известными задачами, решаемыми с помощью теории графов.
Подобрать задачи с практическим содержанием, которые можно решать с помощью графов.
Методы исследования:
Изучение литературы по данному вопросу;
Практическая работа (составление задач с практическим содержанием).
Гипотеза: теория графов действительно помогает решать различные практические задачи.
Информация о теории графов встречается в книгах таких авторов как Оре О. «Графы и их применение», Березина Л.Ю. «Графы и их применение».
Историческая справка
Изучая материалы по данной теме, я сделал вывод, что история теории графов началась с задачи про Кенигсбергские мосты. Город Кенигсберг (ныне Калининград) расположен на берегах реки Прегель (Преголи) и двух островах. Различные части города были соединены семью мостами. По воскресеньям горожане совершали прогулки по городу. Вопрос заключался в том, можно ли совершить прогулку таким образом, чтобы, выйдя из дома, вернуться обратно, пройдя в точности одни раз по каждому мосту?
Многие горожане заинтересовались этой задачей. Однако придумать решение никто не смог. Потом этот вопрос привлек внимание учёных разных стран. Решить проблему удалось знаменитому швейцарскому математику Леонарду Эйлеру(1707 1783). Причем, он решил не только эту конкретную задачу, но и придумал общий метод решения подобных задач: теорию графов. Эта теория является одной из немногих областей математики, дата рождения которых может быть указана. Первая работа о графах появилась в 1736 г. в публикациях Петербургской Академии наук. Эйлер является одной из колоритнейших фигур в истории науки. В 1727 г., когда ему едва исполнилось 20 лет, он был приглашен в Российскую Академию наук. Он уже изучил теологию, восточные языки и медицину, прежде чем целиком посвятил себя занятиям математикой, физикой и астрономией. Он добился блестящих успехов во всех этих областях и написал огромное количество работ. К тому времени, когда он написал работу о графах, он потерял зрение на один глаз, а к старости совершенно ослеп, но даже это не остановило потока его работ. Эйлер начал свою работу о графах как раз с рассмотрения так называемой «задачи о кёнигсбергских мостах».[4,с. 32]
Но своё название теория Эйлера получила на самом деле позже, так как результаты его работы более ста лет являлись, по сути, единственным достижением математической дисциплины, которую позднее и назвали теорией графов. Термин «граф» (от латинского слова «графио»  пишу) вошел в математический язык после выхода в свет известной монографии выдающегося венгерского математика Д. Кёнига в 1936г, в которой впервые графы рассматриваются как самостоятельные математические объекты независимо от их конкретного содержания.
Основные понятия
Графом называют фигуру, состоящую из точек и линий, связывающих эти точки. Точки называют вершинами графа, а линии, которые соединяют вершины, - рёбрами графа. На рисунке 1 изображён граф с шестью вершинами и шестью ребрами, на рисунке 2 - граф с тремя вершинами и тремя ребрами, а на рисунке 3 показан граф с семью вершинами и шестью ребрами (см. Приложение 1)
Примерами графов могут служить схема метрополитена, схемы железных или шоссейных дорог, структурные формулы молекул, аланы выставок и т. д., словом, схемы и планы (или карты) без указания масштабов, показывающие лишь связи между принадлежащими им объектами. ».[1, с. 9]
Вершины в графе могут отличаться друг от друга тем, скольким ребрам они принадлежат. Степенью вершины называется число ребер графа, которым принадлежит эта вершина. Вершины, из которых выходит нечётное число рёбер, называются нечётным вершинами, а вершины, из которых выходит чётное число рёбер, называются – чётными.
Путём от 13 EMBED Equation.3 1415до13 EMBED Equation.3 1415 в графе называется такая последовательность рёбер, ведущая от 13 EMBED Equation.3 1415к13 EMBED Equation.3 1415, в которой каждые два соседних ребра имеют общую вершину, и никакое ребро не встречается более одного раза. Вершины могут повторяться. Путь называется простым, если он не проходит ни через одну из вершин более одного раза.[1,с. 16]
На рисунке (см. Приложение 2) маршрут 13 EMBED Equation.3 1415 является путём, а маршрут 13 EMBED Equation.3 1415 не является путём. Маршрут 13 EMBED Equation.3 1415 - простой путь.
Циклом называется путь, в котором совпадают его начальная и конечная вершины.
Простым циклом в графе называется цикл, не проходящий ни через одну из вершин графа более одного раза.
Две вершины А и В графа называются связными, если в графе существует путь с концами А и В. Две вершины графа называются несвязными, если в графе не существует ни одного пути, связывающего их. На рисунке 4 в графе вершины А и В связные, а вершины А и Н несвязные. (см. Приложение 3)
Граф называемся связным, если каждые две вершины его связные. Граф называется несвязным, если хотя бы две вершины его несвязные. На рисунке 5 изображён связный граф, а на рисунке 6 – несвязный граф. (см. Приложение 3) [1, с.18]
Деревья
Деревом называется связный граф, не содержащий циклов. (см. Приложение 4) Из определения дерева вытекает также, что для каждой пары его вершин существуетединственная соединяющая их цепь или ветвь. Для того чтобы построить дерево, выберем какую-нибудь вершину13 EMBED Equation.3 1415Из 13 EMBED Equation.3 1415проведем ребра в соседние вершины 13 EMBED Equation.3 1415из них проведем ребра к их соседям 13 EMBED Equation.3 1415и т. д., как показано на рисунке в Приложении 5. Первоначально выбранная вершина А0называется корнем дерева; каждая вершина дерева может служить его корнем. Дерево можно построить, последовательно добавляя ребра в его вершинах. Это дает возможность сосчитать число ребер дерева. Простейшее дерево имеет только одно ребро; точнее говоря, оно состоит из двух вершин и одного ребра. Каждый раз, когда мы добавляем еще одно ребро в конце ветви, прибавляется также и вершина. [4,с. 47]

Задача про Кенигсбергские мосты
Вернёмся к задаче про Кенигсбергские мосты. Схематическая карта Кенигсберга изображена на рисунке 7 (см. Приложение 5). Четыре части города обозначены буквами А, В, С, D.Так как нас интересуют только переходы по мостам, мы можем считатьА, В, С, D вершинами, некоторого графа, ребра которого отвечают соответствующим мостам. Этот граф изображен на рисунке 8 (см. Приложение 5).
Эйлер показал, что этот граф не представляет собой единого цикла: иными словами, с какой бы вершины мы ни начали обход, мы не сможем обойти весь граф и вернуться обратно, не проходя никакого ребра дважды. Ведь если бы такой цикл существовал, то в каждой вершине графа было бы столько же входящих в нее ребер, сколько и выходящих из нее, т. е. в каждой вершине графа было бы четное число ребер. Однако это условие очевидно не выполнено для графа, представляющего карту Кенигсберга. [4,с. 34]
Решая эту задачу, Эйлер установил следующие свойства графа:
Если все вершины графа чётные, то можно одним росчерком (т.е. не отрывая карандаша от бумаги и не проводя дважды по одной и той же линии) начертить граф.
Граф с двумя нечётными вершинами тоже можно начертить одним росчерком. Движение нужно начинать от любой нечётной вершины, а заканчивать на другой нечётной вершине.
Граф с более чем двумя нечётными вершинами, невозможно начертить одним росчерком.
В задаче о Кенигсбергских мостах все четыре вершины соответствующего графа – нечётные, значит, нельзя пройти по всем мостам ровно один раз и закончить путь там же.
Графы изоморфные и плоские
В 1859 г. Английский математик Уильям Гамильтон выпустил в продажу головоломку. Она представляла собой деревянный додекаэдр (12-гранник), в вершинах которого вбиты гвоздики. Каждая из 20 вершин была помечена название одного из крупных городов мира – Дели, Брюссель, Кантон и т.д. Требовалось найти замкнутый путь, проходящий по рёбрам додекаэдра и позволяющий побывать в каждой его вершине по одному разу. Путь следовало отмечать с помощью шнура, зацепляя его за гвоздики.
Игрушка не имела такой популярности, какой ещё недавно пользовался «кубик Рубика», но оставила след в математике. Замкнутый путь по рёбрам графа, проходящий по одному разу через все вершины, называют гамильтоновым циклом. В отличии от эйлерова цикла условия существования на произвольном графе гамильтонова цикла до сих пор не установлены.
Два графа, одинаковы: у них одинаковое число вершин, и если две вершины одного графа соединены ребром, то вершины второго графа, имеющие те же номера, так же соединены ребром.( см. Приложение 6)
Это замечание более строго формулируется так: два графа называются изоморфными (от греч. «изос» - «равный» и «морфе» - «вид», «форма»), если между их вершинами можно установить взаимно однозначное соответствие, при котором вершинами, соединенным ребро, соответствуют вершины, также соединённые ребром. [6,с. 269] Бывают изоморфные графы такие, что у одного из них некоторые рёбра пересекаются, у второго же таких пересечений нет ( см. Приложение 6)
Граф, который можно нарисовать так, чтобы его рёбра не пересекались нигде, кроме вершин, называются плоским (см. Приложение 7).
Рассмотрим два графа, которые «не укладываются» на плоскость без пересечения ребер. Первый из них – граф с пятью вершинами, каждые две из которых соединены ребром. Такой граф называется полным (см. Приложение 7).
Второй граф, с шестью вершинами и девятью ребрами, носит название «домики – колодцы» (см. Приложение 7)
Плоские графы обладают многими интересными свойствами. Так, Эйлер обнаружил простую связь между количеством вершин (В), количеством ребер (Р) и количеством частей (Г), на которые граф разделяет плоскость:
В–Р+Г=2.
Задачи на применение теории графов
ЗАДАЧА 1.
Следующая задача. 6 человек из нашего класса захотели поздравить друг друга с новым годом. Сделать это решили с помощью SMS - сообщений. Сколько всего SMS-сообщений было отправлено?
Решение:
Каждый из шести человек будет отправлять сообщения 5 другим людям. Построим соответствующий граф: точками обозначим учеников класса, а рёбра будут означать пары SMS-сообщений, посланных двумя учениками друг другу.(см. Приложение 8). Таким образом, подсчитав количество всех рёбер графа, получается, что эти 6 человек отправят 30 SMS-сообщений, так как каждое ребро считаем 2 раза.

ЗАДАЧА 2.Приведу еще одну задачу. Каждый раз, приходя в школьную столовую и изучив меню, я задумываюсь, что мне взять на обед. А однажды я решила подсчитать, сколько же различных способов пообедать существует? Меню этого дня:
суп - борщ
салаты: витаминный, винегрет, зимний
греча
жаренная курица
котлета
чай
сок
Решение: Для решения этой задачи построим граф в виде дерева, где точки – это названия блюд, а ребра показывают, какие блюда куплены вместе друг с другом. Для удобства салаты обозначены: витаминный - С1, винегрет - С2, зимний - С3 (см. Приложение 9). Данный граф позволяет легко ответить на поставленный вопрос:подсчитаем количество вершин, из которых не выходит больше ни одного ребра. Для указанного меню существует 12 различных способов пообедать.

ЗАДАЧА 3.
Ко мне обратились знакомые с просьбой: решить задачу для 2 класса.[5, с.20]

Решение: Представив каждую фигуру в виде графа (см. Приложение 10), подсчитав степень каждой вершины, можно сделать вывод. В первом графе две вершины четные и две нечетные, значит, начертить эту фигуру одним росчерком можно. Начинать нужно с вершины 2 или 3. Во втором графе все четыре вершины нечетные, значит, начертить её одним росчерком нельзя.
ЗАДАЧА 4.
В шахматном турнире по круговой системе, по которой каждый участник встречается с каждым, участвуют 7 школьников. Известно, что в настоящий момент Ваня сыграл 6 партий, Толя – 5,Леша и Дима –по 3, Семен и Илья – по 2, Женя- 1. С кем играл Леша?
Решение: Поставим в соответствие каждому игроку точку плоскости – вершину графа. Если два игрока встретились между собой, то соединим соответствующие вершины линией – ребром графа. Таким образом, мы построим граф встреч игроков. Пусть в этом графе вершина 1 соответствует Ване, вершина 2 – Толе, вершина 3 – Леше, вершина 4 – Диме, вершина 5 – Семену, вершина 6 – Илье и вершина 7 – Жене. Поскольку Ваня провел 6 встреч, то степень вершины 1 равна 6, и эту вершину соединим со всеми вершинами графа. Степень вершины 2 должна быть равна 5, так как Толя провел 5 встреч. Из вершины 2 уже выходит 1 ребро. Оставшиеся 4 ребра проведем из 2 в вершины 3, 4, 5 и 6, поскольку вершина 7, степень которой равна 1 (Женя провел одну встречу), соединена уже ребром с вершиной 1. Теперь вершины 5 и 6 соответствующие Семену и Илье, должны иметь степень 2, так как эти участники провели по две встречи. Вершины 3 и 4 соединим ребром, поскольку они должны иметь степени 3, так как Леша и Дима провели по 3 встречи( см. Приложение 11) Поэтому Леша, которому соответствует вершина 3, встретился с Ваней, Толей и Димой, которым соответствуют вершины 1, 2 и 4.
Заключение
Занимаясь данной темой, я поняла, что во многих областях человеческой жизни можно найти проблему или задачу, решаемую с помощью графов.
В настоящее время теория графов нашла очень широкое применение в:
1. В микроэлектронике – при разработке топологии микросхем.2. При разработке сложных электрических схем и схем их монтажа в электротехнических шкафах, в электрощитах.3. В химии – при разработке новых сложных молекулярных соединений и т.п.4. Физике – при описании и анализе схем развития квантовых процессов. 5. При разработке коммуникационных систем различного назначения.6. В транспортных системах – как для изучения самих систем, так и при составлении оптимальных маршрутов доставки грузов – логистика. 7. В информатике и программирование – при разработке алгоритмов расчетов, программ.8. В экономике и планировании – в виде сетевых графиков.и т.д.
Я пришла к выводу, что метод графов прост и удобен, поэтому так распространен. Графы могут помочь и при решении задач на уроках математики, на олимпиадах и при сдаче экзаменов.
Теория графов очень полезна в жизни, и мне было интересно узнать, что такая теория существует. Надеюсь, что знакомство с ней поможет мне как на уроках математики, так и в жизни.
Библиографический список.
Березина Л.Ю. Графы и их применение. – М.: Просвещение, 1979г
Графы и кратчайшие расстояния в них. – Математика. Приложение к газете «1 сентября». – 2001 - №15, 16
Берж К. Теория графов и её применение. –М.: Иностранная литература, 1962г
Оре О. Графы и их применение. – М.: Мир, 1965
Холодова О.А. Юным умникам и умницам. Информатика, логика, математика. Рабочая тетрадь. 2 кл. – М.: РОСТ книга, 2013
Энциклопедия для детей. Т. 11 Математика /Глав. редактор М.Д. Аксенова. - М.: Аванта+, 2000
Интернет ресурсы:
[ Cкачайте файл, чтобы посмотреть ссылку ]
[ Cкачайте файл, чтобы посмотреть ссылку ]
[ Cкачайте файл, чтобы посмотреть ссылку ]
Приложения
1.Виды графов.
Граф с шестью вершинами и шестью ребрами.

Рисунок 1.
Граф с тремя вершинами и тремя ребрами

Рисунок 2
Граф с семью вершинами и шестью ребрами

Рисунок 3


2. Путь. Простой путь





3.Связные и несвязные графы











4. Граф - дерево










5.Мосты Кенигсберга









6.Изоморфные графы
[ Cкачайте файл, чтобы посмотреть картинку ]

7.Плоские и полные графы

8.Подсчет количества отправленных SMS-сообщений

9.Количество различных способов пообедать


10. Графы к задаче для 2 класса

11. Граф к задаче про шахматы









13PAGE \* MERGEFORMAT141715




Root Entry