Исследовательская работа по математике по теме "Графы и математика"

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

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

городского округа г.Выкса Нижегородской области

Графы в математике

Физико-математическое отделение

Секция математическая

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

                                                        ученица 9 класса

         Дегтева Алёна Александровна,

                                                                                15 лет

г.Выкса

2015год

Оглавление:

o   Аннотация……………………………………………………………..….  3

o   Введение………………………………………………………………..…  4

o   Глава1. Обзор литературы……………………………………………..  5

o   Глава 2. История теории графов……………………………………...  6

2.1 Из истории возникновения графов………………………………..   6-8

2.2. Пионеры теории графов…………………………………………..….  9

2.3. Азы теории графов……………………………………………..…10-13

2.4. Виды  графов……………………………………………………..…. 13

    2.2.1. Геометрические  и полные графы………………………..…13-15

    2.2.2. Плоские графы…………………………………………….…15-18

    2.2.3 Деревья…………………………………………………...........18-20

              2.2.4.Эйлеровы графы…………………………………………........20-22

o   Глава 3. Результаты и их обсуждения…………………………… 23-24

o   Заключение…………………………………………………………..….  25

o   Список использованной литературы……………………….………   26

o   Приложения …………………………………………………..………..   27

Аннотация

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

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

Мною поставлены следующие задачи:

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

- научиться решать задачи с помощью графов;

- подобрать графы, согласно их классификации;

- придумать интересные задания для одноклассников.

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

Анализ информации следующих источников:

- научной, методической литературы;

- посещение библиотеки, просмотр Интернет-сайтов;

- проведение анкетирования.

На основе этих методов и поставленных мною целей, я получила следующие результаты своей работы:

- собран материал о графах;

- мною подобраны различные графы, согласно их видам;

-создано наглядное пособие «Решаем задачи с помощью графов», презентация.

Введение

Хорошо да  коротко – вдвойне  хорошо.

Народная мудрость

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

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

Проблема: Отсутствие информации у обучающихся о методах решения задач с помощью графов.

Гипотеза:  Использование теории графов способствует успешному решению логических задач.

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

Задачи:

- изучить понятие графа;

- изучить элементы теории графов для решения задач;

- разобрать решение различных видов задач;

- выявить роль графов в математике.

Над своим исследованием я работала около трёх месяцев. Посещала школьную библиотеку. Искала информацию, используя ресурсы Интернет-сайтов.

Глава 1. Обзор литературы.

    В книге «Графы и их применение» О.Оре [1] я узнала, что графы – сети линий, соединяющих заданные точки, широко применяются в разных разделах математики и в приложениях. Я выбрала данную книгу, так как для ее понимания вполне достаточны минимальные предварительные знания, практически не превышающие курса математики средней школы. Здесь рассматриваются основные понятия теории графов, виды графов, примеры задач, решаемых с помощью графов. Также из этой книги я узнала, что теория графов появилась благодаря одной занимательной задаче о Кёнигсбергских мостах, которую решил Леонард Эйлер. Именно он считается отцом теории графов.

   В книге «Теория графов» Ф.Харари [2] я рассмотрела эйлеровы графы, узнала, какие графы можно считать эйлеровыми, как решаются задачи на эйлеровы графы.

   Из книги «Карты метро и нейронные сети. Теория графов» Клауди Альсина [3] я узнала о том, что еще до создания теории графов многие ученые совершенно независимо друг от друга использовали понятия, которые впоследствии были объединены в теорию графов. Развитию теории графов в немалой степени способствовали такие выдающиеся  ученые , как Уильям Томас Татт, Фрэнк Харари, Эдсгер Вибе Дейкстра и Пол Эрдёш. Теория графов приобрела большую известность благодаря их исследованиям, нестандартным задачам и написанными справочниками.

    В журнале «Математика для школьников» [4] рассматриваются различные логические задачи, решаемые методом графов. Некоторые из них я использовала для создания наглядного пособия «Решаем задачи с помощью графов».

 Также задачи для самостоятельного решения я взяла из книги М.И.Зайкина  «Математический тренинг» [5].

