Графы

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                Графы

    Введение

Глава 1

Теория графов

1.1. Понятие графов

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

1.3. Задача о мостах, Леонард Эйлер и теория графов

Глава 2

2.1. Решение задач с помощью графов «Один день из жизни Графа»

        Вывод

Литература

Введение

Актуальность исследования. 

Была предложена задача, в которой нужно было просчитать перестановку фигур за меньшее число ходов. Как это сделать?  Стали искать пути решения, и оказалось, что это можно сделать с помощью графов. С понятием «граф» мы  встречались  на уроке истории при изучении темы дворянство и на уроке математики в 6 классе.

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

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

Объект исследования: понятие «граф»

Предмет исследования: степень распространенности применения графов

Цель исследования: Исследовать роль графов в нашей жизни.

Задачи исследования:

1.Познакомиться с историей возникновения графов.

2.Познакомиться с основными понятиями графа, видами, элементами.

3.Научиться решать задачи с помощью графов.

Глава 1

Теория графов

1.1. Понятие графа

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

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

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

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

Граф, в котором все линии направленные, называется ориентированным графом.

Все вершины, соединенные дугой или ребром, называются смежными.

Граф, содержащий симметричные (ненаправленные) связи- ребра, называется неориентированным.

Основы теории графов как математической науки заложил в 1736 г. Эйлер,

хотя термин «граф» впервые ввел в 1936 году венгерский математик Денеш Кениг.

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

Схема графа, состоящая из «изолированных» вершин, называется нулевым графом. (рис.2)

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

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

Степени вершин и подсчет числа ребер.

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

Если степени всех вершин графа равны, то граф называется однородным. Таким образом, любой полный граф — однородный.

                                                          рис.5

На рисунке 5 изображен граф с пятью вершинами. Степень вершины А обозначим Ст.А.

На рисунке : Ст.А = 1, Ст.Б = 2, Ст.В = 3, Ст.Г= 2, Ст.Д= 0.

Сформулируем некоторые закономерности, присущие определенным графам.

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

Доказательство:

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

Закономерность 2. Сумма степеней вершин графа число четное, равное удвоенному числу ребер графа.

Эта закономерность справедлива не только для полного, но и для любого графа.

 Доказательство:

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

Теорема.

Число нечетных вершин любого графа четно.

Доказательство:

Рассмотрим произвольный граф Г. Пусть в этом графе число вершин, степень которых 1, равна К1; число вершин, степень которых 2, равно K2; ...; число вершин, степень которых n, равно Кn. Тогда сумму степеней вершин этого графа можно записать как K1 + 2К2 + ЗК3 + ...+ nКn.

С другой стороны: если число ребер графа R, то из закономерности 2 известно, что сумма степеней всех вершин графа равна 2R. Тогда можно записать равенство

K1 + 2К2 + ЗК3 + ... + nКn = 2R. (1)

Выделим в левой части равенства сумму, равную числу нечетных вершин графа (К1 + К3 + ...):

K1 + 2К2 + ЗК3 + 4К4 + 5К5 + ... + nК = 2R,

(К1 + К3 + К5 +...) + (2K2 + 2Х3 +4K4 + 4К5 + ...)=2R

Вторая скобка- четное число как сумма четных чисел. Полученная сумма (2R) четное число. Отсюда (К1 + К3 + К5 +...)-четное число.

Заметим, что если полный граф имеет n вершин, то количество ребер будет равно n(n-1)/2.

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

Граф, не являющийся полным, можно дополнить до полного с теми же вершинами, добавив недостающие ребра. Так, например, на рисунке 3 изображен неполный граф с пятью вершинами. На рисунке 4 – ребра, превращающие граф в полный граф, изображены другим цветом. Совокупность вершин графа с этими ребрами называется дополнением графа.

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

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

Такими графы названы в честь учёного Леонарда Эйлера.

Закономерность 3 (вытекает из рассмотренной нами теоремы). Невозможно начертить граф с нечетным числом нечетных вершин.

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

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

Закономерность 6. Граф, имеющий более двух нечетных вершин, невозможно начертить «одним росчерком».

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

         рис.6 (эйлеровы графы)

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

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

