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

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

Решение задач 1 класс Решение задач 1 класс 110
показательные уравнения и способы их решения показательные уравнения и способы их решения 138
Приключение колобка НОД Познание (математика) 2-я младшая группа план-конспект занятия по математике (младшая группа) Приключение колобка НОД Познание (математика) 2-я младшая группа план-конспект занятия по математике (младшая группа) 111
Умножение и деление на 2 половина числа Умножение и деление на 2 половина числа 121
Деление обыкновенных дробей 5 класс Деление обыкновенных дробей 5 класс 107
Логические задачи и загадки Логические задачи и загадки 127
Жизнь и логика Жизнь и логика 114
Масса. Единицы массы: центнер, тонна. план-конспект урока по математике (4 класс) Масса. Единицы массы: центнер, тонна. план-конспект урока по математике (4 класс) 164
Презентация к ОД В гости к бабушке Презентация к ОД В гости к бабушке 115
Как же начали считать? Как же начали считать? 102
Практикалық есептер шығару дағдыларын қалыптастыру үшін түзу мен жазықтық, жазықтықтар Практикалық есептер шығару дағдыларын қалыптастыру үшін түзу мен жазықтық, жазықтықтар 116
Урок математики на тему Прибавление суммы к сумме (1 класс ПНШ) Урок математики на тему Прибавление суммы к сумме (1 класс ПНШ) 120
Нумерация чисел в пределах 1000. Закрепление Нумерация чисел в пределах 1000. Закрепление 102
Открытый банк заданий по математике Задача №14 Открытый банк заданий по математике Задача №14 92
презентация Произведение 3 и более множителей презентация к уроку по математике (3 класс) презентация Произведение 3 и более множителей презентация к уроку по математике (3 класс) 176
Презентация к уроку в 5 классе по математике по теме Сложение и вычитание десятичных дробей Презентация к уроку в 5 классе по математике по теме Сложение и вычитание десятичных дробей 118
презентация Число и цифра 7 презентация к уроку по математике (1 класс) презентация Число и цифра 7 презентация к уроку по математике (1 класс) 138
презентация к НОД В гостях у сказки презентация к уроку по математике (средняя группа) презентация к НОД В гостях у сказки презентация к уроку по математике (средняя группа) 95
Презентация для устного счета по математике на тему Десятичные дроби (6 класс) Презентация для устного счета по математике на тему Десятичные дроби (6 класс) 101
Проект Палочки Кюизенера проект по математике (старшая группа) Проект Палочки Кюизенера проект по математике (старшая группа) 159
Астрономия на координатной плоскости Астрономия на координатной плоскости 112
Задачи на движение Задачи на движение 128
Russian mathematician. Sofia Kovalevskaya Russian mathematician. Sofia Kovalevskaya 83
Проект по математике Математика вокруг нас. Узоры и орнаменты на посуде Проект по математике Математика вокруг нас. Узоры и орнаменты на посуде 143
Обыкновенные дроби Обыкновенные дроби 158
Презентация Формирование математического мышления у дошкольников посредством логико-математических игр презентация к уроку по математике (подготовительная группа) Презентация Формирование математического мышления у дошкольников посредством логико-математических игр презентация к уроку по математике (подготовительная группа) 120
Презентация у уроку математики Решение задач на нахождение четвёртого пропорционального Презентация у уроку математики Решение задач на нахождение четвёртого пропорционального 121
Углы, связанные с окружностью Углы, связанные с окружностью 177
Математические ребусы презентация к уроку по математике (1, 2, 3, 4 класс) Математические ребусы презентация к уроку по математике (1, 2, 3, 4 класс) 115
Презентация по математике на тему Изображение натуральных чисел точками на координатной прямой (5 класс, по учебнику Дорофеева Г.В., Шарыгина И.Ф. и др.) Презентация по математике на тему Изображение натуральных чисел точками на координатной прямой (5 класс, по учебнику Дорофеева Г.В., Шарыгина И.Ф. и др.) 304