ПОМОРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

им. М.В. Ломоносова

КУРСОВАЯ РАБОТА

ЭЙЛЕРОВЫ ГРАФЫ

Выполнила студентка 4 курса

42 группы математического

факультета Катышева Н.Г.

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

Токаревская С.А.

Архангельск

2004

Оглавление

Введение 3

Глава 1. Теоретическая часть. 4

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

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

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

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

Оценка числа эйлеровых графов 13

Алгоритм построения эйлеровой цепи в данном эйлеровом графе. 14

Глава 2. Практическая часть 15

Заключение 24

Литература 25

Введение

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

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

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

Глава 1. Теоретическая часть.

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

Граф G – пара (V,X), где V конечное непустое множество, содержащее p вершин, а множество Х содержит q неупорядоченных пар различных вершин из V.

Каждую пару X={u,v} вершин в Х называют ребром графа G и говорят, что Х соединяет u и v.Мы будем писать X=uv и говорить, что u и v – смежные вершины. Вершина u и ребро Х инцидентны, так же как v и Х. Если два различных ребра X и Y инцидентны одной и той же вершине, то они называются смежными. Граф с р вершинами и q ребрами называется (p;q)- графом. Граф (1,0)- называется тривиальным.[6]

Если элементом множества V может быть пара одинаковых элементов u, то такой элемент множества V называется петлёй.[3]

Типы графов:

• Мультиграф, в нём не допускаются петли, но пары вершин могут соединяться более чем одним ребром, эти рёбра называются кратными (рис.1).

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

Рис.1 Рис.2

• Ориентированный граф, или орграф, состоит из конечного непустого множества V вершин и заданного набора Х упорядоченных пар различных вершин. Элементы из Х называются ориентированными рёбрами, или дугами. Нет петель и кратных дуг (рис. 3).

Рис.3

Рис.4

• Направленный граф – это орграф, не имеющий симметричных пар ориентированных рёбер (рис.4).

• Помеченные графы (или перенумерованные), если его вершины отличаются одна от другой какими-либо пометками. В качестве пометок обычно используются буквы или целые числа.[6]

Степенью вершины v_i в графе G называется число рёбер, инцидентных v_i ,обозначается d_i.[6] Для орграфа вводятся понятия степени входа и выхода. Степенью выхода вершины v называется количество рёбер, для которых v является начальной вершиной, обозначается outdeg(v). Степенью входа вершины v называется количество рёбер , для которых v является конечной вершиной, обозначается indeg(v). Если indeg(v)=0, то вершина v называется источником. Если outdeg(v)=0, то вершина v называется стоком.[1]

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

Граф G^/(U^/,V^/) называется подграфом графа G(U,V), если U^/U и V^/V. Обозначение: G^/G.

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

Маршрутом в графе G называется чередующаяся последовательность вершин и рёбер v₀,x₁,v₁,…v_n-1,x_n,v_n; эта последовательность начинается и кончается вершиной, и каждое ребро последовательности инцидентно двум вершинам, одна из которых непосредственно предшествует ему, а другая непосредственно следует за ним. Указанный маршрут соединяет вершины v₀ и v_n и его можно обозначить v₀v₁v₂…v_n (наличие рёбер подразумевается). Эта последовательность иногда называется (v₀-v_n)-маршрутом. Маршрут замкнут, если v₀=v_n, и открыт в противном случае. Маршрут называется цепью, если все его рёбра различны, и простой цепью, если все вершины (а следовательно, и рёбра ) различны. Замкнутая цепь называется циклом. Замкнутый маршрут называется простым циклом, если все его n вершин различны и n3.

Граф G называется связным, если любая пара его вершин соединена простой цепью.[6]

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

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

Рис.5.

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

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

Рис.6.

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

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

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

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

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

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

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

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

Обратно, нужно показать, что каждый связный граф, у которого степени вершин чётные, имеет эйлеров цикл. Докажем эту теорему, используя индукцию по числу вершин. Поскольку теорема тривиально справедлива при n3, начнём индукцию с 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 .[1]

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

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

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

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

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

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