Глава 2. История теории графов.

Теория графов - (англ. theory, graph; нем. Graphentheorie) в узком смысле - раздел дискретной математики, одна из ветвей дискретной топологии, в широком смысле - теория сетей, наука о топологических формах, сетевых моделях представления любого процесса или системы. Основным объектом исследования этой теории являются графы.

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

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

Графом называется двойка вида G = (X, A),  где X = {x_i}, i = 1, 2, ..., n – множество вершин графа, A = {a_i}, i = 1, 2,... , m – множество ребер графа.

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

2.1. Из истории возникновения графов

   Теория графов появилась благодаря одной занимательной задаче, которую решил Леонард Эйлер. История гласит, что в 1736 году блестящий математик остановился в Кёнигсберге (в настоящее время  - Калининград). Город был разделен рекой на четыре части, которые были соединены семью мостами.

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

    Эйлер писал об этой задаче: «Насколько я понимаю, это задача широко известна. Она формулируется так: в прусском городе Кёнигсберге есть остров под названием Кнайпхоф, окруженный двумя рукавами реки Преголя. Через два рукава реки перекинуто семь мостов. Нужно определить, можно ли обойти все мосты, пройдя по каждому ровно один раз. Мне сообщили, что некоторые утверждают, будто это невозможно, другие сомневаются, но никто не верит, что это  и в самом деле возможно».

    Сам Эйлер определил, что решить задачу невозможно, приведя следующие рассуждения. Расположение районов города можно представить на схеме, где четырём точкам A, B, C и D соответствуют четыре района города, а кривым, соединяющим эти точки, - мосты:

                                          

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

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

    В 1847 году Густав Кирхгоф использовал схемы, подобные графам, при изучении электрических цепей. В 1857 году Артур Кэли изучал число изомеров органического соединения с помощью графов, в которых точки соединялись между собой одной или четырьмя линиями – по числу химических связей. В 1869 году Мари Энмон Камиль Жордан занимался анализом абстрактных древовидных структур. В 1859 году ирландский математик Уильям Роуэн Гамильтон придумал игру, цель которой – обойти вершины многогранника. Несколько лет спустя на основе этой игры были созданы гамильтоновы цепи, которые имеют очень интересное применение.         

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

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

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

2.2. Пионеры теории графов

    Развитию теории графов в немалой степени способствовали такие выдающиеся ученые, как Уильям Томас Татт, Фрэнк Харари, Эдсгер Вибе Дейкстра и Пол Эрдёш. Теория графов приобрела большую известность благодаря их исследованиям, нестандартным задачам и написанным ими справочникам.

   Британский ученый Уильям Томас Татт (1917-2002) изучал химию, но интерес к занимательным математическим задачам заставил его сменить сферу деятельности. В итоге в 1948 году он получил степень доктора математики и начал заниматься преподаванием и научной деятельностью.

Его 168 статей и несколько блестящих книг особенно обогатили теорию графов, а вместе с ней – комбинаторику и дискретную математику. Многие понятия теории графов теперь носят его имя.

     Американский Фрэнк Харари (1921 – 2005) по праву считается основателем современной теории графов. Его 700 статей, выступления на конференциях в 87 странах, основанный им в 1977 году престижный «Журнал теории графов», вышедшая в 1969 году, считающаяся одной из самых значимых книг по этой теме, являются доказательством тому, что он заслужил международное признание. Он применял теорию графов не только в математике и информатике, но и в антропологии, географии, лингвистике, искусстве, музыке, физике, инженерном деле и других областях.

    Голландский учёный Эдсгер Вибе Дейкстра (1930 – 2002)  заинтересовался компьютерными программами в раннем детстве и посвятил им всю свою жизнь. Ему мы обязаны знаменитой фразой «Информатика не более наука о компьютерах, чем астрономия – наука о телескопах». Дейкстра никогда не пользовался компьютером, кроме как для отправки электронной почты и поиска информации в интернете, а все свои труды об алгоритмах и языках программирования он писал … от руки!

    Пол Эрдёш (1913-1996) родился и получил образование в Будапеште. Благодаря выдающемуся уму он добился исключительных результатов в теории графов, комбинаторике, геометрии и теории чисел. Он стал автором множества удивительных задач и гипотез, а также написал свыше 1500 статей.

