Эйлеровы графы. Пути и циклы Эйлера - презентация, доклад, проект скачать

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

Эйлеровы графы. Пути и циклы Эйлера, слайд №1

Эйлеровы графы. Пути и циклы Эйлера, слайд №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

Содержание ▲

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

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

Слайд 1

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

Тема 2 Эйлеровы графы. Пути и циклы Эйлера

Слайд 2

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

Пусть G=(V, E) - граф. Цикл, который включает все ребра и вершины графа G, называется эйлеровым циклом. Если это условие выполняется, то граф G эйлеров цикл. Теорема. Граф с более чем одной вершиной имеет эйлеров цикл тогда и только тогда, когда он связный и каждая вершина имеет одну (четную) степень.

Слайд 3

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

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

Слайд 4

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

Граф имеет не эйлеров цикл, поскольку степени вершин v2 и v4 - нечетные.

Слайд 5

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

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

Слайд 6

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

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

Слайд 7

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

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

Слайд 8

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

Пусть G=(V, E) – ориентированный граф. Ориентированным циклом называется ориентированный путь ненулевой длины из вершины в ту ж вершину без повторения ребер. Определение. Пусть G=(V, E) – ориентированный граф. Ориентированный цикл, который включает все ребра и вершины графа G, называется эйлеровым циклом. Ориентированный граф G имеет эйлеров цикл.

Слайд 9

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

Определение. Вершина w орграфа D (графа G) достижима из вершины v, если либо v=w, либо существует путь из v в w. Более удобное определение связных графов. Определение. Граф называется связным, если для любых двух его вершин v, w существует простая цепь из v в w. Определение. Граф (орграф) называется связным (сильно связным), если для любых двух его вершин v,w существует путь, соединяющий v, w (из v и w).

Слайд 10

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

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

Слайд 11

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

Данный граф является связным: k = 0.

Слайд 12

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

Пусть G – простой граф с n вершинами и k компонентами. Тогда число m его ребер удовлетворяет неравенствам Следствие. Любой простой граф с n вершинами и более чем (m-1)(m-2)/2 ребрами связен.

Слайд 13

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

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

Слайд 14

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

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

Слайд 15

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

Для графа каждое из множеств {e1, e2,e5} и {e3, e6,e7, e8} является разделяющим. Разрезом является множество ребер {e1,e2}.

Слайд 16

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

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

Слайд 17

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

Ориентированный граф не имеет эйлерова цикла, т.к. степень входа вершины v1 не равна степени выхода.

Слайд 18

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

Гиперкубы и код Грея

Слайд 19

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

Определение: Определение: Расстояние между двумя вершинами графа называется длина самого короткого пути между этими двумя вершинами. Определение: Диаметром графа называется наибольшее расстояние между двумя любыми его вершинами. Для лучшей реализации программы вместо одиночного использования процессоров, несколько процессоров соединяются для выполнения программы в параллельном режиме. Один из способов связи компьютеров есть соединение их сериями в кольцо. Недостаток этого метода в том, что для передачи информации потребуется прохождение через значительное число процессов. Незначительное улучшение дает использование сетки, или прямоугольного массива процессоров, когда они помещены в каждой точке сетки. В общем случае сетки M x N возможна ситуация прохождения информации через M + N – 1 процессор.

Слайд 20

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

Слайд 21

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

Таблица – список всех возможных комбинаций утверждений

Слайд 22

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

Карта Карно для n=2 Для n=3 Для n=4

Слайд 23

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

Последовательность вершин для k+1 –мерного куба, используя последовательность вершин k –мерного куба: 1) Поместить 1 перед каждой вершиной в последовательности вершин k –мерного куба. Вершины, которые были смежными в k –мерном кубе, с приставленной единицей остаются смежными в k+1 –мерном кубе. 2) Поместить 0 перед каждой вершиной в последовательности вершин k –мерного куба. Вершины, которые были смежными в k –мерном кубе, с приставленным нулем остаются смежными в k+1 –мерном кубе. 3) Поместить последовательность, построенную в пункте (2), вслед за последовательностью, построенной в пункте (1).

Слайд 24

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

Реверсируем список вершин для k –мерного куба, т.е. порядок вершин в списке изменим на обратный. Формирование списка вершин 2-мерного куба: 1 0 Меняем порядок элементов в столбце 0 1 Помещаем 0 перед каждым элементом 1 1 1 0 0 0 0 1

Слайд 25

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

Список вершин для 3-мерного куба: Перейдем Приведенная процедура всегда будет давать последовательность вершин для k –мерного куба, которую называют k –списком. В таком k –списке (1) каждая вершина последовательности является смежной для следующей вершины и (2) первая вершина последовательности является смежной к последней вершине последовательности.

Слайд 26

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

Код Грея Правило построения кода Грея для k+1 : 1) Поместить 1 перед каждой вершиной в k –списке k –мерного куба. Вершины, смежные в k –мерном кубе, с приставленной впереди 1 остаются смежными в k+1 –мерном кубе. 2) Поместить 0 перед каждой вершиной в реверсированном k –списке k –мерного куба. Вершины, смежные в k –мерном кубе, с приставленным впереди 0 остаются смежными в k+1 –мерном кубе. 3) Разместить последовательность, сформированную в (2), после последовательности, сформированной в (1).

Слайд 27

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

Пример. 3-список и реверсированный 3-список представляют собой соответственно Перейдем

Слайд 28

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

Следовательно, код Грея для n=4

Слайд 29

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

Соединение компьютеров в конфигурацию сетки или решета. Сетка – граф, вершины которого заданы массивом размерности mn , для которого две вершины, соседствующие в одной и той же строке или столбце массива, являются смежными как вершины графа. Возможно ли для m 2k и n  2l построить подгаф k+l –мерного куба, т.е. сетку размера mn ? Делали для карт Карно. Обозначим строки согласно первым m элементам кода Грея для k и обозначим столбцы согласно первым m элементам кода Грея для l . Элемент позиции (i, j) сетки есть метка i–ой строки, за которой следует метка j –го столбца.

Слайд 30

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

Пример. Сетка 37 (i, j) –ый элемент сетки является элементом таблицы. Примеры доказывают теорему:

Слайд 31

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

Теорема Каждая сетка размера mn представляет собой подграф i + j -мерного куба, где m 2i и n  2j .

Слайд 32

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

Теорема Каждый гиперкуб для n  1 является двудольным графом, в котором непересекающиеся множества вершин состоят из множества тех вершин, которые изображаются строками, содержащими четное число единиц, и множества вершин, которые изображаются строками, содержащими нечетное число единиц. Двудо́льный граф или бигра́ф — это граф, множество вершин которого можно разбить на две части таким образом, что каждое ребро графа соединяет какую-то вершину из одной части с какой-то вершиной другой части, то есть не существует ребра, соединяющего две вершины из одной и той же части.