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

Федеральное агентство по образованию

ФГОУ ВПО

«Чувашский государственный  университет им. Ульянова»

Алатырский филиал

Факультет управления и  экономики

Кафедра высшей математики и информационных технологий

 

 

 

Курсовая работа

 

по дисциплине: Дискретная математика

 

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

 

 

 

 

                                                                                 

 

 

 

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

                                                                          студент группы АФТ   0508                          

                                                                          Мещанинов А.А.  

 

                                                                          проверила

                                                                           научный руководитель                 

                                                                           Немкова М.П.

 

 

 

 

 

 

Алатырь 2009г.

 

Содержание

 

Введение……………………………………………………… 3

Основные понятия теории графов………………………….. 4-6

Маршруты и связность……………………………………… 7

Задача о Кениксбергских мостах…………………………… 8-9

Эйлеровы графы……………………………………………... 10-13

Операции на графах…………………………………………. 14-19

Применение теории графов…………………………………. 20

Заключение…………………………………………………… 21

Литература……………………………………………………. 22

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

Граф G – пара (M,R), где M - конечное непустое множество,  содержащее  p вершин, а множество R – множество содержащее q рёбер состоящих из пар вершин из множества M.

Каждую пару {a,b} вершин из М называют ребром графа G .Мы будем писать a,bÎR и говорить, что a и b – смежные вершины. Каждое ребро инцидентно двум вершинам, которое оно соединяет, при этом вершины a и b являются для ребра (a,b) кольцевыми точками называемыми смежными. Граф с р вершинами и q ребрами называется (p;q)- графом. Граф (1,0)- называется тривиальным.

Ребро кольцевые вершины которого совпадают называется петлёй.

Типы графов:

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

 

 

                                              Рис.1                                  Рис.2

 

• Ориентированный граф, или орграф, - это граф в котором нет петель и кратных дуг и состоящий из рёбер которые соединяют 2 вершины и имеют направление от одной вершины к другой (рис. 3).

 

 

 

 

 

 

