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

 

Введение

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

Термин «граф» приобрел право гражданства и вошел в математический язык в 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).