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

Нажмите для полного просмотра!

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Графы. Эйлеровы графы. Гамильтоновы графы. Изоморфизмы графов, слайд №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

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

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Графы. Эйлеровы графы. Гамильтоновы графы. Изоморфизмы графов. Доклад-сообщение содержит 72 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

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

Слайд 2

Описание слайда:

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

Слайд 3

Описание слайда:

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

Слайд 4

Описание слайда:

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

Слайд 5

Описание слайда:

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

Слайд 6

Описание слайда:

Эйлеровы графы Эйлер представил географию указанного района Кенигсберга в виде графа (рисунок ). Оба берега реки и острова изображены вершинами графа, а ребра графа соответствуют мостам, соединяющим участки суши.

Слайд 7

Описание слайда:

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

Слайд 8

Описание слайда:

Эйлеровы графы Определение 1 Эйлеров цикл в графе – это замкнутый путь, который включает все ребра графа . Граф называется эйлеровым, если он имеет хотя бы один эйлеров цикл. Напомним, что в пути все ребра различны. Таким образом, эйлеров цикл включает каждое ребро графа в точности один раз, хотя, конечно, вершины в эйлеровом цикле могут повторяться.

Слайд 9

Описание слайда:

Эйлеровы графы Теорема 1 Связный граф является эйлеровым тогда и только тогда, когда каждая его вершина имеет четную степень.

Слайд 10

Описание слайда:

? Если связный граф является эйлеровым, то каждая его вершина имеет четную степень. Доказательство Предположим, что – связный и имеет эйлеров цикл. Так как – связный, то последовательность вершин эйлерова цикла содержит все вершины графа . Всякий раз, когда цикл проходит через вершину графа, он вносит в степень этой вершины ( вносит ребро, ‘входящее в’ вершину и вносит ребро, ‘выходящее из’ вершины). Так как эйлеров цикл проходит каждое ребро графа в точности один раз, то каждая вершина должна иметь четную степень.

Слайд 11

Описание слайда:

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

Слайд 12

Описание слайда:

? Если граф является связным и каждая его вершина имеет четную степень, то – эйлеров. Доказательство Этот новый граф может оказаться несвязным. Рассмотрим каждую компоненту графа по очереди и воспользуемся индуктивным предположением для построения эйлеровых циклов в каждой компоненте. Наконец, соединим и эйлеровы циклы каждой компоненты графа в эйлеров цикл для графа

Слайд 13

Описание слайда:

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

Слайд 14

Описание слайда:

Эйлеровы графы Пример 1 Полный граф является -регулярным – каждая вершина имеет степень . Так как он связен, то является эйлеровым тогда и только тогда, когда – нечетное число (так что – четное число).

Слайд 15

Описание слайда:

Эйлеровы графы Пример 1 – эйлеров граф тогда и только тогда, когда – нечетное число (так что четно). Граф имеет очевидный эйлеров цикл.

Слайд 16

Описание слайда:

Эйлеровы графы Пример 1 – эйлеров граф тогда и только тогда, когда – нечетное число (так что четно). Найдите эйлеров цикл в . В действительности, имеет эйлеровых цикла.

Слайд 17

Описание слайда:

Эйлеровы графы Полный двудольный граф изображен на рисунке. Множество его вершин разбито на два подмножества и . связен и каждая вершина имеет степень 4. Значит, по теореме 1 эйлеров.

Слайд 18

Описание слайда:

Эйлеровы графы Один эйлеров цикл, начинающийся в вершине , имеет такую последовательность вершин:

Слайд 19

Описание слайда:

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

Слайд 20

Описание слайда:

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

Слайд 21

Описание слайда:

Гамильтоновы графы Сэр Уильям Роуэн Гамильтон (1805 – 1865) был выдающимся ирландским математиком. Закончив университет, в возрасте 22 лет он был избран профессором астрономии и Королевским Астрономом Ирландии. Однако, его вклад в астрономию невелик; его наиболее значительные результаты относятся к математике и физике.

Слайд 22

Описание слайда:

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

Слайд 23

Описание слайда:

Гамильтоновы графы Итак, в 1857 году Уильям Роуэн Гамильтон придумал игру. Существует несколько версий того, как это произошло. По одной из версий он описал эту игру в письме к другу. Согласно другой, он действительно изобрел игру и продал ее производителю игрушек.

Слайд 24

Описание слайда:

