Инфоурок / Математика / Научные работы / Исследовательская работа ученицы 8 класса "Элементы теории графов и их примение"
Обращаем Ваше внимание: Министерство образования и науки рекомендует в 2017/2018 учебном году включать в программы воспитания и социализации образовательные события, приуроченные к году экологии (2017 год объявлен годом экологии и особо охраняемых природных территорий в Российской Федерации).

Учителям 1-11 классов и воспитателям дошкольных ОУ вместе с ребятами рекомендуем принять участие в международном конкурсе «Законы экологии», приуроченном к году экологии. Участники конкурса проверят свои знания правил поведения на природе, узнают интересные факты о животных и растениях, занесённых в Красную книгу России. Все ученики будут награждены красочными наградными материалами, а учителя получат бесплатные свидетельства о подготовке участников и призёров международного конкурса.

ПРИЁМ ЗАЯВОК ТОЛЬКО ДО 21 ОКТЯБРЯ!

Конкурс "Законы экологии"

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

библиотека
материалов

17


XVIII муниципальный конкурс исследовательских работ учащихся

Управление образования администрации Карагайского муниципального района

МОУ «Карагайская средняя общеобразовательная школа №2»


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







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



Автор: Попова Алина Андреевна,

ученица 8б класса

Руководители: Волегова Елена Павловна, учитель математики









Карагай – 2016

Оглавление

Оглавление 2

Введение 3

Историческая справка 4

Основные понятия 5

Деревья 6

Задача про Кенигсбергские мосты 7

Графы изоморфные и плоские 8

Задачи на применение теории графов 9

Заключение 12

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

Приложения 14

1.Виды графов. 14

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

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

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

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

6.Изоморфные графы 16

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

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

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

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

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


Введение

На уроке математики в 5 классе, помню, мы решали задачу на определение количества возможных чисел, которые можно составить из пяти различных цифр без повторения. Я попыталась перебрать все возможные числа, но поняла, что это может занять достаточно много времени. Учитель же предложил нарисовать что-то вроде схемы, состоящей из точек и отрезков, исходящих из этих точек. С помощью этой схемы мы достаточно быстро сумели подсчитать количество всевозможных чисел. Учитель назвал полученную схему графом. Она сказала, что существует целая теория графов, которая позволяет решать большой круг задач. В дальнейшем все чаще на уроках мы встречали такие задачи. Даже участвуя в различных математических конкурсах и олимпиадах, я часто сталкиваюсь с теорией графов. Мне стало очень интересно, что это за теория, и какие задачи можно решать, пользуясь ей. Поэтому для своей исследовательской работы я и выбрала тему "Элементы теории графов и их применение".

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

Для этого необходимо решить следующие задачи:

  • Изучить определение и некоторые свойства графа.

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

  • Подобрать задачи с практическим содержанием, которые можно решать с помощью графов.

Методы исследования:

  1. Изучение литературы по данному вопросу;

  2. Практическая работа (составление задач с практическим содержанием).

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

Информация о теории графов встречается в книгах таких авторов как Оре О. «Графы и их применение», Березина Л.Ю. «Графы и их применение».

Историческая справка

Изучая материалы по данной теме, я сделал вывод, что история теории графов началась с задачи про Кенигсбергские мосты. Город Кенигсберг (ныне Кали­нинград) расположен на берегах реки Прегель (Преголи) и двух островах. Различные части города были соединены семью мостами. По воскресеньям горожа­не совершали прогулки по городу. Вопрос заключался в том, можно ли совершить прогулку таким образом, чтобы, выйдя из дома, вернуться обратно, пройдя в точности одни раз по каждому мосту?

Многие горожане заинтересовались этой задачей. Однако придумать решение никто не смог. Потом этот вопрос привлек внимание учёных разных стран. Решить проблему удалось знаменитому швейцарскому математику Леонарду Эйлеру(1707— 1783). Причем, он решил не только эту конкретную задачу, но и придумал общий метод решения подобных задач: теорию графов. Эта теория является одной из немногих обла­стей математики, дата рождения которых может быть указана. Первая работа о графах появилась в 1736 г. в публикациях Петербург­ской Академии наук. Эйлер является одной из колоритнейших фигур в истории науки. В 1727 г., когда ему едва исполнилось 20 лет, он был приглашен в Российскую Академию наук. Он уже изучил теоло­гию, восточные языки и медицину, прежде чем цели­ком посвятил себя занятиям математикой, физикой и астрономией. Он добился блестящих успехов во всех этих областях и написал огромное количество работ. К тому времени, когда он написал работу о графах, он потерял зрение на один глаз, а к старости совершенно ослеп, но даже это не остановило потока его работ. Эйлер начал свою работу о графах как раз с рассмотрения так называемой «задачи о кёнигсбергских мостах».[4,с. 32]

