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

 

Введение

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

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

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

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

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

- рассмотреть примеры её приложения.

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

• в физике - при построении электрических схем, в химии и биологии – при изучении молекул их цепочек;
• в географии – при составлении карт;
• в истории – при составлении генеалогических древ (родословной);
• в геометрии – чертежи многоугольников, многогранников, пространственных фигур;
• в экономике – при решении задач о выборе оптимального пути для потоков грузового транспорта (схем авиалиний, метро, железных дорог);
• в повседневной жизни – нахождение объездного пути  или ближайшего продуктового магазина, планирование оптимального маршрута.

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

 

 

 

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

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

 

Граф – система, которая интуитивно может быть рассмотрена как множество кружков и множество соединяющих их линий (рис. 1)[8, стр.1 ].

          

           Рис. 1 Графы: А- неориентированный, Б- ориентированный

 

Кружки называются вершинами графа, линии со стрелками – дугами, без стрелок – ребрами. Граф, в котором направление линий не выделяется (все линии являются ребрами), называется неориентированным (рис. 1, А); граф, в котором направление линий принципиально (линии являются дугами) называется ориентированным (рис. 1, Б).

Опр. 1. Задано конечное множество X, состоящее из n элементов (X = {1, 2,…, n}), называемых вершинами графа, и подмножество V декартова произведения X ×X, то есть , называемое множеством дуг, тогда ориентированным графом G называется совокупность (X, V).

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

Дугу между вершинами i и j, , будем обозначать (i, j). Число дуг графа будем обозначать m (V = ( )).

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

Опр. 4. Две вершины называются смежными, если они соединены ребром (дугой). Смежные вершины называются граничными вершинами соответствующего ребра (дуги), а это ребро (дуга) – инцидентным соответствующим вершинам.

Опр.5. Путем называется последовательность дуг (в ориентированном графе), такая, что конец одной дуги является началом другой дуги.

Опр. 5.1. Простой путь – путь, в котором ни одна дуга не встречается дважды.

Опр. 5.2. Элементарный путь – путь, в котором ни одна вершина не встречается дважды.

Опр. 5.3. Контур – путь, у которого конечная вершина совпадает с начальной вершиной.

Опр. 5.4 Длиной пути (контура) называется число дуг пути (или сумма длин его дуг, если последние заданы).

Опр.6. Граф, для которого из (i, j) V следует (j, i) V называется симметрическим.

Опр. 7. Если из (i, j) V следует, что (j, i) V, то соответствующий граф называется антисимметрическим.

Опр. 8.1. Цепью называется множество ребер (в неориентированном графе), которые можно расположить так, что конец (в этом расположении) одного ребра является началом другого.

Опр. 8.2. Цепь – последовательность смежных вершин.

Опр. 9. Замкнутая цепь называется циклом.

Опр. 10.1. Элементарная цепь (цикл, путь, контур), проходящая через все вершины графа называется гамильтоновой цепью (соответственно – циклом, путем, контуром).

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

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

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

Опр. 13. В неориентированном графе степенью вершины i называется число инцидентных ей ребер. Очевидно, . Граф, степени всех вершин которого равны n – 1, называется полным. Граф, все степени вершин которого равны, называется однородным.

Опр. 14. Вершина, для которой не существует инцидентных ей ребер ( = 0) называется изолированной. Вершина, для которой существует только одно инцидентное ей ребро ( = 1) называется висячей.

Опр. 15. Определим матрицу смежности графа как квадратную матрицу n ×n, элемент которой равен единице, если (i, j) V, и нулю, если (i, j) V, i, j X. Для неориентированного графа матрица смежности всегда симметрическая.

Опр. 16. Определим матрицу инциденций для ребер графа как прямоугольную матрицу n×m, элемент которой равен единице, если вершина i инцидентна ребру j, и нулю в противном случае, i = 1, n, j = 1, m.

