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

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

Решение неполных квадратных уравнений Решение неполных квадратных уравнений 84
Использование метода ЛАЧХ для синтеза регуляторов манипулятора с гибким стержнем Использование метода ЛАЧХ для синтеза регуляторов манипулятора с гибким стержнем 100
chislo itsyfra 6 chislo itsyfra 6 74
Презентация к уроку математики по программе Перспективная начальная школа презентация к уроку по математике (1 класс) Презентация к уроку математики по программе Перспективная начальная школа презентация к уроку по математике (1 класс) 91
Логические игры презентация к уроку по математике (младшая группа) Логические игры презентация к уроку по математике (младшая группа) 106
Решение основных задач на проценты Решение основных задач на проценты 91
Старинные меры длины Старинные меры длины 92
Внеклассное мероприятие по математике для 8 класса Отличники Внеклассное мероприятие по математике для 8 класса Отличники 76
Умножение десятичных чисел на натуральное число Умножение десятичных чисел на натуральное число 107
Действия над дробями Действия над дробями 115
Презентация к уроку математики по теме Деление с остатком (закрепление), 3 класс презентация к уроку математики (3 класс) по теме Презентация к уроку математики по теме Деление с остатком (закрепление), 3 класс презентация к уроку математики (3 класс) по теме 94
Решение задач по комбинаторике Решение задач по комбинаторике 172
Урок математики во 2 классе Устные приемы вычислений в пределах 100 Урок математики во 2 классе Устные приемы вычислений в пределах 100 101
Умножение и деление положительных и отрицательных чисел Умножение и деление положительных и отрицательных чисел 81
Подготовка к ОГЭ. Задание № 5. Функции и графики: линейная функция Подготовка к ОГЭ. Задание № 5. Функции и графики: линейная функция 92
Название компонентов и результатов математических действий Название компонентов и результатов математических действий 113
prezentatsiya forma tsvet prezentatsiya forma tsvet 94
Презентация по математике на тему Занимательные задачи по теме Обыкновенные дроби Презентация по математике на тему Занимательные задачи по теме Обыкновенные дроби 232
презентация к уроку по математике Умножение числа 5 презентация к уроку по математике (2 класс) презентация к уроку по математике Умножение числа 5 презентация к уроку по математике (2 класс) 95
Задачи с параметрами Задачи с параметрами 91
Шкільне методичне об'єднання вчителів математики Шкільне методичне об'єднання вчителів математики 100
Презентация Занятия удмуртов и скотоводство Презентация Занятия удмуртов и скотоводство 89
Задачи в рисунках к урокам математики. 1 класс. презентация урока для интерактивной доски по математике (1 класс) Задачи в рисунках к урокам математики. 1 класс. презентация урока для интерактивной доски по математике (1 класс) 105
презентация к уроку№41 по теме Переместительное свойство сложения презентация к уроку по математике (1 класс) презентация к уроку№41 по теме Переместительное свойство сложения презентация к уроку по математике (1 класс) 88
Урок математики. Цель: Развитие логического мышления. Морской бой презентация к уроку по математике (2 класс) Урок математики. Цель: Развитие логического мышления. Морской бой презентация к уроку по математике (2 класс) 95
Простые числа 7 класс Простые числа 7 класс 257
Презентация по теме Угол.Виды углов. презентация урока для интерактивной доски по математике (2 класс) Презентация по теме Угол.Виды углов. презентация урока для интерактивной доски по математике (2 класс) 115
Мои первые шаги в реализации ФГОС 2-ого поколения на уроках математики в 5-ом классе Мои первые шаги в реализации ФГОС 2-ого поколения на уроках математики в 5-ом классе 86
Квадратные уравнения Квадратные уравнения 69
Интерактивный тренажерУчим таблицу умножения и деления (2-3 класс) тренажёр по математике (2 класс) Интерактивный тренажерУчим таблицу умножения и деления (2-3 класс) тренажёр по математике (2 класс) 110