/>ПОМОРСКИЙГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ />им.М.В. ЛомоносоваКУРСОВАЯРАБОТА
ЭЙЛЕРОВЫ ГРАФЫ
Выполнила студентка 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]
Степенью вершины vi в графе G называется число рёбер, инцидентных vi, обозначаетсяdi.[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 называется чередующаясяпоследовательность вершин и рёбер v0,x1,v1,…vn-1,xn,vn; этапоследовательность начинается и кончается вершиной, и каждое ребропоследовательности инцидентно двум вершинам, одна из которых непосредственнопредшествует ему, а другая непосредственно следует за ним. Указанный маршрутсоединяет вершины v0 и vn иего можно обозначить v0v1v2…vn (наличиерёбер подразумевается). Эта последовательность иногда называется (v0-vn)-маршрутом. Маршрут замкнут, если v0=vn, и открыт в противном случае. Маршрут называетсяцепью, если все его рёбра различны, и простой цепью, если все вершины (аследовательно, и рёбра ) различны. Замкнутая цепь называется циклом. Замкнутыймаршрут называется простым циклом, если все его nвершин различны и n³3.
Граф G называется связным, если любая пара еговершин соединена простой цепью.[6]
Задача о кёнигсбергских мостах.
Отцомтеории графов является Эйлер (1707-1782), решивший в 1736г. широко известную вто время задачу, называвшуюся проблемой Кёнигсбергских мостов. В городеКёнигсберге (ныне Калининград) было два острова, соединенных семью мостами сберегами реки Преголя и друг с другом так, как показано на рисунке 5. Задачасостояла в следующем: найти маршрут прохождения всех четырёх частей суши,который начинался бы с любой из них, кончался бы на этой же части и ровно одинраз проходил по каждому мосту.
/> /> /> /> /> /> /> /> /> />
/> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> />
Рис.5.
Легко,конечно попытаться решить эту задачу эмпирически, производя перебор всехмаршрутов, но все попытки окончатся неудачей. Исключительный вклад Эйлера врешение этой задачи заключается в том, что он доказал невозможность такогомаршрута.
Для доказательства того, что задача не имеет решения, Эйлер обозначилкаждую часть суши точкой (вершиной), а каждый мост – линией (ребром),соединяющей соответствующие точки. Получился “граф”. Этот граф показан нарисунке 6, где точки отмечены теми же буквами, что и четыре части суши нарисунке 5.
/>
Рис.6.
Утверждение о не существовании “положительного” решения у этой задачиэквивалентно утверждению о невозможности обойти специальным образом граф,представленный на рисунке 6.
Отправляясь от этого частного случая Эйлер обобщил постановку задачи инашёл критерий существования обхода у данного графа, а именно граф должен бытьсвязным и каждая его вершина должна быть инцидентна чётному числу рёбер.[6]
Эйлеровы графы
Решение Эйлером задачи о Кёнигсбергских мостах привела к первойопубликованной работе по теории графов. Задачу об обходе мостов можно обобщитьи получить следующую задачу теории графов: можно ли найти в данном графе G цикл, содержащий все вершины и все рёбра? Граф, в которомэто возможно, называется эйлеровым. Таким образом, эйлеров граф имеет эйлеровцикл – замкнутую цепь, содержащую все вершины и все рёбра. Ясно, что эйлеровграф должен быть связным.[6]
Если снять ограничения на замкнутость цепи, то граф называетсяполуэйлеровым.
Теорема 1(критерий):
Граф с более чем одной вершиной имеет эйлеров цикл тогда и только тогда,когда он связный и каждая его вершина имеет чётную степень.
Доказательство: Предположим, что граф G имеетэйлеров цикл. Граф является связным, так как каждая вершина принадлежит циклу.Для всякой вершины v графа Gкаждый раз, когда эйлеров цикл проходит через v,он вносит 2 в степень v. Поэтому степень v чётная.
Обратно, нужно показать, что каждый связный граф, у которого степенивершин чётные, имеет эйлеров цикл. Докажем эту теорему, используя индукцию почислу вершин. Поскольку теорема тривиально справедлива при n£3, начнём индукцию с n=3. Предположим, что каждый связный граф, имеющий менее k вершин, и все вершины которого обладают чётной степенью,содержит эйлеров цикл. Пусть G – связный граф,содержащий k вершин, степени которых чётные. Допустим,что v1 и v2 - вершины графа G. Поскольку граф G – связный, существует путь из v1в v2.Поскольку степень v2 – чётная, существует неиспользованноеребро, по которому можно продолжить путь. Поскольку граф конечный, то путь, вконце концов, должен вернуться в v1 ,и эйлеров цикл С1 можно считать построенным. Если С1 являетсяэйлеровым циклом для G, тогда доказательство закончено.Если нет, то пусть G/ - подграф графа G, полученный удалением всех рёбер, принадлежащих С1.Поскольку С1 содержит чётное число рёбер, инцидентных каждойвершине, каждая вершина подграфа G/ имеетчётную степень.
Пусть e – ребро графа G/, пусть Ge – компонента графа G/, содержащая е. Поскольку G/ имеет менее, чем k, вершин, и у каждой вершиныграфа G/ чётная степень, граф G/ имеет эйлеров цикл. Пусть С2.Далее у С1 и С2 имеется общая вершина, допустим, а.Теперь можно продолжить эйлеров цикл, начиная его в а, пройти С1,вернуться в а, затем пройти С2 и вернуться в а. Если новый эйлеровцикл не является эйлеровым циклом для G, продолжаем использовать этот процесс, расширяя нашэйлеров цикл, пока, к конце концов, не получим эйлеров цикл для G.[1]
Из теоремы 1 следует, что если в связном графе Gнет вершин с нечётными степенями, то в G есть замкнутаяцепь, содержащая все вершины и все рёбра графа G.Аналогичный результат справедлив для связных графов, имеющих некоторое числовершин с нечётными степенями.
Следствие 1(а): Пусть G- связный граф, в котором2n вершин имеют нечётные степени, n>1.Тогда множество рёбер графа G можно разбить на n открытых цепей.
Следствие 1(б): Пусть G- связный граф, вкотором две вершины имеют нечётные степени. Тогда в Gесть открытая цепь, содержащая все вершины и все рёбра графа G(и начинающаяся в одной из вершин с нечётной степенью, а кончающаяся в другой).[6]
Эйлеровым путём в графе называется путь, содержащий все рёбра графа.Эйлеров путь называется собственным, если он не является эйлеровым циклом.[1]
Теорема 2: Если граф G обладаетэйлеровым путём с концами А и В (А не совпадает с В), то граф Gсвязный и А и В – единственные нечётные его вершины.
Доказательство: Связность графа следует из определения эйлерова пути. Если путь начинается в А, а заканчивается в другой вершине, то и А и В –нечётные даже если путь неоднократно проходил через А и В. В любую другуювершину графа путь должен был привести и вывести из неё, то есть все остальныевершины должны быть чётными.
Теорема 3: (обратная) Если граф G связныйи А и В единственные нечётные вершины его, то граф Gобладает эйлеровым путём с концами А и В.
Доказательство: Вершины А и В могут быть соединены ребром в графе, амогут быть соединены.
Если А и В соединены ребром, то удалим его; тогда все вершины станутчётными. Новый граф (по теореме 1) обладает эйлеровым циклом, началом и концомкоторого может служить любая вершина. Начнём эйлеров путь в вершине А и кончимего в вершине А. Добавим ребро (А, В) и получим эйлеров путь с началом в А иконцом в В.
Если А и В не соединены ребром, то к графу добавим новое ребро (А, В),тогда все вершины его станут чётными. Новый граф (по теореме 1) обладаетэйлеровым циклом. Начнём его из вершины А по ребру (А, В). Заканчивается путьтоже в вершине А. Если удалить теперь из полученного цикла ребро (А, В), тоостанется эйлеров путь с началом в В и концом в А или началом в А и концом В.
Таким образом, всякую замкнутую фигуру, имеющую в точности две нечётныевершины, можно начертить одним росчерком без повторений, начав в одной изнечётных вершин, а кончив в другой.
Теорема 4: Если связный граф G имеет 2k нечётных вершин, то найдётся семейство из kпутей, которые в совокупности содержат все рёбра графа в точности по одномуразу.
Доказательство: Половину нечётных вершин обозначим А1, А2,…, Аk, другую половину В1, В2,…, Вk(рис.7). Если вершины Аiи Вi (1
/>
Рис.7
Пусть G=(V,E) – ориентированный граф. Ориентированным циклом называетсяориентированный путь ненулевой длины из вершины в ту же вершину без повторенияребер.
Пусть G=(V,E) – ориентированный граф. Ориентированный цикл, которыйвключает все рёбра и вершины графа G, называетсяэйлеровым циклом. Говорят, что ориентированный граф Gимеет эйлеров цикл.
Теорема 5: Ориентированный граф имеет эйлеров цикл тогда и толькотогда, когда он связный и степень входа каждой вершины равна степени выхода.[1]
Оценка числа эйлеровых графов
Лемма: В любом графе число вершин нечётной степени чётно.
Доказательство: По теореме 1 сумма степеней всех вершин числочётное. Сумма степеней вершин чётной степени чётна, значит, сумма степенейвершин нечётной степени также чётна, значит, их чётное число.
Пусть G(p) – множествовсех графов с р вершинами, а Е(р) – множество эйлеровых графов с р вершинами.
Теорема 6: Эйлеровых графов почти нет, то есть
lim/>
Доказательство: Пусть E/ (р)– множество графов с р вершинами и чётными степенями. Тогда по теореме1 Е(р)ÌЕ/(p)и |Е(р)|£|Е/(p)|.В любом графечисло вершин нечётной степени чётно, следовательно, любой граф из Е/(p) можно получить из некоторого графа G(p-1), если добавить новую вершину и соединить её со всемистарыми вершинами нечётной степени. Следовательно, |Е/(p)| £|G(p-1)|. Но |G(p)|=2C(p, 2). Заметим, что
С(k,2)-C(k-1,2)=
= />
Далее имеем:
|Е(р)|£|Е/(p)| £|G(p-1)| = 2C( p-1,2) =2C(p,2)-(p-1) = |G(p)|2-(p-1)
и
/> , откуда lim/> . [3] Алгоритмпостроения эйлеровой цепи в данном эйлеровом графе.
Этот методизвестен под названием алгоритма Флёри.
Теорема7: Пусть G – эйлеров граф, тогда следующаяпроцедура всегда возможна и приводит к эйлеровой цепи графа G.Выходя из произвольной вершины и, идём по рёбрам графа произвольным образом,соблюдая лишь следующие правила:
1) стираемрёбра по мере их прохождения и стираем также изолированные вершины, которые приэтом образуются;
2) накаждом этапе идём по мосту только тогда, когда нет других возможностей.
Доказательство: Покажем сначала, что указанная процедура может быть выполнена на каждом этапе.Предположим, что мы достигли некоторой вершины V; тогдаесли V¹U, то оставшийся подграф H связен исодержит ровно две вершины нечётной степени, а именно Uи V. Согласно теореме 3 и определению полуэйлероваграфа, граф H содержит полуэйлерову цепь P из V в U.Поскольку удаление первого ребра цепи Р не нарушает связности графа Н, тоописанное в теореме построение (Т 1б)) возможно на каждом этапе. Если же V=U, то доказательство остаётся темже самым до тех пор, пока есть ещё рёбра, инцидентные вершине U.
Осталосьтолько показать, что данная процедура всегда приводит к полной эйлеровой цепи.Но это очевидно, так как в G не может быть рёбер,оставшихся не пройденными после использования последнего ребра, инцидентного U. В противном случае удаление некоторого ребра, смежногоодному из оставшихся, привело бы к несвязному графу, что противоречит условию2).[5] Глава 2. Практическая часть
Задачи:
1. Существует лиэйлеров цикл в графе G.Если существует, найдите его.[2]/> /> /> /> /> /> /> /> /> /> /> /> /> />
Решение:
А) Так как каждаявершина имеет чётную степень, то по критерию в этом графе существует эйлеровцикл: 1,4,6,9,10,8,5,3,2,4,7,10,11,8,6,5,2,1
Б) В этом графе такжекаждая вершина имеет чётную степень, значит, существует и эйлеров цикл: 1,2,3,4,5,3,1,4,5,2,1
В) Здесь каждаявершина имеет степень 5, то есть нечётную, следовательно, в этом графе (покритерию) нет эйлерова цикла.
2. Где на выставкеследовало бы сделать вход и выход (рис.8), чтобы можно было провести экскурсиюпо всем залам, побывав в каждом из них в точности один раз?[2]
/>
Рис.8
Решение:
В этомграфе вершины А и В имеют степень 3, то есть нечётную, следовательно, в нёмсуществует эйлеров путь с началом в одной из этих вершин и концом в другой.Значит, вход и выход следует установить в вершинах А и В.
3. Среди приведённых нижеграфов найдите те, которые имеют эйлеров цикл.[1]
/>
Решение:
а) Т.к.этот граф связный и каждая его вершина имеет чётную степень, то по критериюэйлерова графа, данный граф имеет эйлеров цикл:
a b e j i f c b d h j g f a c d e h g i a
б) Этотграф связный, но т.к. все его вершины имеют нечётную степень, то он не имеетэйлерова цикла.
в) Этотграф связный, но т.к. все его вершины имеют степень 3, то есть нечётную, то онне имеет эйлерова цикла.
г) Данныйграф связный, степени вершин а и с имеют нечётную степень, значит, этот графне имеет эйлерова цикла.
4. Среди приведённых нижеграфов найдите те, которые имеют эйлеров цикл.[1]
/>
Решение:
а) Графне является связным, то есть не выполняется первое условие критерия, значит, онне имеет эйлерова цикла.
б) Этотграф является связным и все его вершины имеют чётную степень, значит, покритерию эйлерова графа, он имеет эйлеров цикл:
a c f h I j k g d c b f I l j g e d a
в) Данныйграф связный, но степени вершин а и е нечётные, следовательно по критерию, этотграф не имеет эйлерова цикла.
г) Графявляется связным, но так как все его вершины имеют нечётную степень, то граф неимеет эйлерова цикла.
5. Среди приведённых нижеграфов найдите те, которые имеют собственный эйлеров путь.[1]
/>
Решение:
а) Граф связный, и толькодве его вершины (a и f) имеютнечётную степень, следовательно, то по теореме 3, граф имеет собственныйэйлеров путь.
б) Граф связный; deg(a)=3, deg(b)=3, deg(c)=3,то есть более двух вершин имеют нечётную степень, значит, не имеет эйлеровапути.
в) Этот граф связный итолько две вершины (с и j) имеют нечётную степень,значит, граф имеет собственный эйлеров путь.
г) Граф связный; deg(a)=3, deg(b)=4, deg(c)=1,deg(d)=3, то есть более двухвершин имеют нечётную степень, следовательно, в этом графе нет эйлерова пути.
6. Среди приведённых нижеграфов найдите те, которые имеют собственный эйлеров цикл.[1]
/>
Решение:
а) Данныйграф связный; deg(a)=3, deg(b)=2, deg(c)=3, deg(d)=2,deg(e)=2. Ровно две вершиныимеют нечётную степень, значит, по теореме 3, граф имеет собственный эйлеровпуть.
б) Графявляется связным и ровно две его вершины (е и f) имеютнечётную степень, значит, данный граф имеет собственный эйлеров путь.
в) Графсвязный, найдём степени вершин: deg(d)=5,deg(b)=5, deg(e)=5, нашлись три вершины, степень которых нечётная, значит,граф не имеет эйлерова пути.
г) Данный граф связный итолько две его вершины (а и b) имеют нечётную степень,значит, этот граф имеет собственный эйлеров путь.
7. Какие из следующихориентированных графов имеют эйлеровы циклы? [1]
/>
/>
Решение:
а) Графсвязный, найдём степени входа и выхода вершин (по теореме 5 степени входа ивыхода каждой вершины должны совпадать):
indeg(a)=2, outdeg(a)=1, то есть нашлась вершина, у которой не совпадают степенивхода и выхода, значит, граф не имеет эйлерова цикла.
б) Графсвязный, найдём степени вершин:
indeg(a)=2 outdeg(a)=2
indeg(b)=2 outdeg(b)=2
indeg(c)=2 outdeg(c)=2
indeg(d)=2 outdeg(d)=2
indeg(e)=2 outdeg(e)=2
Следовательно,по теореме 5, граф имеет эйлеров цикл.
в) Графсвязный, найдём степени вершин:
indeg(a)=2 outdeg(a)=2
indeg(b)=1 outdeg(b)=1
indeg(c)=3 outdeg(c)=1
Условиятеоремы 5 не выполняются, значит, граф не имеет эйлерова цикла.
г) ) Граф связный, найдёмстепени вершин:
indeg(a)=2 outdeg(a)=1
Следовательно,т.к. условия теоремы 5 не выполняются то, граф не имеет эйлерова цикла.
8. Какие из следующихориентированных графов имеют эйлеровы циклы? [1]
/>
Решение:
а) Графсвязный, найдём степени вершин:
indeg(a)=1 outdeg(a)=1
indeg(b)=5 outdeg(b)=1
Т.к. второе условие теоремы 5не выполняется, значит, граф не имеет эйлерова цикла.
б) Графне связный, то есть первое условие теоремы 5 не выполняется. Значит, граф неимеет эйлерова цикла.
в) Графсвязный, найдём степени вершин:
indeg(a)=2 outdeg(a)=1
Второеусловие теоремы 5 не выполняется, значит, граф не имеет эйлерова цикла.
г) Графсвязный, найдём степени вершин:
indeg(a)=2 outdeg(a)=2
indeg(b)=3 outdeg(b)=1
Граф неимеет эйлерова цикла, т.к. не выполняется второе условие теоремы 5.
9. Нарисунке план подземелья, в одной из комнат которого скрыты богатства рыцаря.После смерти рыцаря его наследники нашли завещание, в котором было сказано, чтодля отыскания сокровищ достаточно войти в одну из крайних комнат подземелья,пройти через все двери, причём в точности по одному разу через каждую;сокровища скрыты за той дверью, которая будет пройдена последней. В какойкомнате были скрыты сокровища?
/>/>/>/>/>/>/>/>/>/>1 2
/>/>/>/>/>/>/>/>/>/>/>/>3 4 5 6
/>/>/>/>/>/>/>/>/>/>7 8 9 10
/>/>/>/>/>/>/>/>/>/>/>/>/>/>11 12 13 14 15
/>/>/>/>/>/>/>/>/>/>16 17 18 19
/>/>20 21 /> /> /> /> /> />
Построимграф, вершинами которого являются комнаты подземелья, а рёбрами – двери. Затемнайдём такой путь, чтобы пройти по всем рёбрам (через все двери) в точности поодному разу.
/>
Данныйграф имеет эйлеров путь, так как только две вершины имеют нечётную степень, этовершины 6 и 18. Значит, вход и выход могут быть только в вершинах 6 и 18.
Так как комната 6 является крайней, то в ней будет вход, значит, последней комнатойбудет 18-ая, следовательно сокровища скрыты в этой комнате.
Заключение
В даннойработе были рассмотрены основные понятия теории графов, их виды. Большоевнимание уделили вопросу существования в них эйлеровых цепей и циклов,рассмотрели ряд теорем и свойств. Описали алгоритм нахождения эйлерова цикла впроизвольном графе, а в практической части показали его применение наконкретных примерах.
Известно,что эйлеровы графы получили широкое распространение и популярность благодарятому, что многие головоломки и задачи можно решить с использованием знанийтеории графов. Частные примеры таких головоломок и сюжетных задач былиприведены в практической части. Задачи на отыскание путей через лабиринты,близкие к задачам на эйлеровы графы, находят применение в современнойпсихологии и при конструировании вычислительных машин. Также с практическойточки зрения, сейчас графы применяют во многих других областях науки таких как:программирование, физика, химия, биология, экономика и т.д.
Литература
1. Андерсон, Джеймс А. Дискретная математика и комбинаторика: пер. с англ.– М.: Издательский дом «Вильямс», 2003. – 960с.
2. Березина Л. Ю. Графы и их применение. – М.: Просвещение, 1979.
3. Новиков С.А. Дискретная математика для программистов – СПб.: Питер,2001. – 304с.
4. Оре о. Графы и их применение. – М.: Мир,1973.
5. Уилсон Р. Введение в теорию графов. – М.: Мир, 1977.
6. Харари Ф. Теория графов. – М.: Мир, 1973.