2.3. Азы теории графов

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

 

 

               Рис.1           Рис.2                              Рис.3

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

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

     Фигуры, изображенные на рисунке 4а,б,в – это разные представления одного и того же графа. Согласитесь, увидеть это не так-то просто!

 

           Рис.4,а                                     Рис.4,б                                  Рис.4,в

   На рисунках 5 а,б,в,г  изображены четыре графа . Граф (Рис.5,а) является исходным, остальные три  (Рис5б,в,г)  – его подграфы. Это означает, что в них были выбраны лишь некоторые ребра и вершины исходного графа. Подграфы позволяют изучить графы по частям.

                                                                       

 

                                   

           Рис.5,а                                                Рис.5,б

 

               Рис.5,в                                              Рис.5,г

    Обычно различают три типа графов: обыкновенные графы, мультиграфы и псевдографы. На рисунках 6,а,б,в представлены все три типа графов.

 

                                                                                         

 

                                                          

 

               Рис.6,а                        Рис.6,б                                 Рис.6,в

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

     Применительно к различным вариантам обхода графа используются следующие обозначения. Пусть G – помеченный граф с вершинами V₀, V₁, V₂, … и ребрами Х₁, Х₂, Х₃, …Тогда маршрутом в графе G будет называться конечная последовательность вида V₀, Х₁,V₁,… ,V_n-1, X_n, V_n, в которой чередуются ребра и вершины. Запись вида (V₀, V₁, …V_n) подразумевает, что любые две вершины соединяются только одним ребром, и маршрут определяется указанной последовательностью вершин. Если V₀=V_n, то есть исходная и конечная вершина маршрута совпадают, то маршрут является замкнутым, иначе – открытым. Путь – это маршрут, в котором каждое ребро проходит только один раз. Замкнутый маршрут, содержащий n разных вершин, называется циклом. Любой цикл можно представить графически в виде многоугольника.

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

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

                            В

        А                               

                                           D

                         C                                

                                         E          

                                                           Рис.7

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

2.4.1. Геометрические и полные графы

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

 

              Рис.8,а                                                       Рис.8,б

      Подобными графами можно представить маршруты городских автобусов или маршруты патрулей. Число вершин  V равно числу рёбер А.

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

     При подсчете числа граней С следует учитывать, что внешняя часть плоскости также образует грань, так как она тоже ограничена циклом из вершин и ребер графа. Таким образом, граф, изображенный на рисунке 9, имеет 10 вершин, 14 ребер и 6 граней.

 

                                             Рис.9

    Графы, в которых любая пара вершин соединена ребром, называются полными. На следующих рисунках 10а,б,в,г,д,е приведены полные графы с числом вершин от 2 до 7. Полный граф с n вершинами обозначается К_n.

 

                К₂

 

                                                      К₃                                                            К₄

                 а)                                   б)                                      в)

 

                К₅                                                      К₆                                            К₇

                          г)                                          д)                                        е)

                                                   Рис.10

  Подсчитать число ребер полного графа Кn очень просто: каждая вершина должна соединяться с n – 1 вершиной. Число вершин равно n. Следовательно, значение выражения n*(n - 1) будет равно удвоенному числу ребер (так как каждое ребро соединяет две вершины). Поэтому общее число ребер будет равно n(n - 1)/2 – биномиальному коэффициенту (n/2), равному числу ребер и n является квадратичной, следовательно, число ребер Kn будет возрастать очень быстро.

Задача 1. В государстве 100 городов, из каждого выходит 2 дороги, кроме столицы, откуда выходит 5 дорог о города Горный, откуда выходит одна единственная дорога. Сколько всего дорог в государстве?

Решение: сложим количество дорог, выходящих из всех городов: 98×2+5+1=202. Это число – количество концов всех дорог. Поскольку каждая дорога имеет 2 конца, то количество дорог будет вдвое меньше, а именно 101.