• Направленный граф – это орграф, не имеющий симметричных пар ориентированных рёбер (рис.4).
• Помеченные графы (или перенумерованные) – графы в которых вершины отличаются одна от другой какими-либо пометками. В качестве пометок обычно используются буквы или целые числа.
• Граф называется полным, если он не содержит петель и кратных рёбер, но каждая пара его вершин соединена ребром.
• Степенью вершины а_i  в графе G называется число рёбер, инцидентных v_i ,обозначается d_i.. Для орграфа вводятся понятия степени входа и выхода. Степенью выхода вершины а называется количество рёбер, для которых а является начальной вершиной, обозначается outdeg(а). Степенью входа вершины а называется количество рёбер , для которых а является конечной вершиной, обозначается indeg(а). Если indeg(а)=0, то вершина а называется источником. Если outdeg(а)=0, то вершина а называется стоком.
• Дополнением графа G называется граф `G имеющий те же вершины что и G и рёбра которые нужно добавить к G чтобы получился

     полный граф.

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

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

 

• Несвязный граф, состоящий исключительно из деревьев, называется лесом.

  Дерево, все n  вершин которого имеют номера от 1 до n, называют деревом с перенумерованными вершинами.

 

Информация о структуре  графа может быть задана матрицей бинарного отношения. Матрицей смежности называется матрица, элементы которой определяются по правилу: элемент матрицы равен 1 если дуга (a,b) ÎR, и равен 0 если  (a,b)ÏR.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Маршруты и  связность

Граф G^/(М^/,R^/) называется подграфом графа G(M,R), если  M^/ÌM и R^/ÌR∩(M^/)². Обозначение: G^/ÌG.

Если M^/=M, то G^/ называется остовным подграфом G.

Маршрутом в графе G называется чередующаяся последовательность вершин и рёбер u₀,a₁,u₁,…u_n-1,a_n,u_n; эта последовательность начинается вершиной u₁ и кончается вершиной u_n, и каждое ребро последовательности инцидентно двум вершинам, одна из которых непосредственно предшествует ему, а другая непосредственно следует за ним. Указанный маршрут соединяет вершины u₀ и u_n и его можно обозначить u_0,u_1,u_2,…,v_n. Эта последовательность иногда называется (u₀-u_n)-маршрутом. Маршрут замкнут (называется циклическим), если u₀=u_n, и открыт в противном случае. Маршрут называется цепью, если все его рёбра различны, и простой цепью, если все вершины (а следовательно, и рёбра) различны. Маршрут называется путём, если все его дуги различны. Путь называется контуром если первая и последняя его вершины совпадают. Вершина b называется достижимой из вершины a, если существует (а,b) путь. Замкнутая цепь называется циклом. Замкнутый маршрут называется простым циклом, если все его n вершин различны и n³3. Минимальная из длин цикла называется его обхватом.

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

 

 

Задача  о  кёнигсбергских  мостах.

Отцом теории графов является Эйлер (1707-1782), решивший в 1736г. широко известную в  то время задачу, называвшуюся проблемой  Кёнигсбергских мостов. В городе Кёнигсберге (ныне Калининград) было два острова, соединенных семью мостами с берегами реки Преголя  и друг с другом так, как показано на рисунке 5. Задача состояла в следующем: найти маршрут прохождения всех четырёх частей суши, который начинался бы с любой из них, кончался бы на этой же части и ровно один раз проходил по каждому мосту.

                                          

 Рис.5.

 

 

 

                                                      

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

Для доказательства того, что задача не имеет решения, Эйлер обозначил  каждую часть суши точкой (вершиной), а каждый мост – линией (ребром), соединяющей соответствующие точки. Получился “граф”. Этот граф показан на рисунке 6, где точки отмечены теми же буквами, что и четыре части суши на рисунке 5. 

 

 

 

 

 

                    Рис.6.

Утверждение о не существовании  “положительного” решения у этой задачи эквивалентно утверждению о невозможности обойти специальным образом граф, представленный на рисунке 6.

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

 

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

Решение Эйлером задачи о Кёнигсбергских мостах привела к первой опубликованной работе по теории графов. Задачу об обходе мостов можно обобщить и получить следующую задачу теории графов: можно ли найти в данном графе G цикл, содержащий все вершины и все рёбра? Граф, в котором это возможно, называется эйлеровым. Таким образом, эйлеров граф имеет эйлеров цикл – замкнутую цепь, содержащую все вершины и все рёбра. Ясно, что эйлеров граф должен быть связным.

Если снять ограничения на замкнутость  цепи, то граф называется полуэйлеровым.

 

Теорема 1(критерий):

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

Доказательство:  Предположим, что граф G имеет эйлеров цикл. Граф является связным, так как каждая вершина принадлежит циклу. Для всякой вершины v графа G каждый раз, когда эйлеров цикл проходит через v, он вносит 2 в степень v. Поэтому степень v чётная.

Обратно, нужно  показать, что каждый связный граф, у которого степени вершин чётные, имеет эйлеров цикл. Докажем эту  теорему, используя индукцию по числу  вершин. Поскольку теорема тривиально справедлива при n£3, начнём индукцию с n=3. Предположим, что каждый связный граф, имеющий менее k вершин, и все вершины которого обладают чётной степенью, содержит эйлеров цикл. Пусть G – связный граф, содержащий k вершин, степени которых чётные. Допустим, что v₁ и v₂ - вершины графа G. Поскольку граф G – связный, существует путь из v₁ в v₂ .Поскольку степень v₂ – чётная, существует неиспользованное ребро, по которому можно продолжить путь. Поскольку граф конечный, то путь, в конце концов, должен вернуться в v₁  , и эйлеров цикл С₁ можно считать построенным. Если С₁ является эйлеровым циклом для G, тогда доказательство закончено. Если нет, то пусть G^/ - подграф графа G, полученный удалением всех рёбер, принадлежащих С₁. Поскольку С₁ содержит чётное число рёбер, инцидентных каждой вершине, каждая вершина подграфа G^/ имеет чётную степень.

Пусть e – ребро графа G^/ , пусть G_e – компонента графа G^/ , содержащая е. Поскольку G^/ имеет менее, чем k, вершин, и у каждой вершины графа G^/ чётная степень, граф G^/ имеет эйлеров цикл. Пусть С₂  является эйлеровым циклом для G^/. Далее у С₁ и С₂ имеется общая вершина, допустим, а. Теперь можно продолжить эйлеров цикл, начиная его в а, пройти С₁ , вернуться в а, затем пройти С₂ и вернуться в а. Если новый эйлеров цикл не является эйлеровым циклом для G , продолжаем использовать этот процесс, расширяя наш эйлеров цикл, пока, в конце концов, не получим эйлеров цикл для G .

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

Следствие 1(а):  Пусть G- связный граф, в котором 2n вершин имеют нечётные степени, n>1. Тогда множество рёбер графа G можно разбить на n открытых цепей.

Следствие 1(б):   Пусть G- связный граф, в котором две вершины имеют нечётные степени. Тогда в G есть открытая цепь, содержащая все вершины и все рёбра графа G (и начинающаяся в одной из вершин с нечётной степенью, а кончающаяся в другой).

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

Теорема 2:   Если граф G обладает эйлеровым путём с концами А и В (А не совпадает с В), то граф G связный и А и В – единственные нечётные его вершины.

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

Теорема 3: (обратная) Если граф G связный и А и В единственные нечётные вершины его, то граф G обладает эйлеровым путём с концами А и В.

Доказательство:   Вершины А  и В могут быть соединены ребром в графе, а могут быть соединены.

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

Если А и В не соединены  ребром, то к графу добавим новое  ребро (А,В), тогда все вершины  его станут чётными. Новый граф (по теореме 1) обладает эйлеровым циклом. Начнём его из вершины А по ребру (А,В). Заканчивается путь тоже в вершине А. Если удалить теперь из полученного цикла ребро (А,В), то останется эйлеров путь с началом в В и концом в А или началом в А и концом В.