Графы и их применение

            Графы и их применения

                        Содержание

1. Введение
2. Основные понятия теории графов

1. Определение графа
2. Элементы графа
3. Степень вершины
4. Определение полного графа
5. Свойства полного графа

3. Полный граф и его свойства

1. Определение полного графа
2. Свойство полного графа

4. Путь, маршрут и цикл в графе

1. Определение маршрута
2. Определение пути
3. Понятие цикла

5. Избранные задачи
6. Заключение

                                       1. Введение

     Для своего теоретического изучения я выбрал тему «Графы». Почему меня заинтересовала эта тема? Я уже не раз принимал участие в конкурсе «Кенгуру», в заочной олимпиаде физико-математического лицея «Авангард», в предметном чемпионате центра развития одарённости г. Пермь и хочу принимать участие в олимпиадах по математике, проводимых другими учебными организациями. Для подготовки к олимпиадам я пользуюсь книгой «Готовимся к олимпиаде. Математика» автора  Е. Г. Конновой.

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

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

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

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

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

                 2. Основные понятия теории графов

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

 В 30-е годы 20 века немецкий математик Дене Кениг впервые провёл исследование подобных схем и дал им общее название «графы»

2.1. Определения. Графом называется несколько точек, соединенных линиями

2.2. Точки называются вершинами графа, а линии- рёбра

            вершины

        ребро

        рис.1

           Если линия имеет направление, она называется дугой, а граф, содержащий только дуги- ориентированным.

Вершины, соединённые одним ребром, называют смежными.

Рёбра, имеющие общую вершину, тоже называют смежными.

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

        Рис.2

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

        Рис.3

2.3. Определение. Число рёбер, выходящих из одной вершины, называют степенью этой вершины.

Лемма1. Число рёбер в графе ровно в 2 раза меньше, чем сумма степеней вершин.

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

Лемма2. Сумма степеней вершин графа чётна.

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

2.4. Определение. Если степень вершины чётная, то вершина называется чётной, если степень не чётная, то вершина нечётная.

2.5. Лемма3. Число нечётных вершин графа чётно.

Доказательство. Если в графе есть n чётных и k нечётных вершин, то сумма степеней чётных вершин чётна. Сумма степеней нечётных вершин нечётна, если количество этих вершин нечётна. Но тогда общее число степеней вершин тоже нечётна, чего не может быть. Значит, k чётно.

                 3. Полный граф и его свойства

3.1 Определение. Граф называют нулевым, если в нём есть вершины, но нет рёбер (рис.4).

Если не все вершины соединены рёбрами, то граф называют неполным (рис.5).

     В полном графе две любые вершины соединены одним ребром (рис.6)

A        B        A                      B            A                        B

P        C      P                    C              P                      C

рис.4        рис.5        рис.6                

3.2 Лемма 4. В полном графе с n вершинами число рёбер равно  

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

                4. Путь,  маршрут и цикл в графе

4.1 Определение. Маршрутом в графе называется последовательность рёбер, в которой соседние рёбра имеют общую вершину.

Первая вершина называется началом маршрута, последняя- концом.

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

   Если в пути нет повторяющихся вершин, его называют простым путём.

Длина маршрута равна количеству рёбер в порядке их прохождения.

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

 На рисунке  F   длина пути AFBCE   равна 4, а расстояние от A до E равно 2

             F

A                B

        E

        C

   Рис.7

        D

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

Если в цикле все вершины разные, его называют простым циклом.

Если в цикле все рёбра разные, то цикл называется эйлеровым.

    Маршрут, содержащий все рёбра или все вершины графа, называется обходом графа.

На рисунке 4 CEDEBF, FABCE- маршруты, FABCE- путь, CEDEBF- не являются путём, т.к. ребро DE повторяется. AFBA, AFBCEBA- циклы AFBA- простой цикл,  AFBCEBA- эйлеров  цикл.

                       5. Избранные задачи

1. В 10-значном числе каждые две подряд идущие цифры образуют двузначное число, которое делится на 13. Докажите, что среди этих цифр нет цифры 8.

Решение. Существует 7 двузначных чисел, которые делятся на 13. Обозначим эти числа точками и применим определение графа. По условию каждые 2 подряд идущие цифры образуют двузначное число, которые делятся на 13, значит цифры, из которых состоит 10-значное число, повторяются. Соединим вершины графа рёбрами так , чтобы цифры, входящие в этот граф повторялись.

     13                 65

        78

91                               39        52        

26

Из построенных графов видно, что среди цифр 10-значного числа цифры 8 быть не может.

2. В деревне 10 домов, и из каждого выходит по 7 тропинок, идущих к другим домам. Сколько всего тропинок приходит между домами?

Решение. Пусть дома- вершины графа, тропинки- рёбра. По условию из каждого дома (вершины) выходит 7 тропинок (рёбер), тогда степень каждой вершины 7, сумма степеней вершин 7×10=70, а число рёбер 70 : 2= 35. Таким образом между домами проходит 35 тропинок.

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

Решение. Представим себе, что мы нашли таких 5 чисел. Пусть эти числа будут вершинами графа. Если два числа имеют одинаковый простой делитель, соединим их ребром. Степень каждой вершины такого графа равна 3, а вершин 5 получим, что сумма степеней вершин графа 3×5=15 – нечётное число. По лемме 2 сумма степеней вершин графа чётна, значит таких 5 чисел найти нельзя.

4. Сколько диагоналей в 17-угольнике?

Решение. Вершины 17-угольника – вершины графа, а диагонали и стороны – ребра графа. Всего 17×(17-1) : 2 = 136 ребер. Из них 17 сторон, остальные диагонали. Значит, диагоналей 136 – 17 = 119.

5.На рисунке изображены  расстояния между пунктами A, B, C, D, E и F. Двигаться по дорогам можно только в направлениях, указанных стрелочками. Водитель едет из пункта А в пункт Е. Как он должен ехать, чтобы добраться по самому короткому пути?

        C        D        

        A        E

        B        F

Решение. Рассмотрим последовательно возможные пути поездки и сравним их длину. ABFE = 14, ABFCDE = 15, ABFDE = 13, ACDE = 16.Выберем наименьшее расстояние. Оно равно 13, значит нужно ехать по маршруту ABFDE.

6.В офисе компании «Суперботан» 129 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен, ровно с  семью другими?

Решение. Пусть каждый телефон является вершиной графа,  тогда степень каждой вершины равна 7, а сумма степеней всех вершин равна 129×7 = 903-число нечетное. По лемме 2 сумма степеней вершин графа четна, значит соединить телефоны указанным образом нельзя.

                      7.Заключение

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