Графы. Эйлеровы графы. Гамильтоновы графы. Изоморфизмы графов

Содержание

Слайд 2

Эйлеровы графы Мы уже упоминали работу Эйлера, датированную 1736 годом, которая

Эйлеровы графы

Мы уже упоминали работу Эйлера, датированную 1736 годом, которая положила

начало теории графов.
В этой работе Эйлер изложил теорию, позволившую решить задачу о мостах Кенигсберга.
Перейдем к изложению задачи о кенигсбергских мостах. Она состоит в следующем.
Слайд 3

Эйлеровы графы Задача возникла в прусском городе Кенигсберг на реке Прегел.

Эйлеровы графы

Задача возникла в прусском городе Кенигсберг на реке Прегел. На

реке Прегел было два острова, один из которых – остров Кнайпхоф (это больший остров). Этот район и семь его мостов показаны на рисунке.
Слайд 4

Эйлеровы графы Жители Кенигсберга интересовались, могут ли они, начав путь с

Эйлеровы графы

Жители Кенигсберга интересовались, могут ли они, начав путь с одного

участка суши, обойти все мосты, посетив каждый лишь однажды, и вернуться в точку начала пути, не переплывая реки.
Слайд 5

Эйлеровы графы Жители Кенигсберга не могли найти такого пути. Задача заключалась

Эйлеровы графы

Жители Кенигсберга не могли найти такого пути.
Задача заключалась в следующем:

найти путь с требуемыми свойствами или доказать, что такого пути не существует.
Слайд 6

Эйлеровы графы

Эйлеровы графы

 

Слайд 7

Эйлеровы графы

Эйлеровы графы

 

Слайд 8

Эйлеровы графы

Эйлеровы графы

 

Слайд 9

Эйлеровы графы

Эйлеровы графы

 

Слайд 10

 

 

Слайд 11

 

 

Слайд 12

 

 

Слайд 13

Эйлеровы графы Жители Кенигсберга не могли найти свой эйлеров цикл по

Эйлеровы графы

Жители Кенигсберга не могли найти свой эйлеров цикл по теперь

весьма понятной для нас причине – его не существует.
Граф, представляющий задачу о кенигсбергских мостах, связен, но не удовлетворяет условию теоремы 1. Каждая его вершина имеет нечетную степень.
Слайд 14

Эйлеровы графы

Эйлеровы графы

 

Слайд 15

Эйлеровы графы

Эйлеровы графы

 

Слайд 16

Эйлеровы графы

Эйлеровы графы

 

Слайд 17

Эйлеровы графы

Эйлеровы графы

 

Слайд 18

Эйлеровы графы

Эйлеровы графы

 

Слайд 19

Гамильтоновы графы Эйлеров цикл проходит через каждое ребро графа (один раз)

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

Эйлеров цикл проходит через каждое ребро графа (один раз) и

возвращается в начальную точку пути.
Сформулируем аналогичную задачу: можем ли мы побывать в каждой вершине графа один раз, проходя по каждому ребру не более одного раза, и вернуться в начальную точку пути.
Этой задачей занимался Гамильтон (хотя он был не первым ее исследователем) и сегодня его имя ассоциируется с путями указанного типа.
Слайд 20

Гамильтоновы графы Определение 2 Гамильтонов цикл в графе – это цикл,

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

Определение 2
Гамильтонов цикл в графе – это цикл, который проходит

через каждую вершину графа один раз.
Граф называется гамильтоновым, если он имеет гамильтонов цикл.
Этой терминологией мы обязаны игре, изобретенной в 1857 ирландским математиком Сэром Уильямом Роуэном Гамильтоном.
Слайд 21

Гамильтоновы графы Сэр Уильям Роуэн Гамильтон (1805 – 1865) был выдающимся

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

Сэр Уильям Роуэн Гамильтон (1805 – 1865) был выдающимся ирландским

математиком. Закончив университет, в возрасте 22 лет он был избран профессором астрономии и Королевским Астрономом Ирландии.
Однако, его вклад в астрономию невелик; его наиболее значительные результаты относятся к математике и физике.
Слайд 22

Гамильтоновы графы В 1843 он открыл кватернионы – одну из разновидностей

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

