Презентация на тему: Дискретная математика

Дискретная математика
Задача о мостах Кёнигсберга
Граф – схема мостов
Известные головоломки
Эйлеров граф
Полуэйлеров граф
Теорема Эйлера (условие эйлеровости графа)
Теорема (условие полуэйлеровости графа)
Эйлеров, полуэйлеров, не эйлеров графы
Алгоритм Флери
Пример построения эйлерова цикла
Гамильтонов граф
Полугамильтонов граф
Гамильтонов, полугамильтонов графы
1/14
Средняя оценка: 4.5/5 (всего оценок: 83)
Код скопирован в буфер обмена
Скачать (449 Кб)
1

Первый слайд презентации: Дискретная математика

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

Изображение слайда
2

Слайд 2: Задача о мостах Кёнигсберга

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

Изображение слайда
3

Слайд 3: Граф – схема мостов

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

Изображение слайда
4

Слайд 4: Известные головоломки

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

Изображение слайда
5

Слайд 5: Эйлеров граф

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

Изображение слайда
6

Слайд 6: Полуэйлеров граф

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

Изображение слайда
7

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

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

Изображение слайда
8

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

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

Изображение слайда
9

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

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

Изображение слайда
10

Слайд 10: Алгоритм Флери

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

Изображение слайда
11

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

Изображение слайда
12

Слайд 12: Гамильтонов граф

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

Изображение слайда
13

Слайд 13: Полугамильтонов граф

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

Изображение слайда
14

Последний слайд презентации: Дискретная математика: Гамильтонов, полугамильтонов графы

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

Изображение слайда