Ответ: 101

Задача 2. На остров Коневец завезли 13 телефонов. Настоятель хочет организовать такую схему телефонной связи, чтобы соединить каждый телефон ровно  с 7-ю другими. Удастся ли ему это решить?

Решение: Посчитаем, сколько проводов нужно, чтобы осуществить такую схему. Концов проводов будет 13×7=91, а самих проводов – вдвое меньше, то есть 45,5 штук. Это означает такая схема связи невозможна.

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

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

                                                                          A

        А                     В

                                                             E                         B

 

         D                    C                                 D          C

                                              Рис.11

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

                                               В                              A                           B

 

                    

                                                С

     D                                                                 D                                        C

Рис.12

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

Задача о колодцах и враждующих семьях

    Задача звучит так: в трёх домах a,b,c  живут три семьи, враждующие между собой. Рядом с их домами находятся три колодца  e,f,g.  Один из колодцев всегда полон, два других пусты. Соседи хотят проложить дорожки так, чтобы из каждого дома можно было попасть к каждому колодцу. Никакие две дорожки не должны пересекаться, чтобы каждый мог избежать встреч с соседями. Можно ли проложить девять дорожек таким способом?

   На рисунке 13,а  показана первая попытка соединить дома a,b,c  и колодцы

e,f,g. Такой граф обозначается К_3,3. Получилось множество нежелательных пересечений. На рисунке 13,б тот же граф  изображен иначе, но избежать пересечений по-прежнему не удалось. Заметим, что если убрать дорожку от дома b к колодцу g, то можно проложить восемь дорожек без пересечений.

          a          b        c                                                   e

                                                                      a                           b

                                                                   

         e          f          g                                   g                             f

 

                         а)                                                      c         б)

                                                     Рис.13

     Можно ли добавить к этому  графу недостающее ребро так, чтобы не пересекать остальные? Будет уместно привести одно интуитивно понятное утверждение (любопытно, что доказать его непросто): если простая плоская замкнутая непрерывная кривая делит плоскость на две части (внешнюю и внутреннюю), то любая непрерывная кривая, соединяющая точку внешней части и точку внутренней части, пересечет данную кривую минимум один раз. Это утверждение носит название теоремы Жордана. Посмотрим снова на рисунок 13 и увидим, что в обоих случаях точка g находится внутри непрерывной замкнутой кривой, а точка b – вне её. Следовательно, задача о колодцах не имеет решения. Единственный способ, которым можно  проложить дорожку из дома b к колодцу g  - это построить мост, проходящий поверх одной из дорожек.

В задаче о колодцах представлен первый пример не планарного графа. Граф, который мы обозначили  К_3,3, не является планарным. Еще один простой пример не планарного графа – это полный граф  К₅ в форме пятиугольника с пятиугольной звездой внутри, изображенный на рисунке 14:

 

Рис.14

Рассмотрим примеры задач.

    Задача 3. Между девятью планетами солнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам: Земля – Меркурий; Плутон – Венера; Земля – Плутон; Плутон – Меркурий; Меркурий – Венера; Уран – Нептун; Нептун – Сатурн; Сатурн – Юпитер; Юпитер – Марс и Марс – Уран. Можно ли долететь на рейсовых ракетах с Земли до Марса?

Решение: Нарисуем схему условия: планеты изобразим точками, а маршруты ракет – линиями.

                                   З                          Н                     С

                                                 М

                  П                                                                             

                                                            У                             Ю

                                              В                                       Марс

Ответ: долететь с Земли до Марса нельзя.

2.2.3. Деревья, за которыми виден лес

   Дерево – это очень простой граф, все вершины которого соединены так, что отсутствуют циклы, как, например, на  рисунке 15:  

 

                                 Рис.15

      В дереве можно проложить маршрут между любыми двумя вершинами.

      Последовательность чисел, обозначающих количество всех возможных деревьев для каждого числа вершин, выглядит так: 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159…

     Если дерево имеет p  вершин, то в нем всегда будет p – 1  ребер, но для каждого значения p можно изобразить p^p-2  разных деревьев (формула Кэли). Понятие дерева впервые ввел Кэли в 1857 году. Деревья образуют очень важный класс графов, так как в них все вершины соединены минимально возможным числом ребер.

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

     «Граф  G является деревом  тогда и только тогда, когда между любыми двумя различными его вершинами  u и v существует единственный путь. Это равносильно следующему утверждению: G является связным графом, если он имеет p  вершин и  p – 1  ребро».