В 1843 он открыл кватернионы – одну из разновидностей обобщения

комплексных чисел – и большую часть своей жизни он посвятил их изучению. Его имя также ассоциируется с гамильтоновым оператором энергии, используемым в физике (в частности, в волновой механике).
Слайд 23

Гамильтоновы графы Итак, в 1857 году Уильям Роуэн Гамильтон придумал игру.

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

Итак, в 1857 году Уильям Роуэн Гамильтон придумал игру.
Существует

несколько версий того, как это произошло. По одной из версий он описал эту игру в письме к другу. Согласно другой, он действительно изобрел игру и продал ее производителю игрушек.
Слайд 24

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

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

 

Слайд 25

Гамильтоновы графы Используя веревку, требовалось найти путь через города, посетив каждый

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

Используя веревку, требовалось найти путь через города, посетив каждый город

один раз, и вернуться в исходный город.
Слайд 26

Гамильтоновы графы Рассмотрим эквивалентный вопрос. Существует ли цикл в графе, изображенном

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

Рассмотрим эквивалентный вопрос.
Существует ли цикл в графе, изображенном на рисунке,

который проходит через каждую вершину графа ровно один раз?
Слайд 27

Гамильтоновы графы Ответ на последний вопрос решает головоломку Гамильтона, так как

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

Ответ на последний вопрос решает головоломку Гамильтона, так как построенный

граф изоморфен графу, составленному из вершин и ребер додекаэдра.
Слайд 28

Гамильтоновы графы Решение головоломки Гамильтона показано на рисунке.

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

Решение головоломки Гамильтона показано на рисунке.

Слайд 29

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

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

 

Слайд 30

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

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

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

обстоят дела с гамильтоновыми графами.
Действительно, изучая последние графы более столетия, математики до сих пор не нашли критерия гамильтоновости графов.
(Под ‘критерием’ гамильтоновости графа мы понимаем необходимое и достаточное условия того, что граф является гамильтоновым.)
Слайд 31

Гамильтоновы графы Эта задача остается одной из основных нерешенных проблем теории

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

Эта задача остается одной из основных нерешенных проблем теории графов.
Очевидным

необходимым условием гамильтоновости графа является его связность.
Известны также и различные достаточные условия гамильтоновости графа.
Как правило, в достаточных условиях гамильтоновости графа требуется, чтобы граф имел ‘достаточно’ ребер в определенном смысле этого слова.
Слайд 32

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

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

 

Слайд 33

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

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

 

Слайд 34

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

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

 

 

Слайд 35

Гамильтоновы графы В действительности, каждый из графов, связанных с пятью правильными многогранниками, имеет гамильтонов цикл.

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

В действительности, каждый из графов, связанных с пятью правильными многогранниками,

имеет гамильтонов цикл.
Слайд 36

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

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

 

Слайд 37

Гамильтоновы графы Задача 1 Покажите, что каждый из графов, изображенных на

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

Задача 1
Покажите, что каждый из графов, изображенных на рисунке и

связанных с правильными многогранниками (октаэдр – слева и икосаэдр – справа) является гамильтоновым.
Слайд 38

Изоморфизм графов

Изоморфизм графов

 

Слайд 39

Изоморфизм графов

Изоморфизм графов

 

Слайд 40

Изоморфизм графов

Изоморфизм графов

 

Слайд 41

 

 

 

Слайд 42

 

 

 

Слайд 43

Изоморфизм графов

Изоморфизм графов

 

Слайд 44

Изоморфизм графов

Изоморфизм графов

 

Слайд 45

Изоморфизм графов

Изоморфизм графов

 

Слайд 46

Изоморфизм графов

Изоморфизм графов

 

Слайд 47

Изоморфизм графов

Изоморфизм графов

 

Слайд 48

Изоморфизм графов Изоморфизм графов является отношением эквивалентности.

Изоморфизм графов

Изоморфизм графов является отношением эквивалентности.

Слайд 49

Изоморфизм графов Так как изоморфные графы имеют, по существу, одно и

Изоморфизм графов

Так как изоморфные графы имеют, по существу, одно и тоже