Опр. 17. Матрица инциденций для дуг графа – прямоугольная матрицу m xn, элемент rij которой равен плюс единице, если дуга исходит из вершины i, минус единице, если дуга заходит в вершину i, и нулю в остальных случаях, i = 1, n, j = 1, m

Опр. 18. Деревом называется связный граф без простых циклов, имеющий не менее двух вершин. Для дерева m = n – 1, а число висячих вершин равно Легко показать, что в дереве любые две вершины связаны единственной цепью.

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

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

Опр. 21. Степенью грани называется число ее граничных ребер (висячие ребра считаются дважды).

Любому связному плоскому графу G можно поставить в соответствие двойственный ему связный плоский граф G*, определяемый следующим образом: каждой грани графа G соответствует вершина графа G*, каждому ребру V графа G, являющемуся граничным для граней z1 и z2, соответствует ребро V* графа G*, соединяющее соответствующие граням z1 и z2 вершины.

 

1.2 Примеры графов

 

Вполне несвязные графы. [5,стр24] Граф, у которого множество ребер пусто, называется вполне несвязным (или пустым) графом.[5,стр24] Будем обозначать вполне несвязный граф с n вершинами через Nn; N4 показан на рис. 1. Заметим, что у вполне несвязного графа все вершины изолированы. Вполне несвязные графы не представляют особого интереса.

 

 

Рис.1 Пустой граф

Полные графы. Простой граф, в котором любые две вершины смежны, называется полным графом. Полный граф с n вершинами обычно обозначается через . Графы и изображены на рис. 2 и 3. имеет ровно n (n – 1)/2 ребер.

Рис.2 Пример полного графа             Рис.3 Пример полного графа       

 

Регулярные графы. Граф, у которого все вершины имеют одну и ту же степень, называется регулярным графом. Если степень каждой вершины равна r, то граф называется регулярным степени r. Регулярные графы степени 3, называемые также кубическими (или трехвалентными) графами (см., например, рис. 2 и 4). Другим известным примером кубического графа является так называемый граф Петерсена, показанный на рис. 5. Отметим, что каждый вполне несвязный граф является регулярным степени 0, а каждый полный граф Кn – регулярным степени n – 1.

 

 

 

                                      

   Рис.4 Кубический граф                                                           Рис.5 Граф Петерсена

Платоновы графы. Среди регулярных графов особенно интересны так называемые Платоновы графы – графы образованные вершинами и ребрами пяти правильных многогранников – платоновых тел: тетраэдра, куба, октаэдра, додекаэдра и икосаэдра. Граф соответствует тетраэдру (рис. 2); графы, соответствующие кубу и октаэдру, показаны на рис. 5 и 6;

 

  

Рис. 6 Пример платонового графа

Двудольные графы. Допустим, что множество вершин графа можно разбить на два непересекающихся подмножества V1 и V2 так, что каждое ребро в G соединяет какую-нибудь вершину из V1 с какой-либо вершиной из V2 (рис. 7);

 

   Рис. 7 Двудольный граф  
тогда G называется двудольным графом. Такие графы иногда обозначают G(V1,V2), если хотят выделить два указанных подмножества. Двудольный граф можно определить и по-другому – в терминах раскраски его вершин двумя цветами, скажем красным и синим. При этом граф называется двудольным, если каждую его вершину можно окрасить красным или синим цветом так, чтобы любое ребро имело один конец красный, а другой – синий. Следует подчеркнуть, что в двудольном графе совсем не обязательно каждая вершина из V1 соединена с каждой вершиной из V2; если же это так и если при этом граф G простой, то он называется полным двудольным графом и обычно обозначается где m, n – число вершин соответственно в V1 и V2. Например, на рис. 8 изображен граф K4,3. Заметим, что граф имеет ровно m + n вершин и mn ребер. Полный двудольный граф вида называется звездным графом; на рис. 9 изображен звездный граф .

 

                             

            Рис. 8 Полный двудольный граф                                   Рис. 9 Звёздный граф