Гамильтоновы графы В любом случае игра, по-видимому, включала додекаэдр, т.е. правильный многогранник, граней которого представляли собой конгруэнтные правильные пятиугольники. В каждом из углов, или вершин тела, просверливалась дырка, в которую вставлялся колышек, изображавший город.

Слайд 25

Описание слайда:

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

Слайд 26

Описание слайда:

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

Слайд 27

Описание слайда:

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

Слайд 28

Описание слайда:

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

Слайд 29

Описание слайда:

Гамильтоновы графы Пример 1 На рисунке изображен гамильтонов цикл в полном двудольном графе

Слайд 30

Описание слайда:

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

Слайд 31

Описание слайда:

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

Слайд 32

Описание слайда:

Гамильтоновы графы Приведем один из простейших результатов такого сорта. Теорема 1 Если – связный простой граф с вершинами и если степень каждой вершины удовлетворяет неравенству то – гамильтонов граф.

Слайд 33

Описание слайда:

Гамильтоновы графы Теорема 1 Если – связный простой граф с вершинами и если степень каждой вершины удовлетворяет неравенству то – гамильтонов граф. Условие, накладываемое на степени вершин: , – не является необходимым условием гамильтоновости графа . Граф может быть гамильтоновым и без выполнения этого условия.

Слайд 34

Описание слайда:

Гамильтоновы графы Убедимся в этом, обратившись к графу додекаэдра. Этот граф имеет вершин, степень каждой вершины равна , однако, граф – гамильтонов.

Слайд 35

Описание слайда:

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

Слайд 36

Описание слайда:

Гамильтоновы графы Задача 1 Покажите, что каждый из графов, изображенных на рисунке и связанных с правильными многогранниками (тетраэдр – слева и куб – справа) является гамильтоновым.

Слайд 37

Описание слайда:

Гамильтоновы графы Задача 1 Покажите, что каждый из графов, изображенных на рисунке и связанных с правильными многогранниками (октаэдр – слева и икосаэдр – справа) является гамильтоновым.

Слайд 38

Описание слайда:

Изоморфизм графов Рассмотрим два графа и определенные следующим образом: имеет множество вершин и матрицу смежности , и имеет множество вершин и матрицу смежности , где

Слайд 39

Описание слайда:

Изоморфизм графов имеет множество вершин и матрицу смежности

Слайд 40

Описание слайда:

Изоморфизм графов имеет множество вершин и матрицу смежности

Слайд 41

Описание слайда:

После недолгих раздумий становится очевидным, что графы и по существу одинаковы.

Слайд 42

Описание слайда:

Если мы переименуем вершины графа как , в указанном порядке, и переименуем ребра как for то эти две диаграммы будут различными графическими представлениями одного и того же графа.

Слайд 43

Описание слайда:

Изоморфизм графов Определение 1 Пусть и – два графа. Изоморфизм из в состоит из пары биекций и таких, что для каждого ребра графа , если , то . Два графа называют изоморфными и пишут, если существует изоморфизм из одного графа на другой.

Слайд 44

Описание слайда:

Изоморфизм графов Условие если , то гарантирует, что биекции между множествами вершин и множествами ребер двух графов корректно согласованы друг с другом. Другими словами, если ребро графа соответствует ребру графа то множества вершин, инцидентные этим ребрам, также соответствуют друг другу (относительно биекции ).

Слайд 45

Описание слайда:

Изоморфизм графов Если ребро графа соответствует ребру графа то множества вершин, инцидентные этим ребрам, также соответствуют друг другу (относительно биекции ). Это показано на рисунке.

Слайд 46

Описание слайда:

Изоморфизм графов Пусть обозначает множество ребер, соединяющих вершины и в графе , тогда реберное отображение определяет биекцию Поэтому для всех пар вершин графа , , т.e. число ребер графа , соединяющих и равно числу ребер графа , соединяющих соответствующие им вершины и .

Слайд 47

Описание слайда:

Изоморфизм графов Пусть – простой граф. Чтобы определить изоморфизм из в , нам нужно только корректно специфицировать биекцию . Действительно, любую пару вершин соединяет не более одного ребра. Поэтому, если биекция (корректно) определена, то существует единственная функция удовлетворяющая требуемым свойствам.

Слайд 48

Описание слайда:

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

Слайд 49

Описание слайда:

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

Слайд 50

Описание слайда:

