Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.

Для правообладателей

Обратная связь

Email: Нажмите что бы посмотреть 

Яндекс.Метрика

Презентация на тему Обходы. Эйлеров и гаильтонов графы

Содержание

Задача о мостах КёнигсбергаКарта мостов Кенигсберга во времена Эйлера
Обходы.Эйлеров и гаильтонов графыДискретная математика Задача о мостах КёнигсбергаКарта мостов Кенигсберга во времена Эйлера Граф – схема мостовЧасти города – вершины, мосты – ребра.Из рисунка видно, Известные головоломкиСабли Магомеда Эйлеров графЭйлеровым циклом в н-графе называется цикл, обходящий все ребра графа (ровно Полуэйлеров графЭйлеровой цепью в н-графе называется цепь, обходящая все ребра графа (ровно Теорема Эйлера (условие эйлеровости графа)Для того, чтобы произвольный Теорема (условие полуэйлеровости графа)Для того, чтобы произвольный н-граф был полуэйлеровым, необходимо и Эйлеров, полуэйлеров, не эйлеров графыЭйлеров граф Алгоритм ФлериПри построении эйлерова цикла начинаем с произвольной вершины и двигаемся в Пример построения эйлерова цикла Гамильтонов графГамильтоновым циклом в н-графе называется простой цикл, обходящий все вершины графа Полугамильтонов графГамильтоновой цепью в н-графе называется простая цепь, обходящий все вершины графа Гамильтонов, полугамильтонов графыГамильтонов граф
Слайды презентации

Слайд 2



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

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

Эйлера

Слайд 3



Граф – схема мостов
Части города – вершины, мосты

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

– ребра.

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


Слайд 4



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





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

Пентаграмма

Слайд 5



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

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

все ребра графа (ровно по одному разу.
Эйлеров граф –

граф, в котором есть эйлеров цикл

Слайд 6



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

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

все ребра графа (ровно по одному разу).
Полуэйлеров граф –

граф, в котором есть эйлерова цепь

Слайд 7



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

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

н-граф был эйлеровым, необходимо и достаточно,

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

Слайд 8



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

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

был полуэйлеровым, необходимо и достаточно, чтобы: 1) он был

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

Слайд 9



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

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




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


Не эйлеров граф

Слайд 10



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

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

вершины и двигаемся в произвольном направлении выполняя два условия:
стираем

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

Слайд 11



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

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

Слайд 12



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

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

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

– граф, в котором есть гамильтонов цепь.

Слайд 13



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

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

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

– граф, в котором есть гамильтонова цикл.
  • Имя файла: obhody-eylerov-i-gailtonov-grafy.pptx
  • Количество просмотров: 96
  • Количество скачиваний: 0
- Предыдущая М.И. Кутузов
Следующая - Как научить ребёнка работать над проектом

Похожие презентации

Измерение времени Измерение времени 109
Авторские ученические тесты как одно из средств подготовки к ЕГЭ Авторские ученические тесты как одно из средств подготовки к ЕГЭ 126
Интерактивная играЗасели домики взята с сайта http://ya-umni4ka Интерактивная играЗасели домики взята с сайта http://ya-umni4ka 110
Конспекты уроков презентация к уроку по математике (3 класс) Конспекты уроков презентация к уроку по математике (3 класс) 113
Площадь фигуры Площадь фигуры 106
Определители и их свойства Определители и их свойства 142
Презентация к уроку математики по теме Способ вычитания столбиком 2 класс ПНШ презентация к уроку по математике (2 класс) Презентация к уроку математики по теме Способ вычитания столбиком 2 класс ПНШ презентация к уроку по математике (2 класс) 131
Методы решения тригонометрических уравнений (10 класс) Методы решения тригонометрических уравнений (10 класс) 99
Презентация по математике на тему Формулы (5 класс) Презентация по математике на тему Формулы (5 класс) 132
Числовые неравенства и числовые промежутки Числовые неравенства и числовые промежутки 88
Презентация к уроку Умножение смешанных дробей Презентация к уроку Умножение смешанных дробей 114
Учим различать предметы по форме, воспитатель Солдатченкова И.А. МАДОУ ЦРР Д/С № 14 г. Кропоткин презентация к уроку по математике (младшая группа) по теме Учим различать предметы по форме, воспитатель Солдатченкова И.А. МАДОУ ЦРР Д/С № 14 г. Кропоткин презентация к уроку по математике (младшая группа) по теме 41
Математические тренажеры презентация к уроку по математике (старшая, подготовительная группа) Математические тренажеры презентация к уроку по математике (старшая, подготовительная группа) 103
Натуральные числа и шкалы Натуральные числа и шкалы 125
Математическая игра по математике для 6-7 классов Я счастливчик! Математическая игра по математике для 6-7 классов Я счастливчик! 161
Алгоритм нахождения производной Алгоритм нахождения производной 97
Проецирование Проецирование 107
Обобщающий урок по теме: Сравнение чисел и отрезков план-конспект урока по математике (1 класс) Обобщающий урок по теме: Сравнение чисел и отрезков план-конспект урока по математике (1 класс) 122
Устные упражнения Устные упражнения 119
Методическая разработка. Конспект НОД во второй младшей группе с использованием ИКТ. Тема: Сказка в гости к нам пришла(по сюжету русской народной сказки Репка). методическая разработка по математике (младшая группа) Методическая разработка. Конспект НОД во второй младшей группе с использованием ИКТ. Тема: Сказка в гости к нам пришла(по сюжету русской народной сказки Репка). методическая разработка по математике (младшая группа) 100
Пятый постулат Евклида. Неевклидова геометрия Пятый постулат Евклида. Неевклидова геометрия 127
презентация по математике Табличное умножение и деление 2 класс презентация к уроку математики (2 класс) по теме презентация по математике Табличное умножение и деление 2 класс презентация к уроку математики (2 класс) по теме 100
Опорные таблицы Опорные таблицы 122
Неопределенный интеграл: свойства и методы интегрирования Неопределенный интеграл: свойства и методы интегрирования 107
Формулы сокращенного умножения. Представление выражения в виде многочлена Формулы сокращенного умножения. Представление выражения в виде многочлена 109
Методическая разработка по проведению непрерывной непосредственно образовательной деятельности образовательной ситуации ФЭМП по теме Играем и считаем в старшей группе (6 -7 лет) план-конспект занятия по математике (старшая группа) Методическая разработка по проведению непрерывной непосредственно образовательной деятельности образовательной ситуации ФЭМП по теме Играем и считаем в старшей группе (6 -7 лет) план-конспект занятия по математике (старшая группа) 103
Решение систем линейных алгебраических уравнений Решение систем линейных алгебраических уравнений 88
Путешествие в Египет. презентация к уроку по математике (4 класс) по теме Путешествие в Египет. презентация к уроку по математике (4 класс) по теме 124
Показательная функция, её график и свойства. Показательная функция, её график и свойства. 51
Живая геометрия Живая геометрия 106