Связные графы. Граф связный, если его нельзя представить в виде объединения двух графов, и несвязный в противном случае. Очевидно, что всякий несвязный граф G можно представить в виде объединения конечного числа связных графов – каждый из таких связных графов называется компонентой (связности) графа G. (На рис. 10 изображен граф с тремя компонентами.) Доказательство некоторых утверждений для произвольных графов часто бывает удобно сначала провести для связных графов, а затем применить их к каждой компоненте в отдельности.

 

      

Рис.10 Связный граф с тремя компонентами

 

Циклические графы и колеса. Связный регулярный граф степени 2 называется циклическим графом (или циклом); циклический граф. с п вершинами обозначается через Сn. Соединение графов и (п ≥ 3) называется колесом с п вершинами и обозначается Wn. На рис. 11 изображены С6 и W6; граф W4 уже появлялся на рис. 2.

Рис.11 Циклический граф и колесо

 

 

1.3 Эйлеровы графы

 

Связный граф G называется эйлеровым, если существует замкнутая цепь, проходящая через каждое его ребро; такая цепь называется эйлеровой цепью. Отметим, что в этом определении требуется, чтобы каждое ребро проходилось только один раз. Если снять ограничение на замкнутость цепи, то граф называется полуэйлеровым; при этом каждый эйлеров граф будет полуэйлеровым. На рис. 13,14,15 изображены соответственно не эйлеров, полуэилеров и эйлеров графы.

 

 

 

                                        

Рис.13 Не эйлеров граф               Рис.14 Полуэилеров граф                        Рис.15 Эйлеров графы

Название «эйлеров» возникло в связи с тем, что Эйлер первым решил знаменитую задачу о кенигсбергских мостах, в которой нужно было узнать, имеет ли граф, изображенный на рис. 15, эйлерову цепь (не имеет). Сразу же возникает вопрос: можно ли найти необходимые и достаточные условия для того, чтобы граф был эйлеровым

Докажем простую лемму.

Лемма 1. Если степень каждой вершины графа G не меньше двух, то G содержит цикл.

Доказательство. Если в графе G имеются петли или кратные ребра, то утверждение очевидно; поэтому предположим, что G является простым графом. Пусть v – произвольная вершина графа G; построим по индукции маршрут , выбирая вершину v1 смежной вершине v, а для i≥1 – выбирая vi+1 смежной vi и отличной от vi-1 (существование такой вершины vi+1 гарантировано условием леммы). Так как G имеет конечное число вершин, то в конце концов мы придем к вершине, которая уже была выбрана раньше. Предположим, что vk – первая такая вершина; тогда часть маршрута, лежащая между двумя вхождениями vh, и является требуемым циклом (рис.16).

 

Рис.16

 

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

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

 

Рис.17

 

Проведем доказательство индукцией по числу ребер в G. В силу связности G, степень каждой вершины не меньше двух, а отсюда, по предыдущей лемме, заключаем, что граф G содержит цикл С. Если С проходит через каждое ребро графа G, то доказательство завершено; если нет, то, удаляя из G ребра, принадлежащие циклу С, получим новый (быть может, и несвязный) граф Н. Число ребер в Н меньше, чем в G, и любая вершина в Н по-прежнему имеет четную степень. Согласно индуктивному предположению, в каждой компоненте графа Н существует эйлерова цепь. В силу связности графа G, каждая компонента в Н имеет по крайней мере одну общую вершину с циклом С, поэтому искомую эйлерову цепь графа G можно получить так: идем по ребрам цикла С до тех пор, пока не встретим неизолированную вершину графа Н, затем следуем по эйлеровой цепи той компоненты в Н, которая содержит указанную вершину; далее продолжаем путь по ребрам цикла С, пока не встретим вершину, принадлежащую другой компоненте графа Н, и т.д.; заканчивается процесс тогда, когда мы попадаем обратно в начальную вершину (рис. 17).