Несмотря на простоту этой теоремы, число возможных деревьев по мере увеличения p возрастает очень быстро.

Рассмотрим задачу, которую можно решить с помощью деревьев.

     Даны n городов А₁, А2,…, А_n . Зная затраты на установление сообщения между каждой парой  городов (стоимость строительства дорог, прокладки водо- и газопровода, линий  электропередачи, телефонных линий), определите, как можно соединить города  самым дешевым способом. Очевидно, что сеть «экономических связей» будет деревом, так как все города должны быть  связаны друг с другом и не должно существовать циклов. Если бы в этой сети существовал цикл, можно было бы удалить одно из его ребер и все города по-прежнему были бы соединены между собой, но уже при меньших затратах.

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

  Задача 5:  Сколько четырехбуквенных слов можно составить, используя только буквы А и Б?

Решение: Составим дерево для всех комбинаций  четырехбуквенных слов из букв А и Б.

А

Б

А

Б

А

Б

А

Б

А

Б

А

Б

А

Б

А

Б

А

Б

А

Б

А

Б

А

Б

А

Б

А

Б

А

Б

Ответ: 16 слов.

2.2.4. Эйлеровы графы

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

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

Эйлер доказал, что эти условия являются также и достаточными.

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

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

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

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

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

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

 

                                                               

Решение:                    А                                                                                                                                                                

                   Е                          В

                                                                   С – Е – В – Д – Е – А – В – С – Д

                   Д                             С

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

 

Решение: Нельзя нарисовать такую фигуру одним росчерком, так как она имеет четыре нечетных узла.

Глава 3. Результаты и их обсуждения

1.     Изучив литературу по теме исследования, я составила схему «Виды графов».

«Виды графов»

                                  Схема № 1.               

                                                                Графы                  

                                                              

                       Полные                                                          Эйлеровы

                        Геометрические       Плоские        Деревья  

2.     В ходе своего исследования мной было проведено анкетирование  среди учащихся 7 – 9 классов для выявления их осведомленности о графах  и решении задач с помощью графов. В опросе участвовало 60 обучающихся. Результаты своего анкетирования я занесла в таблицу.

№	Вопрос	Кол-во учащихся		%
		Да	Нет	Да	Нет
1	Слышали вы задачу: начертить конвертик, не отрывая карандаша от бумаги и не проводя ни одной линии дважды?	58	2	97	3
2	Смогли вы ее решить?	20	40	33	67
3	Знакомо ли вам понятие граф?	48	12	80	20
4	Надо ли знакомить учащихся с графами?	53	7	88	12

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

3.     На предметной неделе – неделе точных наук – я провела в 8-х классах информационный час  «Решаем с помощью графов». Сделала небольшую историческую справку о возникновении графа, привела несколько примеров, показала, как решаются задачи с помощью графов. Далее я предложила ребятам решить самим подобные задачи. Им очень понравились задачи на эйлеровы графы и на составление деревьев.

4.     Итогом моей работы стало наглядное пособие  «Решаем с помощью графов» (См. Приложение 1).

Заключение

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

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

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

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

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

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

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

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

2.     Ф.Харари. Теория графов. – М.: Едиториал УРСС, 2003.

3.     Мир математики в 40 т. Т.11: Клауди Альсина. Карты  метро и нейронные сети. Теория графов. – М.: Де Агостини, 2014.

4.     М.И.Зайкин. математический тренинг: Развиваем комбинационные способности. – М.: ВЛАДОС, 1996.

5.     «Математика для школьников» - научно-практический журнал №3, 2011.

Сайты Интернет:

6.     http://kenigsberg-pr.narod.ru/image/i3.gif

Приложение №1.