Граф называется несвязным, если это условие не выполняется.

                                   рис.7                                    рис.8

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

Такое ребро в теории графов (после удаления которого граф из связного превращается в несвязный) называется мостом.

Примерами мостов на рисунке 7 могли бы служить ребра ДЕ, A3, ВЖ и др., каждое из которых соединяло бы вершины «изолированных» частей графа.(рис.8)

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

1.3. Задача о мостах. Леонард Эйлер и теория графов

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

Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам, не проходя ни по одному из них дважды? Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически, во время прогулок. Но никому это не удавалось, однако не удавалось и доказать, что это даже теоретически невозможно.

Этот вопрос привлек внимание ученых разных стран. В 1736 году задача о семи мостах заинтересовала выдающегося математика, члена Петербургской академии наук Леонарда Эйлера, о чём он написал в письме итальянскому математику и инженеру Мариони от 13 марта 1736 года. В этом письме Эйлер пишет о том, что он смог найти правило, пользуясь которым легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них (в случае семи мостов Кёнигсберга это невозможно).

Причем, он не только решил эту конкретную задачу, но придумал общий метод решения подобных задач. Эйлер поступил следующим образом: он «сжал» сушу в точки, а мосты «вытянул» в линии, как показано на рисунке 9 а, б.

Рисунок 9

На упрощённой схеме части города (графе) мостам соответствуют линии (рёбра графа), а частям города — точки соединения линий (вершины графа). В ходе рассуждений Эйлер пришёл к следующим выводам:

Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа всегда чётно. Невозможно начертить граф, который имел бы нечётное число нечётных вершин.

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

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

Давайте четко сформулируем поставленную задачу.

 При каком условии можно обойти все ребра графа, пройдя каждое ровно один раз?

Решение оказалось очень простым.

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

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

пройти по всем мостам, не проходя ни по одному из них дважды.

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

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

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

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

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

Деревья.

Деревом называется любой связный граф, не имеющий циклов. Договорились считать «деревом» и всякий граф, состоящий из одной (изолированной) вершины.

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

Если все вершины цикла разные, то такой цикл называется элементарным (или простым) циклом.

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

 В графе на рис.10б два цикла: 1-2-3-4-1 и 5-6-7-5.

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

Висячей вершиной называется вершина, из которой выходит ровно одно ребро. (рис.12)

                                                                рис.10 а;б

Свойство 1. Для каждой пары вершин дерева существует единственный путь, их соединяющий.

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

Свойство 2. Всякое ребро в дереве является мостом.

Действительно, после удаления любого ребра дерева, оно «распадается» на два дерева.

рис.12 (кружком обведены висячие вершины)

       Граф, в котором две любые вершины соединены ровно одним простым путём, является деревом.

Доказательство:

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

Дерево – это граф, в котором две любые вершины соединены ровно одним

 простым путём.

Лемма (о висячей вершине). В каждом дереве есть висячая вершина.

Доказательство:

Рассмотрим произвольную вершину дерева и пойдём по любому выходящему из неё ребру в другую вершину. Если из новой вершины больше рёбер не выходит, то мы остаёмся в ней, а противном случае, идём по любому другому ребру дальше. Понятно, что в этом путешествии мы никогда не сможем попасть в вершину, в которой уже побывали: это означало бы наличие цикла. Так как у графа конечное число вершин, то наше путешествие обязательно должно закончится. Но закончиться оно может только в висячей вершине. Лемма доказана.

Что можно описать с помощью графов? Обозначим области применения данного описания.

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

Например:

Схему линий метрополитена можно рассматривать как граф.

В химии граф можно рассматривать как способ отображения структуры молекулы.

В медицине – вопрос о группе крови.

В виде графа можно представить генеалогическое дерево.

Системы классификаций в науке.

Иерархическую структуру административного управления предприятия, ВУЗа и т.д.

В информатике: файловая система диска, доменных адресов в Интернете систему, блок – схемы алгоритмов.

И еще можно привести очень много различных примеров.

Глава 2