строение, то любое теоретико-графовое свойство, которым обладает один граф, должно быть присуще и второму графу.
Мы перечислим некоторые такие свойства в следующей теореме.
Слайд 50

Изоморфизм графов

Изоморфизм графов

 

Слайд 51

 

 

Слайд 52

 

 

Слайд 53

 

 

Слайд 54

 

 

Слайд 55

 

 

Слайд 56

 

 

Слайд 57

 

 

Слайд 58

 

 

Слайд 59

Изоморфизм графов Пример Определим, какие из приведенных ниже графов являются изоморфными.

Изоморфизм графов

Пример Определим, какие из приведенных ниже графов являются изоморфными.

Слайд 60

Пример Определим, какие из приведенных ниже графов являются изоморфными. Каждый граф

Пример Определим, какие из приведенных ниже графов являются изоморфными.

Каждый граф является

простым, связным, имеет семь вершин и десять ребер.
Слайд 61

Пример Определим, какие из приведенных ниже графов являются изоморфными.

Пример Определим, какие из приведенных ниже графов являются изоморфными.

 

Слайд 62

Пример Определим, какие из приведенных графов являются изоморфными.

Пример Определим, какие из приведенных графов являются изоморфными.

 

Слайд 63

Пример Определим, какие из приведенных графов являются изоморфными.

Пример Определим, какие из приведенных графов являются изоморфными.

 

Слайд 64

Пример Определим, какие из приведенных графов являются изоморфными.

Пример Определим, какие из приведенных графов являются изоморфными.

 

Слайд 65

Пример Определим, какие из приведенных графов являются изоморфными.

Пример Определим, какие из приведенных графов являются изоморфными.

 

Слайд 66

Пример Определим, какие из приведенных графов являются изоморфными.

Пример Определим, какие из приведенных графов являются изоморфными.

 

Слайд 67

Пример Определим, какие из приведенных графов являются изоморфными.

Пример Определим, какие из приведенных графов являются изоморфными.

 

Слайд 68

Пример Определим, какие из приведенных графов являются изоморфными.

Пример Определим, какие из приведенных графов являются изоморфными.

 

Слайд 69

Пример Определим, какие из приведенных графов являются изоморфными.

Пример Определим, какие из приведенных графов являются изоморфными.

 

Слайд 70

Пример Определим, какие из приведенных графов являются изоморфными.

Пример Определим, какие из приведенных графов являются изоморфными.

 

Слайд 71

Пример Определим, какие из приведенных ниже графов являются изоморфными.

Пример Определим, какие из приведенных ниже графов являются изоморфными.

 

- Предыдущая
Финансирование деятельности по управлению рисками
Следующая -
Азот и его соединения

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

2 класс Математический диктант № 8 Выполнила Кирилова С.Г. Учитель начальных классов Школы «Ученики Пифагора» г. Лимассол, р.Кипр
Степень числа. 7 класс
Презентация на тему Задачи на движение
Модуль действительного числа
Признак перпендикулярности прямой и плоскости
Скалярное произведение векторов. Математический диктант
Презентация на тему Округление десятичных дробей
Елементи теорії виміру. Шкали виміру. Лекція 5. Тема 3
Решение задач по стереометрии
Правила выполнения действий с натуральными числами
График линейного уравнения с двумя переменными
ГИА - 2012. Открытый банк заданий по математике. (Задача 4)
Линейное уравнение с одной переменной
Делимость натуральных чисел
Ромб. Свойства параллелограмма
Планиметрия
Запись всех точек, соответствующих данным точкам единичной окружности
Сумма n-первых членов арифметической прогрессии
Иррациональные уравнения и неравенства
Формулы двойного аргумента
Женщины в математике
Подобие. Признаки подобия треугольников
Обыкновенные дроби
Презентация на тему Сумма углов треугольника
Муниципальное бюджетное образовательное учреждение «Лопхаринская средняя общеобразовательная школа» Урок математики в 5 кла
Сумма углов треугольника
Кубик Рубика - гимнастика ума. Исследовательская работа
Задачи оптимизации производства товаров и услуг
Вы можете прислать нам Вашу презентацию и мы опубликуем ее на сайте.
Обратная связь
Для правообладателей
Email: Нажмите что бы посмотреть