Графы

Муниципальное бюджетное образовательное учреждение

средняя образовательная школа № 85

с углубленным  изучением отдельных предметов.

Научное общество учащихся

Графы

Выполнила:

Кулемалина Анастасия

ученица 8  «А» класса

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

Репьева Марина Вениаминовна

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

Нижний Новгород

2014г.

Содержание.

Введение

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

1.  Основные понятия
2.  Плоские графы
3.  Графы с цветными рёбрами
4.  Ориентированные графы

2. Применение теории графов

1.  Математические задачи, решаемые с помощью графов
2.  Игры и графы
3.  Головоломки, решаемые с помощью графов

Заключение

Список используемой литературы

Введение.

Тема моей научной работы «Графы и их применение».

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

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

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

Цель моей работы:

                 - Изучить теорию графов

                 - Исследовать возможности применения её к решению математических и логических задач

Для достижения цели мне нужно:

                  - Подобрать литературу по исследуемой теме

                   - Рассмотреть основы теории графов

                   - Выделить основные типы задач, решаемых с помощью графов

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

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

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

            1                           2                        3                           4

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

На рис. 4, вершина А имеет степень 4, вершина И – степень равную 1, вершина С – 0.

Вершина, степень которой равна 0 называется изолированной. Вершина называется нечётной, если её степень число нечётное. Вершина называется чётной, если её степень число чётное. Вершина А – чётная, В – нечётная.

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

                     5                                    6                               7                                8

В изображённом на рис. 5 графе путь от вершины А до вершины Е происходит так: [A, B]; [B, C]; [C, D]; [D, E]. Если путь не проходит ни через одну из вершин более 1 раза, он называется простым.

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

Введение понятия «путь» подвело нас к важному в теории графов понятию «связность». Дадим определение связности вершин и связности графа.

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

На рис. 6 Вершины А и В связны, а В и Е – несвязные. Примером связного графа может служить рис.5, а несвязного – рис.8.

Выделим такое понятие как «отношение» в графе, оно наглядно иллюстрируется с помощью понятия «квадрат множества».

 Элементы а и b (на рисунке они могут быть вершинами графа) некоторого множества, взятые в определённом порядке, называются упорядоченной порой. Обозначают её [a, b]. Возможны и такие пары, в которых оба элемента совпадают, т.е. пары вида [a, a]. Упорядоченный пары вида [a, b] и [b, a] считаются различными, если a=b. Две упорядоченные пары  [a, b] и [c, d]  считаются равными, если a=с и b=d.  Множество возможных пар элементов множества M называется квадратом множества М. Его принято обозначать М*М или М2.

Пусть множество М = [a, b, c]. Выпишем возможные пары элементов этого множества. В этом нам поможет таблица на рис.6 выпишем «координаты» всех точек:[a, a], [a, b], [a, c], [b, a], [b, b], [b, c], [c, a], [c, b], [c, c]. Полученное множество пар и будет квадратом множества М.

1.2. Плоские графы.

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

              9                       10                          11                                       12

Граф, изображённый на рис.9 – плоский, а граф, изображённый на рис.10 – неплоский. Любые попытки нарисовать его плоским обречены на неудачу. Граф на рис.11  вроде бы неплоский, но при внимательном изучении оказывается, что этот граф тот же, что и граф на рис.9. Говорим, что рис.9 – плоское представление графа. В качестве характеристики плоского представления графа вводится понятие «грань». Гранью в плоском представлении графа называется часть плоскости, ограниченная простым циклом и не содержащая внутри других циклов. На рис.12 изображено плоское представление графа с четырьмя гранями:[1,7,4,1], [1,3,2,4,1], [1,2,3,1], [2,6,5,4,2].

1.3. Графы с цветными рёбрами.

Из-за разных отношений между множествами пар элементов в графе появились графы, которые называются графами с цветными рёбрами. Эти графы изображены на рис.13 и 14.

                    13                                             14

Эти графы помогают решать немало разных задач.

Графы с цветными рёбрами имеют свойства:

Свойство 1. Любая вершина полного графа с 6 или более вершинами и рёбрами двух цветов принадлежит по меньшей мере трём рёбрам одного цвета.

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

Свойство 2. В любом полном графе с 6 или более вершинами и рёбрами 2 цветов найдётся по меньшей мере один треугольник с одноцветными сторонами.

Свойство 3. Если в полном графе с 5 вершинами и рёбрами двух цветов не найдётся треугольника с одноцветными сторонами, то граф можно изобразить в виде «пятиугольника» с красными сторонами и синими диагоналями.

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

Свойство 5. В полном графе с 17 или более вершинами и рёбрами 3 цветов всегда найдётся по меньшей мере 1 треугольник с одноцветными сторонами.

1.4. Ориентированные графы.

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

            15                              16                                        17

На рисунках ориентированное ребро изображают стрелкой. Такую «стрелку» называют дугой. Говорят, что ориентированное ребро DC выходит из вершины D и входит в вершину C. Граф, все рёбра которого не ориентированы, называется неориентированным графом. Ориентированный граф изображён на рис.15 . Одна и та же вершина может служить началом для одних рёбер и концом для других. Различают 2 степени вершины: степень входа и степень выхода. Степенью выхода вершины А ориентированного графа называется число выходящих из А рёбер. Степенью входа вершины А называется число входящих в А рёбер. На рис.17 степень выхода вершины А равна 3, а степень выхода – 0. В ориентированных графах в зависимости от сочетания степеней входа и выхода рассматриваются 3 случая вершины. Изолированной вершиной называется вершина, у которой степени входа и выхода равны 0. Источником называется вершина, степень выхода  которой положительна, а степень входа равна 0. Стоком называется вершина, степень входа которой положительна, а степень выхода равна 0(рис. 16 вершина А – источник, Вершина D – сток, вершина С – изолирована).