Следствие 1. Связный граф является эйлеровым тогда и только тогда, когда семейство его ребер можно разбить на непересекающиеся циклы.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2. Примеры приложения теории графов в школьном курсе математики

2.1 Логические задачи

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

Условно их можно классифицировать, подразделив на несколько групп:

1. Задачи о мостах
2. Логические задачи
3. Задачи о «правильном» раскрашивании карт
4. Задачи на построение уникурсальных графов

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

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

Задача 1.  Из трех человек, стоящих рядом, один всегда говорит правду

(правдолюб), другой всегда лжет (лжец), а третий, смотря по обстоятельствам, говорит либо правду, либо ложь (дипломат). У стоящего слева спросили: "Кто стоит рядом с тобой?". Он ответил: "Правдолюб". Стоящему в центре задали вопрос: "Кто ты?", и он ответил: "Я дипломат". Когда у стоящего справа спросили: "Кто стоит рядом с тобой?", он сказал: "Лжец". Кто где стоял?

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

Рис. 1

Рассмотрим первую возможность. Если "правдолюб" стоит слева, то рядом с ним, судя по его ответу, также стоит "правдолюб". У нас же стоит "лжец".

Следовательно, эта расстановка не удовлетворяет условию задачи. Рассмотрев таким образом все остальные возможности, мы придем к выводу, что позиция "дипломат", "лжец", "правдолюб" удовлетворяет задаче. Действительно, если "правдолюб" стоит справа, то, по его ответу, рядом с ним стоит "лжец", что выполняется. Стоящий в центре заявляет, что он "дипломат", и, следовательно, лжет (что возможно из условия), а стоящий справа также лжет. Таким образом, все условия задачи выполнены.

 

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

Решение: Решение этой задачи достигается построением следующего графа (рис. 2), где каждая вершина обозначает соответствующую газету и

соответственно 5 подписчиков, а каждое ребро будет соответствовать одному

подписчику.

Рис. 2

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

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

Любая географическая карта является многоугольным графом, в котором страны  будут гранями, границы – ребрами, а окружающий страны Мировой океан – бесконечной гранью. Для лучшего зрительного восприятия необходимо, чтобы страны с общей границей были раскрашены в разные цвета. Такую карту называют "правильно" раскрашенной. Широко известное предположение состоит в том, что каждая карта может быть раскрашена с соблюдением требуемых условий при помощи четырех красок. Этому вопросу уделяется большое внимание в популярной литературе, и здесь мы не будем останавливаться на его рассмотрении. Задачи на проведение эйлеровых линий без повторений и без отрыва карандаша от бумаги являются одним из математических развлечений. При решении подобных

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

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

 

В учебнике Математика 6 класс [6,стр. 207,215,223,229]  представлен ряд задач решаемых с помощью графов.

№1220(1204) Решение некоторые математические задачи помогают специальные схемы, состоящие из точек и соединяющих их дуг или стрелок (рис. 3). Такие схемы называют графами, точки называют вершинами графа, а дуги – рёбрами графа.

Решить с помощью графов задачу:

а) В спортивном зале собрались Витя, Коля, Петя, Серёжа и Максим (рис. 3,а).

Оказалось, что каждый из мальчиков знаком только с двумя другими. Кто с кем знаком? (Ребро графа означает «мы знакомы».)

Б) Во дворе гуляют братья и сёстры одной семьи. Кто из этих детей мальчики, а кто девочки (рис. 3, б)? (Пунктирные рёбра означают «я - сестра», а сплошные «я брат».)

 

Рис. 3             а)                                                                 б)

Решение: а) Витя знаком с Колей и Серёжей, Серёжа знаком с Витей и Петей, Петя знаком с Серёжей и Максимом, Максим знаком с Колей и Петей, Коля знаком с Витей и Максимом.

б) А и В – сёстры, Б и Г – братья.

 

