Что такое 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
  • Количество просмотров: 98
  • Количество скачиваний: 0
- Предыдущая М.И. Кутузов
Следующая - Как научить ребёнка работать над проектом

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

matematika 10 matematika 10 139
Различные способы решения квадратных уравнений Различные способы решения квадратных уравнений 111
Арифметическая и геометрическая прогрессия Арифметическая и геометрическая прогрессия 93
Простые и составные числа Простые и составные числа 137
Задания по арифметической прогрессии Задания по арифметической прогрессии 100
Презентация к уроку в 1 классе по математике. презентация к уроку по математике (1 класс) Презентация к уроку в 1 классе по математике. презентация к уроку по математике (1 класс) 53
Увеличение и уменьшение числа на 2 Увеличение и уменьшение числа на 2 123
Многочлен и его стандартный вид Многочлен и его стандартный вид 97
Геометрические фигуры и их свойства в школьном курсе математики Геометрические фигуры и их свойства в школьном курсе математики 128
Доли. Обыкновенные дроби Доли. Обыкновенные дроби 336
Решение нестандартных задач Решение нестандартных задач 125
Удивительные кривые линии Секция прикладной математики Удивительные кривые линии Секция прикладной математики 105
открытое занятие по математике в средней группе детского сада по программе Радуга план-конспект занятия по математике (средняя группа) по теме открытое занятие по математике в средней группе детского сада по программе Радуга план-конспект занятия по математике (средняя группа) по теме 109
Математическое путешествие в сказку презентация к уроку по математике (4 класс) по теме Математическое путешествие в сказку презентация к уроку по математике (4 класс) по теме 135
Решение ЕГЭ по математике Решение ЕГЭ по математике 124
Нахождение части от числа и нахождение числа по его части Нахождение части от числа и нахождение числа по его части 120
Санның бөлігін табу . презентация 5 класс Санның бөлігін табу . презентация 5 класс 214
Умножение и деление десятичных дробей на натуральные числа Умножение и деление десятичных дробей на натуральные числа 89
Презентация к уроку математики 1 класс.Вычитание числа 1. презентация к уроку по математике (1 класс) Презентация к уроку математики 1 класс.Вычитание числа 1. презентация к уроку по математике (1 класс) 134
Древние и новые счеты Древние и новые счеты 102
Методы принятия решений Методы принятия решений 111
Презентация к занятию пр ФЭМП Путешествие с Лунтиком! презентация к уроку по математике (старшая группа) Презентация к занятию пр ФЭМП Путешествие с Лунтиком! презентация к уроку по математике (старшая группа) 119
Презентация Игра Найди предмет похожий на треугольник презентация урока для интерактивной доски по математике (средняя группа) Презентация Игра Найди предмет похожий на треугольник презентация урока для интерактивной доски по математике (средняя группа) 109
Площадь фигуры Площадь фигуры 138
Презентация Знакомим дошкольника с часами презентация к уроку по математике (подготовительная группа) Презентация Знакомим дошкольника с часами презентация к уроку по математике (подготовительная группа) 234
Презентация к уроку математики 2 класс на тему Вычитание трехзначных чисел с переходом через разряд . Презентация к уроку математики 2 класс на тему Вычитание трехзначных чисел с переходом через разряд . 96
Таблицы для быстрого решения задач на проценты Таблицы для быстрого решения задач на проценты 108
Путешествие в сказочное математическое королевство Путешествие в сказочное математическое королевство 111
Презентация к уроку математики в 3 классе по теме Закрепление. Решение задач. презентация к уроку по математике (3 класс) по теме Презентация к уроку математики в 3 классе по теме Закрепление. Решение задач. презентация к уроку по математике (3 класс) по теме 111
didakticheskie igry chernyshevoy svety didakticheskie igry chernyshevoy svety 109