Путём в ориентированном от вершины А1  до вершины Аn называется последовательность ориентированных рёбре, ведущая от А1 до Аn так, что конец каждого предыдущего ребра совпадает с началом, и ни одно ребро не встречается более одного раза. Если в ориентированном графе нашёлся путь от D до С, то обратного пути может и не быть. Рис. 17 для вершины А достижима вершина B, но для В недостижима А. Простым путём в ориентированном графе называется путь в котором ни одна вершина не содержится более одного раза. Замкнутый путь в ориентированном графе называется циклом. Длиной пути называется число рёбер в этом пути. Расстояние от А до В в ориентированном графе называется длина наикратчайшего пути от А до В. Если пути от А до В не существует, то расстояние от А до В называется бесконечным. На рис.17 расстояние от А до В равно 1.

2.Применение теории графов.

2.1.Математические задачи, решаемые с помощью графов.

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

Задача 1.

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

Решение.

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

Ответ:

Имение Е принадлежит Манилову, D – Коробочке, С – Ноздрёву, А – Собакевичу, В – Плюшкину, М – Тентетникову, F – Бетрищеву, Н – Петуху, К – Констанжогло, О – Кошкареву.

              18                                   19                                       20

Задача 2.

Утверждают, что в одной компании из пяти человек каждый знаком с двумя и только с двумя другими. Возможна ли такая компания?

Решение.

Каждого из этой компании изобразим на рисунке кружком Если двое знакомы, соединим соответствующие кружки отрезком(рис. 21). Из рассматриваемой компании нельзя выделить ни «четырёхугольник», ни «треугольник», поскольку тогда из оставшихся нельзя будет составить компанию, удовлетворяющую условию, т.е. схема знакомства единственная.

         21                22

Задача 3.

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

          Решение.(рис.22)

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

Рассмотрим одну из точек, например, А. Из неё выходит 5 отрезков, значит, хотя бы 3 из них будут одинаковы. Пусть отрезки АБ, АГ и АД – красные, тогда отрезки БГ, БД и ГД обязательно будут синими, ибо не может быть 3 человек, которые были бы знакомы друг с другом(на рисунке не может быть треугольника, все стороны которого красные отрезки). Но это значит, что Б, Г и Д незнакомы друг с другом. Аналогично рассматриваются другие случаи.

Задача 4.

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

Решение(рис.23)

Обозначим каждого одноклассника точкой и соединим эти точки отрезками, тогда граф для решения этой задачи будет иметь вид:

         23

Задача 5.

Андрей, Борис, Виктор и Григорий играли в шахматы. Каждый сыграл с каждым по одной партии. Сколько партий было сыграно?

Решение(рис.24)

Обозначим каждого из ребят точкой и соединим эти точки отрезками, тогда решение этой задачи будет представлено на этом графе:

            24

2.2.Игры и графы.

Ещё одна наука или, точнее, раздел математики, в котором применяются графы для осуществления перебора – это теория игр. Используем для примера игру «Одинокий король»

Задача.

Имеется доска N*N, состоящая из чёрных и белых клеток(не обязательно в шахматном порядке). В нижнем левом углу стоит белый король, который умеет ходить на 1 клетку вправо или вверх, но только по белым клеткам. Двое игроков ходят этим королём по очереди. Проигрывает тот, кому некуда ходить.

Решение.

Разберём эту задачу на доске *5, которая изображена на рис.23.

                23                                 24

Возьмём клетки доски в качестве вершин графа. 2 вершины соединены дугами, если с одной на другую можно перейти. Будем ставить на клетку «+», если на неё следует ходить, чтобы выиграть, и «-», если на неё не следует ходить. Очевидно, что вершины, не имеющие исходящих рёбер, являются выигрышными, - если игрок делает ход на такую клетку, то его противнику будет некуда ходит. Поэтому на соответсующие клетки сразу поставим «+». Во все клетки, из которых существует ход в выигрышную клетку, являются проигрышными и поэтому ставим в них «-»(рис.24). Из этого рисунка видно, что выигрывает игрок, который ходит первым. Для этого ему нужно сделать первый ход направо. Если по ошибке сделать ход наверх, то может выиграть второй игрок.

2.3.Головоломки, решаемые при помощи графов.

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

                    25                                            26

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

К таким головоломкам относится всем известная головоломка «Паромщик». В этой головоломке требуется перевезти с одного берега на другой волка, козу и капусту так, чтобы коза не съела капусту, а волк – козу. Введём обозначения: В – волк, М - мешок с капустой, К – коза. Тогда граф, соответствующий решению этой головоломки, будет иметь вид рис.26.

Заключение.

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

В ходе работы были даны определения таким понятиям как:

• Граф
• Путь в графе
• Связность
• Грань

Была проведена классификация графов на группы:

• Плоские
• С цветными рёбрами
• Ориентированные

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

Список используемой литературы.

1.Графы и их применение/ Березина Л.Ю. – М.: 1979

1. Журнал «квант» №4 1994; №7 1981
2. Информатика 7-9 класс. Базовый курс. Теория./ Под ред. Макаровой Н.В. – СПб.: 2001
3. Информатика 9 класс/ Под ред. Макаровой Н.В. – СПб.:1999
4. Информатика 10 класс./Семкин И.Г. – М.: 2001