Презентация «Эйлеровы графы. Пути и циклы Эйлера»

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

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

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

Pic.1
Тема 2 Эйлеровы графы. Пути и циклы Эйлера
Тема 2 Эйлеровы графы. Пути и циклы Эйлера
Pic.2
Пусть G=(V, E) - граф. Цикл, который включает все ребра и вершины графа G, называется эйлеровым цикл
Пусть G=(V, E) - граф. Цикл, который включает все ребра и вершины графа G, называется эйлеровым циклом. Если это условие выполняется, то граф G эйлеров цикл. Теорема. Граф с более чем одной вершиной …
Pic.3
Граф имеет эйлеров цикл, поскольку степень каждой его вершины четная.
Граф имеет эйлеров цикл, поскольку степень каждой его вершины четная.
Pic.4
Граф имеет не эйлеров цикл, поскольку степени вершин v2 и v4 - нечетные.
Граф имеет не эйлеров цикл, поскольку степени вершин v2 и v4 - нечетные.
Pic.5
Пусть G=(V, E) – граф. Путь, который включает каждое ребро графа G только один раз называется эйлеро
Пусть G=(V, E) – граф. Путь, который включает каждое ребро графа G только один раз называется эйлеровым путем. В этом случае граф G имеет эйлеров путь. Если эйлеров путь не является эйлеровым циклом, …
Pic.6
Граф имеет собственный эйлеров путь, т. к. ровно две его вершины имеют нечетную степень.
Граф имеет собственный эйлеров путь, т. к. ровно две его вершины имеют нечетную степень.
Pic.7
Граф не имеет собственного эйлерова пути, т. к. четыре две его вершины имеют нечетную степень.
Граф не имеет собственного эйлерова пути, т. к. четыре две его вершины имеют нечетную степень.
Pic.8
Пусть G=(V, E) – ориентированный граф. Ориентированным циклом называется ориентированный путь ненуле
Пусть G=(V, E) – ориентированный граф. Ориентированным циклом называется ориентированный путь ненулевой длины из вершины в ту ж вершину без повторения ребер. Определение. Пусть G=(V, E) – …
Pic.9
Определение. Вершина w орграфа D (графа G) достижима из вершины v, если либо v=w, либо существует пу
Определение. Вершина w орграфа D (графа G) достижима из вершины v, если либо v=w, либо существует путь из v в w. Более удобное определение связных графов. Определение. Граф называется связным, если …
Pic.10
Определение. Орграф называется односторонне связным, если для любых его двух вершин, по крайней мере
Определение. Орграф называется односторонне связным, если для любых его двух вершин, по крайней мере, одна достижима из другой. Определение. Если граф не является связным, то он называется несвязным. …
Pic.11
Данный граф является связным: k = 0.
Данный граф является связным: k = 0.
Pic.12
Пусть G – простой граф с n вершинами и k компонентами. Тогда число m его ребер удовлетворяет неравен
Пусть G – простой граф с n вершинами и k компонентами. Тогда число m его ребер удовлетворяет неравенствам Следствие. Любой простой граф с n вершинами и более чем (m-1)(m-2)/2 ребрами связен.
Pic.13
При исследовании графов возникает вопрос: насколько сильно связен связный граф? Этот вопрос можно сф
При исследовании графов возникает вопрос: насколько сильно связен связный граф? Этот вопрос можно сформулировать и так: сколько ребер нужно удалить из графа, чтобы он перестал быть связным? Под …
Pic.14
Определение. Разрезом называется такое разделяющее множество, никакое собственное подмножество котор
Определение. Разрезом называется такое разделяющее множество, никакое собственное подмножество которого не является разделяющим. Определение. Разрез, состоящий из одного ребра, называется мостом …
Pic.15
Для графа каждое из множеств {e1, e2,e5} и {e3, e6,e7, e8} является разделяющим. Разрезом является м
Для графа каждое из множеств {e1, e2,e5} и {e3, e6,e7, e8} является разделяющим. Разрезом является множество ребер {e1,e2}.
Pic.16
Ориентированный граф имеет эйлеров цикл тогда и только тогда, когда он связный и степень входа каждо
Ориентированный граф имеет эйлеров цикл тогда и только тогда, когда он связный и степень входа каждой вершины равна ее степени выхода. Пример. Ориентированный граф имеет эйлеров цикл, т. к. степень …
Pic.17
Ориентированный граф не имеет эйлерова цикла, т. к. степень входа вершины v1 не равна степени выхода
Ориентированный граф не имеет эйлерова цикла, т. к. степень входа вершины v1 не равна степени выхода.
Pic.18
Гиперкубы и код Грея
Гиперкубы и код Грея
Pic.19
Определение: Определение: Расстояние между двумя вершинами графа называется длина самого короткого п
Определение: Определение: Расстояние между двумя вершинами графа называется длина самого короткого пути между этими двумя вершинами. Определение: Диаметром графа называется наибольшее расстояние …
Pic.20
«Эйлеровы графы. Пути и циклы Эйлера», слайд 20
Pic.21
Таблица – список всех возможных комбинаций утверждений
Таблица – список всех возможных комбинаций утверждений
Pic.22
Карта Карно для n=2 Для n=3 Для n=4
Карта Карно для n=2 Для n=3 Для n=4
Pic.23
Последовательность вершин для k+1 –мерного куба, используя последовательность вершин k –мерного куба
Последовательность вершин для k+1 –мерного куба, используя последовательность вершин k –мерного куба: 1) Поместить 1 перед каждой вершиной в последовательности вершин k –мерного куба. Вершины, …
Pic.24
Реверсируем список вершин для k –мерного куба, т. е. порядок вершин в списке изменим на обратный. Фо
Реверсируем список вершин для k –мерного куба, т. е. порядок вершин в списке изменим на обратный. Формирование списка вершин 2-мерного куба: 1 0 Меняем порядок элементов в столбце 0 1 Помещаем 0 …
Pic.25
Список вершин для 3-мерного куба: Перейдем Приведенная процедура всегда будет давать последовательно
Список вершин для 3-мерного куба: Перейдем Приведенная процедура всегда будет давать последовательность вершин для k –мерного куба, которую называют k –списком. В таком k –списке (1) каждая вершина …
Pic.26
Код Грея Правило построения кода Грея для k+1 : 1) Поместить 1 перед каждой вершиной в k –списке k –
Код Грея Правило построения кода Грея для k+1 : 1) Поместить 1 перед каждой вершиной в k –списке k –мерного куба. Вершины, смежные в k –мерном кубе, с приставленной впереди 1 остаются смежными в k+1 …
Pic.27
Пример. 3-список и реверсированный 3-список представляют собой соответственно Перейдем
Пример. 3-список и реверсированный 3-список представляют собой соответственно Перейдем
Pic.28
Следовательно, код Грея для n=4
Следовательно, код Грея для n=4
Pic.29
Соединение компьютеров в конфигурацию сетки или решета. Сетка – граф, вершины которого заданы массив
Соединение компьютеров в конфигурацию сетки или решета. Сетка – граф, вершины которого заданы массивом размерности mn , для которого две вершины, соседствующие в одной и той же строке или столбце …
Pic.30
Пример. Сетка 37 (i, j) –ый элемент сетки является элементом таблицы. Примеры доказывают теорему:
Пример. Сетка 37 (i, j) –ый элемент сетки является элементом таблицы. Примеры доказывают теорему:
Pic.31
Теорема Каждая сетка размера mn представляет собой подграф i + j -мерного куба, где m 2i и n  2j
Теорема Каждая сетка размера mn представляет собой подграф i + j -мерного куба, где m 2i и n  2j .
Pic.32
Теорема Каждый гиперкуб для n  1 является двудольным графом, в котором непересекающиеся множества в
Теорема Каждый гиперкуб для n  1 является двудольным графом, в котором непересекающиеся множества вершин состоят из множества тех вершин, которые изображаются строками, содержащими четное число …
Pic.33
!
!


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

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