2.1. Решение задач с помощью графов «Один день из жизни Графа»

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

Задача 1. Утром учащихся нашей школы привезли с окрестных деревень Волчино, Ольховка, Кочковатое, Павловка на занятия. На рисунке изображен граф, представляющий информацию о дорогах между четырьмя деревнями: Волчино, Ольховка, Кочковатое, Павловка. Веса вершин – названия деревень, веса линий – длина дорог в километрах.

Маршрут движения автобуса – это граф.

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

Решение.

Задача решается с помощью полных графов.

1)Встретились трое:

 Количество рукопожатий равно количеству рёбер, т.е.3.

2)Встретились четверо:

Количество рёбер 6; возможно 6 рукопожатий.

3)Встретились пятеро:

В графе 10 рёбер; возможно 10 рукопожатий.

Ответ: 1)3; 2)6; 3)10.

По расписанию у нас шесть уроков: геометрия, история, информатика, география, русский язык и физика.

Задача 3.На уроке геометрии было предложено построить граф классификации геометрических объектов. Это оказалось легко сделать с помощью понятия граф.

Задача 4. А на уроке истории нужно было составить родословное дерево. Родословное дерево. Использует графы и дворянство.

Например, в генеалогическом дереве, вершины – члены рода, а связывающие их отрезки – отношения родственности.

Всем известно, что слово «граф» означает дворянский титул, например граф Лев Николаевич Толстой. На рисунке еще один граф – часть генеалогического древа графа Л.Н. Толстого. Здесь вершины – предки писателя, а ребра показывают родственные связи между ними.

Задача 4. На уроке информатике мы познакомились с новой темой «Алгоритмы». И к нашему удивлению, оказалось, что блок схема – ориентированный граф.

 Блок – схема алгоритма представляет собой граф процесса управления некоторым исполнителем.

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

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

Задача 5. На уроке русского языка тема «Числительные» и учитель предложила нам составить опорный конспект.

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

 Пример простых числительных: четыре, пять.

 Пример сложных числительных : шестьдесят, пятьсот.

 Пример составных числительных: 35, 154. По значению числительные делятся на порядковые и количественные.

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

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

Решение.

Чтобы указать все обеды из двух блюд, будем рассуждать так. Выберем одно первое блюдо (борщ) и будем добавлять к нему поочерёдно разные вторыеблюда, получим пары:

б - г, б – к, б – с, б – п. (4 пары).

Теперь в качестве первого блюда выберем рассольник и будем добавлять к нему поочерёдно разные вторые блюда:

р – г, р – к, р – с, р – п. (4 пары).

Таким образом, всего есть 2 ∙ 4 = 8 вариантов обеда из двух блюд, которые может заказать посетитель.    

Проиллюстрируем ответ, построив дерево возможных вариантов.

                                  Обед

                         Первое блюдо

 Рассольник                                               Борщ

Гуляш      Котлеты      Сосиски      Пельмени

     1                2                    3                     4

     5                6                    7                     8

Ответ: 8 разных обедов из двух блюд.

Замечание. В задаче осуществляются два выбора, но каждый выбор - из своего множества вариантов.

Ответ: 6 сочетаний.

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

Благодаря теории графов, с легкостью решаются логические задачи.

Поход в магазин за хлебом. Система «Хлебный магазин» состоит из следующих элементов: хлеб, продавец, покупатель, прилавок, автомобиль, шофер, грузчик, деньги, чек. Вершинами графа являются перечисленные объекты, а дуги – отношения между ними.

 Везде и повсюду нас окружают Графы.

Вывод

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

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

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

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

Литература

1. Генкин С.А, Итенберг И.В. Ленинградские математические кружки:              пособие для внеклассной работы. Киров, 1994г.

2. Горбачев, В.Г. Сборник олимпиадных задач по математике. М., 2004г.

3. Игнатьев Е.И. Математическая смекалка.  Москва, 1994 г.

4. Оре О. Графы и их применение. Москва, 1979 г.

5. Перельман Я.И. Весёлые задачи. Москва, 2003г

6. Физико-математический журнал «Квант», А. Савин, №6, 1994г.