Дискретная математика
Задача о мостах Кёнигсберга
Граф – схема мостов
Известные головоломки
Эйлеров граф
Полуэйлеров граф
Теорема Эйлера (условие эйлеровости графа)
Теорема (условие полуэйлеровости графа)
Эйлеров, полуэйлеров, не эйлеров графы
Алгоритм Флери
Пример построения эйлерова цикла
Гамильтонов граф
Полугамильтонов граф
Гамильтонов, полугамильтонов графы
1.52M
Category: mathematicsmathematics

Обходы. Эйлеров и гаильтонов графы

1. Дискретная математика

Обходы.
Эйлеров и гаильтонов графы

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

Карта мостов Кенигсберга во времена
Эйлера

3. Граф – схема мостов

Части города – вершины, мосты – ребра.
Из рисунка видно,
что задача,
Поставленная
Эйлером,
не выполнима.

4. Известные головоломки

Сабли Магомеда
Пентаграмма

5. Эйлеров граф

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

6. Полуэйлеров граф

Эйлеровой цепью в н-графе
называется цепь, обходящая все
ребра графа (ровно по одному
разу).
Полуэйлеров граф – граф, в
котором есть эйлерова цепь

7. Теорема Эйлера (условие эйлеровости графа)

Для того, чтобы произвольный
н-граф был эйлеровым,
необходимо и достаточно, чтобы
1)он был связен и
2) локальные степени всех его
вершин были четными.

8. Теорема (условие полуэйлеровости графа)

Для того, чтобы произвольный н-граф
был полуэйлеровым, необходимо и
достаточно, чтобы: 1) он был связен и
2) локальные степени всех его
вершин, кроме двух, были четными.
Вершины с нечетными степенями
являются началом и концом
эйлеровой цепи

9. Эйлеров, полуэйлеров, не эйлеров графы

Эйлеров граф
Полуэйлеров граф
Не эйлеров граф

10. Алгоритм Флери

При построении эйлерова цикла
начинаем с произвольной вершины и
двигаемся в произвольном направлении
выполняя два условия:
1)стираем пройденные ребра и
изолированные вершины, которые при
этом появляются;
2) идем по мосту, только если нет
другой возможности.

11. Пример построения эйлерова цикла

12. Гамильтонов граф

Гамильтоновым циклом в нграфе называется простой цикл,
обходящий все вершины графа
(ровно по одному разу).
Гамильтонов граф – граф, в
котором есть гамильтонов цепь.

13. Полугамильтонов граф

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

14. Гамильтонов, полугамильтонов графы

Гамильтонов граф
Полгамильтонов граф
English     Русский Rules