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

содержащих все рёбра графа.[2]


Рис.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. Выходя из произвольной вершины и, идём по рёбрам графа произвольным образом, соблюдая лишь следующие правила:

стираем рёбра по мере их прохождения и стираем также изолированные вершины, которые при этом образуются;

на каждом этапе идём по мосту только тогда, когда нет других возможностей.

Доказательство: Покажем сначала, что указанная процедура может быть выполнена на каждом этапе. Предположим, что мы достигли некоторой вершины V; тогда если V№U, то оставшийся подграф H связен и содержит ровно две вершины нечётной степени, а именно U и V. Согласно теореме 3 и определению полуэйлерова графа, граф H содержит полуэйлерову цепь P из V в U. Поскольку удаление первого ребра цепи Р не нарушает связности графа Н, то описанное в теореме построение (Т 1б)) возможно на каждом этапе. Если же V=U, то доказательство остаётся тем же самым до тех пор, пока есть ещё рёбра, инцидентные вершине U.

Осталось только показать, что данная процедура всегда приводит к полной эйлеровой цепи. Но это очевидно, так как в G не может быть рёбер, оставшихся не пройденными после использования последнего ребра, инцидентного U. В противном случае удаление некоторого ребра, смежного одному из оставшихся, привело бы к несвязному графу, что противоречит условию 2).[5]

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


Задачи:

Существует ли эйлеров цикл в графе 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, то есть нечётную, следовательно, в этом графе (по критерию) нет эйлерова цикла.

Где на выставке следовало бы сделать вход и выход (рис.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

Построим граф, вершинами которого являются комнаты подземелья, а рёбрами – двери. Затем найдём такой путь, чтобы пройти по всем рёбрам (через все двери) в точности по одному разу.

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


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


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

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

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Подробнее

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: