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

Опубликовано Переломова Марина Анатольевна вкл 08.11.2014 - 20:50

Автор:

Корниенко Григорий

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

Скачать:

Вложение	Размер
kornienkogrisha_mbou_sosh_5.docx	882.31 КБ

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

VII городская конференция

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

Секция точных наук

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

Работу выполнил:

Корниенко Григорий Игоревич

ученик 6 б класса

МБОУ «СОШ №5» г.Архангельска

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

Переломова Марина Анатольевна,

I квалификационная категория,

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

г.Архангельск

2014г

Оглавление

Введение……………………………………………………………………………...…..3
Историческая справка…………………………………………………………………...3
Основные понятия………………………………………………….……………………4
Деревья…………………………….……….……………………………………………..5
Задача про Кенигсбергские мосты ……………………………………………………..5
Задачи на применение теории графов………………………………………………….6
Заключение……………………………………………………………………………… 9
Библиография…………………………………………………………………………...10
Приложения …………………………………………………………………………….11

Виды графов………………………………………………………………………...11
Путь. Простой путь…………………………………………………………………11
Связные и несвязные графы……………………………………………………….12
Мосты Кенигсберга………………………………………………………………...12
Граф – дерево……………………………………………………………………….12
Карта Архангельска………………………………………………………………...13
Граф,соответствующий архангельским мостам….……………………………...13
Дерево для подсчета количества различных обходов архангельских мостов….13
Подсчет количества отправленных SMS-ок……………………………………..14
Меню………………………………………………………………………………...14
Количество различных способов пообедать……………………………………...14
Графы к задаче для 2 класса………………………………………………………15

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Деревья

Деревом называется связный граф, не содержащий циклов. Из определения дерева вытекает также, что для каждой пары его вершин существует единственная соединяющая их цепь или ветвь. Для того чтобы построить дерево, выберем какую-нибудь вершину Из проведем ребра в соседние вершины из них проведем ребра к их соседям и т. д., как показано на рисунке в Приложении 5. Первоначально выбранная вершина А0 называется корнем дерева; каждая вершина дерева может служить его корнем. Дерево можно построить, последовательно добавляя ребра в его вершинах. Это дает возможность сосчитать число ребер дерева. Простейшее дерево имеет только одно ребро; точнее говоря, оно состоит из двух вершин и одного ребра. Каждый раз, когда мы добавляем еще одно ребро в конце ветви, прибавляется также и вершина. [4, с. 47]

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

Вернёмся к задаче про Кенигсбергские мосты. Схематическая карта Кенигсберга изображена на рисунке 7 (см. Приложение4). Четыре части города обозначены буквами А, В, С, D. Так как нас интересуют только переходы по мостам, мы можем считать А, В, С, D вершинами, некоторого графа, ребра которого отвечают соответствующим мостам. Этот граф изображен на рисунке 8 (см. Приложение 4).

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

Решая эту задачу, Эйлер установил следующие свойства графа:

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

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

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

ЗАДАЧА 1.

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

Решение.

Чтобы ответить на поставленный вопрос, я поступил так же как и Эйлер. Для исследования я выбрал следующие округа: Соломбальский, Октябрьский, Ломоносовский, Майская Горка, Исакогорский и часть Варавино-Фактория (см. Приложение 6). Сушу сжал в точки, а мосты представил в виде отрезков. Таким образом, я получил граф, состоящий из 6 вершин и 9 ребер. (см. Приложение 7 рис 1).Точки обозначают: «С» – Соломбала, «К» - Кемский посёлок, «М» - Мосеев остров, «Г» - центральная часть города, «Л» - Левый берег, «Кр» - Краснофлотский остров. Подсчитаем степень каждой вершины. Степ.С = 4, степ.К = 3, степ. М = 3, степ.Г = 2, степ.Л = 2, степ. Кр. = 2. Таким образом, две вершины имеют нечётную степень.

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

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

ЗАДАЧА 2.

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

Решение.

Используя граф, построенный в задаче 1, можно просчитать количество возможных способов обойти все мосты. Для этого пронумеруем все рёбра в графе от 1 до 9. (см. Приложение 7 рис 2). Построим дерево возможных вариантов для треугольника КМС и дерево для треугольника ГЛКр. (см. Приложение 8)

В каждом дереве подсчитаем количество вершин, из которых не выходит больше ни одного ребра. Это число и будет количеством путей, которые существует, чтобы обойти треугольник КМС. Если начинать из точки К, то, чтобы попасть в точку М, есть 12 различных путей без повторения рёбер. Чтобы обойти треугольник ГЛКр, существует 2 различных пути. Таким образом, при каждом из 12 способов обойти треугольник КМС существует два способа обойти треугольник ГЛКр. Значит, всего существует способа пройти от точки К до точки Г, пройдя по всем рёбрам графа только по одному разу.

Если же мы начнём обход из точки Г и закончим в точке К, то у нас есть так же 24 различных способа обойти все рёбра.

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

ЗАДАЧА 3.

Следующая задача. 6 человек из нашего класса захотели поздравить друг друга с новым годом. Сделать это решили с помощью SMS-ок. Сколько всего SMS-ок было отправлено?

Решение:

Каждый из шести человек будет отправлять сообщения 5 другим людям. Построим соответствующий граф: точками обозначим учеников класса, а рёбра будут означать пары SMS-ок, посланных двумя учениками друг другу. (см. Приложение 9). Таким образом, подсчитав количество всех рёбер графа, получается, что эти 6 человек отправят 30 SMS-сообщений, так как каждое ребро считаем 2 раза.

ЗАДАЧА 4.

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

Решение: Для решения этой задачи постоим граф в виде дерева, где точки – это названия блюд, а ребра показывают, какие блюда куплены вместе друг с другом. Для удобства напитки обозначены цифрами: 1- чай, 2 – кофе, 3 – сок, 4 – морс. (см. Приложение 11). Данный граф позволяет легко ответить на поставленный вопрос: подсчитаем количество вершин, из которых не выходит больше ни одного ребра. Для указанного меню существует 128 различных способов пообедать.

ЗАДАЧА 5.

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

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

Заключение

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

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

Библиография.

Березина Л.Ю. Графы и их применение. – М.: Просвещение, 1979г
Графы и кратчайшие расстояния в них. – Математика. Приложение к газете «1 сентября». – 2001 - №15, 16
Берж К. Теория графов и её применение. –М.: Иностранная литература, 1962г
Оре О. Графы и их применение. – М.: Мир, 1965 г
Холодова О.А. Юным умникам и умницам. Информатика, логика, математика. Рабочая тетрадь. 2 кл. – М.: РОСТкнига, 2013г
Интернет ресурсы:

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