Изоморфизм графов Теорема 1 Пусть – изоморфизм из на тогда: и имеют одинаковое число вершин; и имеют одинаковое число ребер; и имеют одинаковое число компонент; Соответствующие вершины имеют одинаковые степени: для любой , и имеют одинаковые степенные последовательности; если является простым, то – также простой; если является эйлеровым, то – также эйлеров; если является гамильтоновым, то – также гамильтонов.

Слайд 51

Описание слайда:

? Пусть – изоморфизм из в тогда и имеют одинаковое число вершин. Доказательство Изоморфизм из в состоит из пары биекций и таких, что для каждого ребра графа , если , то . Если – биекция, где и – конечные множества, то . Таким образом, .

Слайд 52

Описание слайда:

? Пусть – изоморфизм из в тогда и имеют одинаковое число ребер. Доказательство Изоморфизм из в состоит из пары биекций и таких, что для каждого ребра графа , если , то . Если – биекция, где и – конечные множества, то . Таким образом, .

Слайд 53

Описание слайда:

? Пусть – изоморфизм из в тогда и имеют одинаковое число компонент. Доказательство Если , , , – путь, соединяющий и в , то , , , – путь, соединяющий и в . Обратно, если , , , – путь, соединяющий и в , то – путь в соединяющий и . Поэтому и принадлежат одной и той же компоненте графа тогда и только тогда, когда и принадлежат одной и той же компоненте графа . Следовательно, и имеют одинаковое число компонент.

Слайд 54

Описание слайда:

? Пусть – изоморфизм из в тогда соответствующие вершины имеют одинаковые степени: для любой , Доказательство и Осталось заметить, что – биекция и отображение определяет биекцию

Слайд 55

Описание слайда:

? Пусть – изоморфизм из в тогда и имеют одинаковые степенные последовательности. Доказательство Это утверждение следует из d).

Слайд 56

Описание слайда:

? Пусть – изоморфизм из в . Если является простым, то – также простой. Доказательство – простой граф тогда и только тогда, когда и для всех . Результат следует из существования биекций

Слайд 57

Описание слайда:

? Пусть – изоморфизм из в . Если является эйлеровым, то – также эйлеров. Доказательство Связный граф является эйлеровым тогда и только тогда, когда степень каждой его вершины четна. Но и имеют одинаковые степенные последовательности.

Слайд 58

Описание слайда:

? Пусть – изоморфизм из в . Если является гамильтоновым, то – также гамильтонов. Доказательство Если , , , – гамильтонов цикл в то , , , – гамильтонов цикл в .

Слайд 59

Описание слайда:

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

Слайд 60

Описание слайда:

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

Слайд 61

Описание слайда:

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

Слайд 62

Описание слайда:

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

Слайд 63

Описание слайда:

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

Слайд 64

Описание слайда:

Пример Определим, какие из приведенных графов являются изоморфными. Итак, графы и не являются гамильтоновыми. Графы и – гамильтоновы. Отсюда следует, что ни граф ни не изоморфны графу или графу . Проверить, является ли произвольный граф не гамильтоновым, довольно сложно. Поэтому можно предложить другое доказательство последних неизоморфностей.

Слайд 65

Описание слайда:

Пример Определим, какие из приведенных графов являются изоморфными. Графы и не изоморфны: в графе вершина степени 4 является смежной с двумя вершинами степени 3, а в графе вершина степени 4 является смежной с четырьмя вершинами степени 3.

Слайд 66

Описание слайда:

Слайд 67

Описание слайда:

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

Слайд 68

Описание слайда:

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

Слайд 69

Описание слайда:

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

Слайд 70

Описание слайда:

Пример Определим, какие из приведенных графов являются изоморфными. Графы и неизоморфны. В имеется вершина степени 3 (вершина ), смежная с двумя другими вершинами степени 3, а в каждая вершина степени 3 является смежной только с одной вершиной степени 3.

Слайд 71

Описание слайда:

Пример Определим, какие из приведенных ниже графов являются изоморфными. Подведем итоги: графы (a) и (c) изоморфны, а осталь- ные пары графов не являются изоморфными.

Слайд 72

Описание слайда:

Изоморфизм графов Принцип изоморфизма Чтобы доказать, что два графа изоморфны, следует построить изоморфизм из одного графа на другой; чтобы доказать, что два графа неизоморфны, следует найти теоретико-графовое свойство, которым один граф обладает, а второй – нет.