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

Смотреть слайды в полном размере
Презентация «Графы. Эйлеровы графы. Гамильтоновы графы. Изоморфизмы графов»

Вы можете ознакомиться с презентацией онлайн, просмотреть текст и слайды к ней, а также, в случае, если она вам подходит - скачать файл для редактирования или печати. Документ содержит 72 слайда и доступен в формате ppt. Размер файла: 4.10 MB

Просмотреть и скачать

Pic.1
Графы Ирина Борисовна Просвирнина Эйлеровы графы Гамильтоновы графы Изоморфизмы графов
Графы Ирина Борисовна Просвирнина Эйлеровы графы Гамильтоновы графы Изоморфизмы графов
Pic.2
Эйлеровы графы Мы уже упоминали работу Эйлера, датированную 1736 годом, которая положила начало теор
Эйлеровы графы Мы уже упоминали работу Эйлера, датированную 1736 годом, которая положила начало теории графов. В этой работе Эйлер изложил теорию, позволившую решить задачу о мостах Кенигсберга. …
Pic.3
Эйлеровы графы Задача возникла в прусском городе Кенигсберг на реке Прегел. На реке Прегел было два
Эйлеровы графы Задача возникла в прусском городе Кенигсберг на реке Прегел. На реке Прегел было два острова, один из которых – остров Кнайпхоф (это больший остров). Этот район и семь его мостов …
Pic.4
Эйлеровы графы Жители Кенигсберга интересовались, могут ли они, начав путь с одного участка суши, об
Эйлеровы графы Жители Кенигсберга интересовались, могут ли они, начав путь с одного участка суши, обойти все мосты, посетив каждый лишь однажды, и вернуться в точку начала пути, не переплывая реки.
Pic.5
Эйлеровы графы Жители Кенигсберга не могли найти такого пути. Задача заключалась в следующем: найти
Эйлеровы графы Жители Кенигсберга не могли найти такого пути. Задача заключалась в следующем: найти путь с требуемыми свойствами или доказать, что такого пути не существует.
Pic.6
Эйлеровы графы Эйлер представил географию указанного района Кенигсберга в виде графа (рисунок ). Оба
Эйлеровы графы Эйлер представил географию указанного района Кенигсберга в виде графа (рисунок ). Оба берега реки и острова изображены вершинами графа, а ребра графа соответствуют мостам, соединяющим …
Pic.7
Эйлеровы графы Переформулируем задачу о кенигсбергских мостах на языке теории графов. Следует выясни
Эйлеровы графы Переформулируем задачу о кенигсбергских мостах на языке теории графов. Следует выяснить, существует ли замкнутый путь, который включает все ребра графа, изображенного на рисунке .
Pic.8
Эйлеровы графы Определение 1 Эйлеров цикл в графе – это замкнутый путь, который включает все ребра г
Эйлеровы графы Определение 1 Эйлеров цикл в графе – это замкнутый путь, который включает все ребра графа . Граф называется эйлеровым, если он имеет хотя бы один эйлеров цикл. Напомним, что в пути все …
Pic.9
Эйлеровы графы Теорема 1 Связный граф является эйлеровым тогда и только тогда, когда каждая его верш
Эйлеровы графы Теорема 1 Связный граф является эйлеровым тогда и только тогда, когда каждая его вершина имеет четную степень.
Pic.10
? Если связный граф является эйлеровым, то каждая его вершина имеет четную степень. Доказательство П
? Если связный граф является эйлеровым, то каждая его вершина имеет четную степень. Доказательство Предположим, что – связный и имеет эйлеров цикл. Так как – связный, то последовательность вершин …
Pic.11
? Если граф является связным и каждая его вершина имеет четную степень, то – эйлеров. Доказательство
? Если граф является связным и каждая его вершина имеет четную степень, то – эйлеров. Доказательство Докажем утверждение индукцией по , числу ребер графа . Индуктивный переход (набросок …
Pic.12
? Если граф является связным и каждая его вершина имеет четную степень, то – эйлеров. Доказательство
? Если граф является связным и каждая его вершина имеет четную степень, то – эйлеров. Доказательство Этот новый граф может оказаться несвязным. Рассмотрим каждую компоненту графа по очереди и …
Pic.13
Эйлеровы графы Жители Кенигсберга не могли найти свой эйлеров цикл по теперь весьма понятной для нас
Эйлеровы графы Жители Кенигсберга не могли найти свой эйлеров цикл по теперь весьма понятной для нас причине – его не существует. Граф, представляющий задачу о кенигсбергских мостах, связен, но не …
Pic.14
Эйлеровы графы Пример 1 Полный граф является -регулярным – каждая вершина имеет степень . Так как он
Эйлеровы графы Пример 1 Полный граф является -регулярным – каждая вершина имеет степень . Так как он связен, то является эйлеровым тогда и только тогда, когда – нечетное число (так что – четное …
Pic.15
Эйлеровы графы Пример 1 – эйлеров граф тогда и только тогда, когда – нечетное число (так что четно).
Эйлеровы графы Пример 1 – эйлеров граф тогда и только тогда, когда – нечетное число (так что четно). Граф имеет очевидный эйлеров цикл.
Pic.16
Эйлеровы графы Пример 1 – эйлеров граф тогда и только тогда, когда – нечетное число (так что четно).
Эйлеровы графы Пример 1 – эйлеров граф тогда и только тогда, когда – нечетное число (так что четно). Найдите эйлеров цикл в . В действительности, имеет эйлеровых цикла.
Pic.17
Эйлеровы графы Полный двудольный граф изображен на рисунке. Множество его вершин разбито на два подм
Эйлеровы графы Полный двудольный граф изображен на рисунке. Множество его вершин разбито на два подмножества и . связен и каждая вершина имеет степень 4. Значит, по теореме 1 эйлеров.
Pic.18
Эйлеровы графы Один эйлеров цикл, начинающийся в вершине , имеет такую последовательность вершин:
Эйлеровы графы Один эйлеров цикл, начинающийся в вершине , имеет такую последовательность вершин:
Pic.19
Гамильтоновы графы Эйлеров цикл проходит через каждое ребро графа (один раз) и возвращается в началь
Гамильтоновы графы Эйлеров цикл проходит через каждое ребро графа (один раз) и возвращается в начальную точку пути. Сформулируем аналогичную задачу: можем ли мы побывать в каждой вершине графа один …
Pic.20
Гамильтоновы графы Определение 2 Гамильтонов цикл в графе – это цикл, который проходит через каждую
Гамильтоновы графы Определение 2 Гамильтонов цикл в графе – это цикл, который проходит через каждую вершину графа один раз. Граф называется гамильтоновым, если он имеет гамильтонов цикл. Этой …
Pic.21
Гамильтоновы графы Сэр Уильям Роуэн Гамильтон (1805 – 1865) был выдающимся ирландским математиком. З
Гамильтоновы графы Сэр Уильям Роуэн Гамильтон (1805 – 1865) был выдающимся ирландским математиком. Закончив университет, в возрасте 22 лет он был избран профессором астрономии и Королевским …
Pic.22
Гамильтоновы графы В 1843 он открыл кватернионы – одну из разновидностей обобщения комплексных чисел
Гамильтоновы графы В 1843 он открыл кватернионы – одну из разновидностей обобщения комплексных чисел – и большую часть своей жизни он посвятил их изучению. Его имя также ассоциируется с гамильтоновым …
Pic.23
Гамильтоновы графы Итак, в 1857 году Уильям Роуэн Гамильтон придумал игру. Существует несколько верс
Гамильтоновы графы Итак, в 1857 году Уильям Роуэн Гамильтон придумал игру. Существует несколько версий того, как это произошло. По одной из версий он описал эту игру в письме к другу. Согласно …
Pic.24
Гамильтоновы графы В любом случае игра, по-видимому, включала додекаэдр, т. е. правильный многогранн
Гамильтоновы графы В любом случае игра, по-видимому, включала додекаэдр, т. е. правильный многогранник, граней которого представляли собой конгруэнтные правильные пятиугольники. В каждом из углов, …
Pic.25
Гамильтоновы графы Используя веревку, требовалось найти путь через города, посетив каждый город один
Гамильтоновы графы Используя веревку, требовалось найти путь через города, посетив каждый город один раз, и вернуться в исходный город.
Pic.26
Гамильтоновы графы Рассмотрим эквивалентный вопрос. Существует ли цикл в графе, изображенном на рису
Гамильтоновы графы Рассмотрим эквивалентный вопрос. Существует ли цикл в графе, изображенном на рисунке, который проходит через каждую вершину графа ровно один раз?
Pic.27
Гамильтоновы графы Ответ на последний вопрос решает головоломку Гамильтона, так как построенный граф
Гамильтоновы графы Ответ на последний вопрос решает головоломку Гамильтона, так как построенный граф изоморфен графу, составленному из вершин и ребер додекаэдра.
Pic.28
Гамильтоновы графы Решение головоломки Гамильтона показано на рисунке.
Гамильтоновы графы Решение головоломки Гамильтона показано на рисунке.
Pic.29
Гамильтоновы графы Пример 1 На рисунке изображен гамильтонов цикл в полном двудольном графе
Гамильтоновы графы Пример 1 На рисунке изображен гамильтонов цикл в полном двудольном графе
Pic.30
Гамильтоновы графы Для эйлеровых графов имеется достаточно простой критерий. Однако, не так обстоят
Гамильтоновы графы Для эйлеровых графов имеется достаточно простой критерий. Однако, не так обстоят дела с гамильтоновыми графами. Действительно, изучая последние графы более столетия, математики до …
Pic.31
Гамильтоновы графы Эта задача остается одной из основных нерешенных проблем теории графов. Очевидным
Гамильтоновы графы Эта задача остается одной из основных нерешенных проблем теории графов. Очевидным необходимым условием гамильтоновости графа является его связность. Известны также и различные …
Pic.32
Гамильтоновы графы Приведем один из простейших результатов такого сорта. Теорема 1 Если – связный пр
Гамильтоновы графы Приведем один из простейших результатов такого сорта. Теорема 1 Если – связный простой граф с вершинами и если степень каждой вершины удовлетворяет неравенству то – гамильтонов …
Pic.33
Гамильтоновы графы Теорема 1 Если – связный простой граф с вершинами и если степень каждой вершины у
Гамильтоновы графы Теорема 1 Если – связный простой граф с вершинами и если степень каждой вершины удовлетворяет неравенству то – гамильтонов граф. Условие, накладываемое на степени вершин: , – не …
Pic.34
Гамильтоновы графы Убедимся в этом, обратившись к графу додекаэдра. Этот граф имеет вершин, степень
Гамильтоновы графы Убедимся в этом, обратившись к графу додекаэдра. Этот граф имеет вершин, степень каждой вершины равна , однако, граф – гамильтонов.
Pic.35
Гамильтоновы графы В действительности, каждый из графов, связанных с пятью правильными многогранника
Гамильтоновы графы В действительности, каждый из графов, связанных с пятью правильными многогранниками, имеет гамильтонов цикл.
Pic.36
Гамильтоновы графы Задача 1 Покажите, что каждый из графов, изображенных на рисунке и связанных с пр
Гамильтоновы графы Задача 1 Покажите, что каждый из графов, изображенных на рисунке и связанных с правильными многогранниками (тетраэдр – слева и куб – справа) является гамильтоновым.
Pic.37
Гамильтоновы графы Задача 1 Покажите, что каждый из графов, изображенных на рисунке и связанных с пр
Гамильтоновы графы Задача 1 Покажите, что каждый из графов, изображенных на рисунке и связанных с правильными многогранниками (октаэдр – слева и икосаэдр – справа) является гамильтоновым.
Pic.38
Изоморфизм графов Рассмотрим два графа и определенные следующим образом: имеет множество вершин и ма
Изоморфизм графов Рассмотрим два графа и определенные следующим образом: имеет множество вершин и матрицу смежности , и имеет множество вершин и матрицу смежности , где
Pic.39
Изоморфизм графов имеет множество вершин и матрицу смежности
Изоморфизм графов имеет множество вершин и матрицу смежности
Pic.40
Изоморфизм графов имеет множество вершин и матрицу смежности
Изоморфизм графов имеет множество вершин и матрицу смежности
Pic.41
После недолгих раздумий становится очевидным, что графы и по существу одинаковы.
После недолгих раздумий становится очевидным, что графы и по существу одинаковы.
Pic.42
Если мы переименуем вершины графа как , в указанном порядке, и переименуем ребра как for то эти две
Если мы переименуем вершины графа как , в указанном порядке, и переименуем ребра как for то эти две диаграммы будут различными графическими представлениями одного и того же графа.
Pic.43
Изоморфизм графов Определение 1 Пусть и – два графа. Изоморфизм из в состоит из пары биекций и таких
Изоморфизм графов Определение 1 Пусть и – два графа. Изоморфизм из в состоит из пары биекций и таких, что для каждого ребра графа , если , то . Два графа называют изоморфными и пишут, если существует …
Pic.44
Изоморфизм графов Условие если , то гарантирует, что биекции между множествами вершин и множествами
Изоморфизм графов Условие если , то гарантирует, что биекции между множествами вершин и множествами ребер двух графов корректно согласованы друг с другом. Другими словами, если ребро графа …
Pic.45
Изоморфизм графов Если ребро графа соответствует ребру графа то множества вершин, инцидентные этим р
Изоморфизм графов Если ребро графа соответствует ребру графа то множества вершин, инцидентные этим ребрам, также соответствуют друг другу (относительно биекции ). Это показано на рисунке.
Pic.46
Изоморфизм графов Пусть обозначает множество ребер, соединяющих вершины и в графе , тогда реберное о
Изоморфизм графов Пусть обозначает множество ребер, соединяющих вершины и в графе , тогда реберное отображение определяет биекцию Поэтому для всех пар вершин графа , , т. e. число ребер графа , …
Pic.47
Изоморфизм графов Пусть – простой граф. Чтобы определить изоморфизм из в , нам нужно только корректн
Изоморфизм графов Пусть – простой граф. Чтобы определить изоморфизм из в , нам нужно только корректно специфицировать биекцию . Действительно, любую пару вершин соединяет не более одного ребра. …
Pic.48
Изоморфизм графов Изоморфизм графов является отношением эквивалентности.
Изоморфизм графов Изоморфизм графов является отношением эквивалентности.
Pic.49
Изоморфизм графов Так как изоморфные графы имеют, по существу, одно и тоже строение, то любое теорет
Изоморфизм графов Так как изоморфные графы имеют, по существу, одно и тоже строение, то любое теоретико-графовое свойство, которым обладает один граф, должно быть присуще и второму графу. Мы …
Pic.50
Изоморфизм графов Теорема 1 Пусть – изоморфизм из на тогда: и имеют одинаковое число вершин; и имеют
Изоморфизм графов Теорема 1 Пусть – изоморфизм из на тогда: и имеют одинаковое число вершин; и имеют одинаковое число ребер; и имеют одинаковое число компонент; Соответствующие вершины имеют …
Pic.51
? Пусть – изоморфизм из в тогда и имеют одинаковое число вершин. Доказательство Изоморфизм из в сост
? Пусть – изоморфизм из в тогда и имеют одинаковое число вершин. Доказательство Изоморфизм из в состоит из пары биекций и таких, что для каждого ребра графа , если , то . Если – биекция, где и – …
Pic.52
? Пусть – изоморфизм из в тогда и имеют одинаковое число ребер. Доказательство Изоморфизм из в состо
? Пусть – изоморфизм из в тогда и имеют одинаковое число ребер. Доказательство Изоморфизм из в состоит из пары биекций и таких, что для каждого ребра графа , если , то . Если – биекция, где и – …
Pic.53
? Пусть – изоморфизм из в тогда и имеют одинаковое число компонент. Доказательство Если , , , – путь
? Пусть – изоморфизм из в тогда и имеют одинаковое число компонент. Доказательство Если , , , – путь, соединяющий и в , то , , , – путь, соединяющий и в . Обратно, если , , , – путь, соединяющий и в …
Pic.54
? Пусть – изоморфизм из в тогда соответствующие вершины имеют одинаковые степени: для любой , Доказа
? Пусть – изоморфизм из в тогда соответствующие вершины имеют одинаковые степени: для любой , Доказательство и Осталось заметить, что – биекция и отображение определяет биекцию
Pic.55
? Пусть – изоморфизм из в тогда и имеют одинаковые степенные последовательности. Доказательство Это
? Пусть – изоморфизм из в тогда и имеют одинаковые степенные последовательности. Доказательство Это утверждение следует из d).
Pic.56
? Пусть – изоморфизм из в . Если является простым, то – также простой. Доказательство – простой граф
? Пусть – изоморфизм из в . Если является простым, то – также простой. Доказательство – простой граф тогда и только тогда, когда и для всех . Результат следует из существования биекций
Pic.57
? Пусть – изоморфизм из в . Если является эйлеровым, то – также эйлеров. Доказательство Связный граф
? Пусть – изоморфизм из в . Если является эйлеровым, то – также эйлеров. Доказательство Связный граф является эйлеровым тогда и только тогда, когда степень каждой его вершины четна. Но и имеют …
Pic.58
? Пусть – изоморфизм из в . Если является гамильтоновым, то – также гамильтонов. Доказательство Если
? Пусть – изоморфизм из в . Если является гамильтоновым, то – также гамильтонов. Доказательство Если , , , – гамильтонов цикл в то , , , – гамильтонов цикл в .
Pic.59
Изоморфизм графов Пример Определим, какие из приведенных ниже графов являются изоморфными.
Изоморфизм графов Пример Определим, какие из приведенных ниже графов являются изоморфными.
Pic.60
Пример Определим, какие из приведенных ниже графов являются изоморфными. Каждый граф является просты
Пример Определим, какие из приведенных ниже графов являются изоморфными. Каждый граф является простым, связным, имеет семь вершин и десять ребер.
Pic.61
Пример Определим, какие из приведенных ниже графов являются изоморфными. Каждый граф имеет степенную
Пример Определим, какие из приведенных ниже графов являются изоморфными. Каждый граф имеет степенную последовательность , каждый граф не эйлеров.
Pic.62
Пример Определим, какие из приведенных графов являются изоморфными. Рассматривая вершины степени 2,
Пример Определим, какие из приведенных графов являются изоморфными. Рассматривая вершины степени 2, мы видим, что графы и не являются гамильтоновыми.
Pic.63
Пример Определим, какие из приведенных графов являются изоморфными. Графы и являются гамильтоновыми
Пример Определим, какие из приведенных графов являются изоморфными. Графы и являются гамильтоновыми (с гамильтоновыми циклами и соответственно).
Pic.64
Пример Определим, какие из приведенных графов являются изоморфными. Итак, графы и не являются гамиль
Пример Определим, какие из приведенных графов являются изоморфными. Итак, графы и не являются гамильтоновыми. Графы и – гамильтоновы. Отсюда следует, что ни граф ни не изоморфны графу или графу . …
Pic.65
Пример Определим, какие из приведенных графов являются изоморфными. Графы и не изоморфны: в графе ве
Пример Определим, какие из приведенных графов являются изоморфными. Графы и не изоморфны: в графе вершина степени 4 является смежной с двумя вершинами степени 3, а в графе вершина степени 4 является …
Pic.66
Пример Определим, какие из приведенных графов являются изоморфными. Графы и не изоморфны: в графе ве
Пример Определим, какие из приведенных графов являются изоморфными. Графы и не изоморфны: в графе вершина степени 4 является смежной с двумя вершинами степени 3, а в графе вершина степени 4 является …
Pic.67
Пример Определим, какие из приведенных графов являются изоморфными. Графы и изоморфны. Обозначим мно
Пример Определим, какие из приведенных графов являются изоморфными. Графы и изоморфны. Обозначим множества вершин графов и через и , соответственно, и определим изоморфизм графов, задав биекцию
Pic.68
Пример Определим, какие из приведенных графов являются изоморфными. Графы и неизоморфны, так как гра
Пример Определим, какие из приведенных графов являются изоморфными. Графы и неизоморфны, так как граф изоморфен графу а – нет. Аналогично графы и неизоморфны.
Pic.69
Пример Определим, какие из приведенных графов являются изоморфными. Графы и неизоморфны, так как гра
Пример Определим, какие из приведенных графов являются изоморфными. Графы и неизоморфны, так как граф изоморфен графу а – нет.
Pic.70
Пример Определим, какие из приведенных графов являются изоморфными. Графы и неизоморфны. В имеется в
Пример Определим, какие из приведенных графов являются изоморфными. Графы и неизоморфны. В имеется вершина степени 3 (вершина ), смежная с двумя другими вершинами степени 3, а в каждая вершина …
Pic.71
Пример Определим, какие из приведенных ниже графов являются изоморфными. Подведем итоги: графы (a) и
Пример Определим, какие из приведенных ниже графов являются изоморфными. Подведем итоги: графы (a) и (c) изоморфны, а осталь- ные пары графов не являются изоморфными.
Pic.72
Изоморфизм графов Принцип изоморфизма Чтобы доказать, что два графа изоморфны, следует построить изо
Изоморфизм графов Принцип изоморфизма Чтобы доказать, что два графа изоморфны, следует построить изоморфизм из одного графа на другой; чтобы доказать, что два графа неизоморфны, следует найти …


Скачать презентацию

Если вам понравился сайт и размещенные на нем материалы, пожалуйста, не забывайте поделиться этой страничкой в социальных сетях и с друзьями! Спасибо!