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

Июль 22, 2022

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

Содержание

2. Задача о мостах Кёнигсберга Карта мостов Кенигсберга во времена Эйлера
3. Граф – схема мостов Части города – вершины, мосты – ребра. Из рисунка видно, что задача,
4. Известные головоломки Сабли Магомеда Пентаграмма
5. Эйлеров граф Эйлеровым циклом в н-графе называется цикл, обходящий все ребра графа (ровно по одному разу.
6. Полуэйлеров граф Эйлеровой цепью в н-графе называется цепь, обходящая все ребра графа (ровно по одному разу).
7. Теорема Эйлера (условие эйлеровости графа) Для того, чтобы произвольный н-граф был эйлеровым, необходимо и достаточно, чтобы
8. Теорема (условие полуэйлеровости графа) Для того, чтобы произвольный н-граф был полуэйлеровым, необходимо и достаточно, чтобы: 1)
9. Эйлеров, полуэйлеров, не эйлеров графы Эйлеров граф Полуэйлеров граф Не эйлеров граф
10. Алгоритм Флери При построении эйлерова цикла начинаем с произвольной вершины и двигаемся в произвольном направлении выполняя
11. Пример построения эйлерова цикла
12. Гамильтонов граф Гамильтоновым циклом в н-графе называется простой цикл, обходящий все вершины графа (ровно по одному
13. Полугамильтонов граф Гамильтоновой цепью в н-графе называется простая цепь, обходящий все вершины графа (ровно по одному
15. Скачать презентацию

Слайд 2

Задача о мостах Кёнигсберга
Карта мостов Кенигсберга во времена Эйлера

Слайд 3

Граф – схема мостов
Части города – вершины, мосты – ребра.
Из рисунка

видно,
что задача,
Поставленная
Эйлером,
не выполнима.

Слайд 4

Известные головоломки
Сабли Магомеда
Пентаграмма

Слайд 5

Эйлеров граф
Эйлеровым циклом в н-графе называется цикл, обходящий все ребра графа

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

Слайд 6

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

(ровно по одному разу).
Полуэйлеров граф – граф, в котором есть эйлерова цепь

Слайд 7

Теорема Эйлера (условие эйлеровости графа)
Для того, чтобы произвольный н-граф был эйлеровым,

необходимо и достаточно, чтобы
он был связен и
локальные степени всех его вершин были четными.

Слайд 8

Теорема (условие полуэйлеровости графа)
Для того, чтобы произвольный н-граф был полуэйлеровым, необходимо

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

Слайд 9

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

Слайд 10

Алгоритм Флери
При построении эйлерова цикла начинаем с произвольной вершины и двигаемся

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

Слайд 11

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

Слайд 12

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

графа (ровно по одному разу).
Гамильтонов граф – граф, в котором есть гамильтонов цепь.

Слайд 13

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

графа (ровно по одному разу).
Полугамильтонов граф – граф, в котором есть гамильтонова цикл.