№1249(1233) Решите с помощью графа задачу: «Вера, Нина, Оля и Люба надели платья разных цветов (красное, синее, белое, голубое). На вопрос, кто из них в каком платье, три девочки ответили: 1) Оля – в синем, Люба – в белом; 2) Оля – в красном, Нина – в синем; 3) Вера – в синем, Люба – в голубом. В каждом ответе только одна часть верна, а остальные нет. Какого цвета платье одела каждая девочка? »

Решение: Все ответы девочек можно изобразить в виде графа (рис 4):

Рис.4

Предположим, что в пункте 1) утверждение «Оля – в синем» верно, тогда в пункте 2) утверждение «Оля – в красном» неверно и должно быть верным утверждение «Нина – в синем», но это будет противоречить нашему предположению из пункта 1) что «Оля – в синем» верно, значит, в пункте 1) верным является утверждение «Люба – в белом». Из пункта 3) следует, что утверждение «Вера – в синем» верно, а из пункта 2) следует, что верно утверждение «Оля – в красном». Для Нины остаётся один вариант: «Нина – в голубом».

 

№1303(1287) Решите помощью графа задачу: «Марина, Лариса, Жанна и Катя умеют играть на разных инструментах (пианино, виолончели, гитаре, скрипке), но каждая только на одном. Они же знают иностранные языки (английский, французский, немецкий, испанский), но каждая только один. Известно: 1) девушка, которая играет на гитаре, говорит по-испански; 2) Лариса не играет ни на скрипке, ни на виолончели и не знает английского языка; 3) Марина не играет ни на скрипке, ни на скрипке, ни на виолончели и не знает ни немецкого, ни английского языка; 4) девушка, которая говорит по-немецки, не играет на виолончели; 5) Жанна знает французский язык, но не играет на скрипке. Кто на каком инструменте играет и какой иностранный язык знает? »

Решение: Из условия 5) и 3) следует, что Марина говорит по-испански. Из условия 1) следует, что Марина играет на гитаре. Из условия 2) следует что Лариса играет на пианино и говорит по-немецки. Из 5) следует, что Жанна говорит по-французски и играет на виолончели. Для Кати остаётся один вариант: она говорит по-английски и играет на скрипке.

 

№1340(1324) Древнегреческая задача.

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

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

Решение: Изучают математику 1/2всех учеников Пифагора; изучают природу  1/4 всех учеников; проводят время в размышлении 1/7 всех учеников; все эти ученики вместе составляют: 1/2+1/4+1/7=14/28+7/28+4/28=25/28. Женщины составляют 1-(25/28)=3/28 всех учеников. Женщин было трое, значит, всего учеников у Пифагора  было:  3:(3/28)=(3*28)/3=28. Ответ: у Пифагора было 28 учеников.

 

 

 

 

 

Заключение

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

Важную роль на начальной стадии ознакомления с теорией графов играют:

- простота: многие её задачи, формулировки  и возможные пути решения понятны  даже школьникам начальных классов;

- большая наглядность многих теоретико-графовых конструкций;

- естественность приёмов доказательства;

- яркий прикладной характер.

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

 

 

 

Список использованных источников:

 

          Список печатных источников:

1. Басакер Р., Саати Т. Конечные графы и сети. – М.: Наука, 1975г.
2. Березина Л. Графы и их применение. – М.: Просвещение, 1979г.
3. Берж К. Теория графов и ее применения. – М.: Изд-во иностр. лит., 1962г.
4. Зыков А. Основы теории графов. – М.: Наука, 1984г.
5. Уилсон Р. Введение в теорию графов. – М.: Мир, 1977г.
6. Виленкин Н. Математика 6 класс. – М.: Мнемозина, 2010г.

 

     Список электронных ресурсов:

7. Сайт «Дискретная математика (электронный учебник)» (http://lvf2004.com)
8. В.Н. Бурков, Д.А. Новиков – Элементы   теории   графов (http://www.mtas.ru/start/t_garf.pdf)