Но своё название теория Эйлера получила на самом деле позже, так как результаты его работы более ста лет являлись, по сути, единственным достижением математической дисциплины, которую позднее и назвали теорией графов. Термин «граф» (от латинского слова «графио»  пишу) вошел в математический язык после выхода в свет известной монографии выдающегося венгерского математика Д. Кёнига в 1936г, в которой впервые графы рассматриваются как самостоятельные математические объекты независимо от их конкретного содержания.

Основные понятия

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

Примерами графов могут служить схема метрополитена, схе­мы железных или шоссейных дорог, структурные формулы молекул, аланы выставок и т. д., словом, схемы и планы (или карты) без указания масштабов, показывающие лишь связи между принад­лежащими им объектами. ».[1, с. 9]

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

Путём от hello_html_m70c04394.gifдоhello_html_315e555a.gif в графе называется такая последовательность рёбер, ведущая от hello_html_m70c04394.gifкhello_html_315e555a.gif, в которой каждые два соседних ребра имеют общую вершину, и никакое ребро не встречается более одного раза. Вершины могут повторяться. Путь называется простым, если он не проходит ни через одну из вершин более одного раза.[1,с. 16]

На рисунке (см. Приложение 2) маршрут hello_html_m7f74dc.gif является путём, а маршрут hello_html_6fc02155.gif не является путём. Маршрут hello_html_m3a5ce268.gif - простой путь.

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

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

Две вершины А и В графа называются связными, если в графе существует путь с концами А и В. Две вершины графа называются несвязными, если в графе не суще­ствует ни одного пути, связывающего их. На рисунке 4 в графе вершины А и В — связные, а вершины А и Н — несвязные. (см. Приложение 3)

Граф называемся связным, если каждые две вершины его связные. Граф называется несвязным, если хотя бы две вершины его несвязные. На рисунке 5 изображён связный граф, а на рисунке 6 – несвязный граф. (см. Приложение 3) [1, с.18]

Деревья

Деревом называется связный граф, не содер­жащий циклов. (см. Приложение 4) Из определения дерева вытекает также, что для каждой пары его вершин существуетединственная соединяющая их цепь или ветвь. Для того чтобы построить дерево, выберем какую-нибудь вершинуhello_html_bb43595.gifИз hello_html_bb43595.gifпроведем ребра в соседние вершины hello_html_5eed35f4.gifиз них проведем ребра к их со­седям hello_html_m11662593.gifи т. д., как показано на рисунке в Приложении 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]

hello_html_2ed2dd2e.gif

Решение: Представив каждую фигуру в виде графа (см. Приложение 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. В экономике и планировании – в виде сетевых графиков.
и т.д.

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

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

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

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

  2. Графы и кратчайшие расстояния в них. – Математика. Приложение к газете «1 сентября». – 2001 - №15, 16

  3. Берж К. Теория графов и её применение. –М.: Иностранная литература, 1962г

  4. Оре О. Графы и их применение. – М.: Мир, 1965

  5. Холодова О.А. Юным умникам и умницам. Информатика, логика, математика. Рабочая тетрадь. 2 кл. – М.: РОСТ книга, 2013

  6. Энциклопедия для детей. Т. 11 Математика /Глав. редактор М.Д. Аксенова. - М.: Аванта+, 2000

  7. Интернет ресурсы:

http://vuz.exponenta.ru/pdf/L10.html

http://ru.wikipedia.org/wiki/%D2%E5%EE%F0%E8%FF_%E3%F0%E0%F4%EE%E2

http://zaykan.narod.ru/teor/inf/intuit/graphsuse_4.html

Приложения

1.Виды графов.

Граф с шестью вершинами и шестью ребрами.

hello_html_m1cc5efaf.jpg

Рисунок 1.

Граф с тремя вершинами и тремя ребрами

hello_html_731f036f.jpg

Рисунок 2

Граф с семью вершинами и шестью ребрами

hello_html_6003deb2.jpg

Рисунок 3





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


hello_html_ed1e2a1.png




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


hello_html_726a6c81.png










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

hello_html_1bb12ea9.png










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




hello_html_2cedd060.png






6.Изоморфные графы

hello_html_11b4ce61.png

hello_html_4538db3b.png

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

hello_html_m9f330f9.png

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

hello_html_7ceff1f6.png

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

hello_html_1052e2e6.jpg


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

hello_html_1d4ccf9b.png

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

hello_html_m274bc8.jpg

Общая информация

Номер материала: ДВ-561454

Похожие материалы