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

1.

ЭЙЛЕРОВЫ И
ГАМИЛЬТОНОВЫ
ГРАФЫ
Авторы: Кляпнева Ангелина (417 гр.)
Семиков Алексей (419 гр.)
Научные руководители: Павлов Игорь Сергеевич
Харчева Анна Александровна
ННГУ им. Н.И. Лобачевского, радиофизический факультет,
Нижний Новгород, май 2021 г.

2.

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

3.

Что такое эйлеров граф?
ОПРЕДЕ
ЛЕНИЕ
Цикл, содержащий все ребра графа, называется эйлеровым циклом.
4
6
2
5
1
3
ЗАМЕЧАНИЕ
Эйлеров цикл содержит не только все ребра (конечно, по
одному разу), но и все вершины графа (одна вершина может
входить в цикл несколько раз).

4.

ОПРЕДЕ
ЛЕНИЕ
ЗАДАЧА
Связный граф, в котором существует эйлеров цикл, называется
эйлеровым графом.
Задача о кенигсбергских мостах
C
B
A
D

5.

Критерий эйлеровости графа: Связный нетривиальный граф G
является эйлеровым тогда и только тогда, когда степени всех его
вершин четные.
ТЕОРЕМА
ЭЙЛЕРОВ ГРАФ
Пример 1
ЗАМЕЧАНИЕ
ЭЙЛЕРОВ ГРАФ
Пример 2
НЕ(!) ЭЙЛЕРОВ ГРАФ
Пример 3
Эйлеров граф можно изобразить одним росчерком пера, причем
процесс такого изображения должен начинаться и заканчиваться в
одной и той же вершине.

6.

ПРИМЕР
Последнее условие (процесс такого изображения должен начинаться и
заканчиваться в одной и той же вершине) чрезвычайно важное, его
несоблюдение приводит к ошибочному увеличению числа эйлеровых графов.

7.

Полуэйлеров граф?
ОПРЕДЕ
ЛЕНИЕ
Если граф имеет цепь, содержащую все его ребра, то такая цепь называется
эйлеровой цепью, а сам граф называется полуэйлеровым.

8.

ТЕОРЕМА
ТЕОРЕМА
Критерий полуэйлеровости графа: Cвязный граф G
обладает эйлеровой цепью в том и только том случае,
если он имеет ровно 2 вершины нечетной степени.
Теорема об оценке числа эйлеровых графов: где G(р) –
множество всех графов с р вершинами, Э(р) – множество
эйлеровых графов с р вершинами.

9.

Очевидно, что эйлеров граф не имеет мостов
(т.к. мост не принадлежит ни одному из циклов графа).
Эйлеров граф (мостов нет)
НЕ эйлеров граф
МОСТ

10.

Что такое Гамильтонов граф? 20
ОПРЕД
ЕЛЕНИЕ
ОПРЕД
ЕЛЕНИ
Е
Граф, имеющий
гамильтонов
цикл, называется
гамильтоновым
графом
1
8
19
Простая цепь, проходящая
через все вершины
данного графа, называется
гамильтоновой цепью, а
простой цикл, проходящий
через все вершины
данного графа, называется
гамильтоновым циклом.
2
7
9
3
6
10
15
4
14
5
11
18
12
13
17
16

11.

ЗАМЕЧАНИЕ
Любой граф можно превратить в гамильтонов, добавив
достаточное количество вершин и ребер, соединяющих эти
новые вершины между собой и с некоторыми из старых.
TAP
TO
UPGRADE
Граф НЕ гамильтонов!
Граф гамильтонов!
Ура!

12.

ТЕОРЕМА
ТЕОРЕМА
Теорема об оценке числа гамильтоновых графов: Почти все графы
являются гамильтоновыми, т.е. где G(р) – множество всех графов
с р вершинами, H(р) – множество гамильтоновых графов с р
вершинами.
Необходимое условие гамильтоновости: гамильтонов граф
должен быть, как минимум, двухсвязным.

13.

ТЕОРЕМА
1-е достаточное условие гамильтоновости. Теорема Г. Дирака
(1952 г.). Если в графе G(V, E) с , то граф G является гамильтоновым.
ТЕОРЕМА
2-е достаточное условие гамильтоновости. Теорема О. Оре (1960 г.).
Если в связном графе G(V, E) , то граф G гамильтонов.
ТЕОРЕМА
3-е достаточное условие гамильтоновости. Теорема В. Хватала (1972
г.) Граф со степенной последовательностью вершин является
гамильтоновым, если для всякого k, удовлетворяющего неравенствам
, при выполнении условия следует, что
не существует
критерия гамильтоновости графа!

14.

ГАМИЛЬТОНОВ ГРАФ
НЕ ГАМИЛЬТОНОВ
ГРАФ
НЕ ГАМИЛЬТОНОВ
ГРАФ
Пример 1
Пример 2
Пример 3

15.

ЗАДАЧА
Является ли данный граф гамильтоновым?

16.

СПАСИБО ЗА
ВНИМАНИЕ!