Теория графов путь, цепь, цикл - презентация, доклад, проект скачать

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

Теория графов путь, цепь, цикл, слайд №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

Содержание ▲

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

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

Слайд 1

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

ТЕОРИЯ ГРАФОВ ПУТЬ, ЦЕПЬ, ЦИКЛ Путь (маршрут) – конечная последовательность ребер графа, в котором два соседних ребра соединены общей вершиной. В маршруте одно и тоже ребро может встречаться несколько раз. Путь – это совокупность ребер, которые объединены вершинами таким образом, что можно двигаться по ним вдоль графа. Обозначение маршрута – v0,v1,…vk.

Слайд 2

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

ТЕОРИЯ ГРАФОВ ПУТЬ, ЦЕПЬ, ЦИКЛ Путь длины k – последовательность, содержащая k ребер. Длина пути - количество ребер в нем; каждое ребро считается столько раз, сколько оно встречается в маршруте.

Слайд 3

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

ТЕОРИЯ ГРАФОВ ПУТЬ, ЦЕПЬ, ЦИКЛ Путь называется простым или цепью, если все его ребра различны. Если все вершины в цепи различны, то она является простой цепью. Циклом называется путь, в котором v0=vk,. Простой цикл – цикл, у которого все ребра и все вершины, кроме концов, различны. В простой цепи число вершин на единицу больше, чем число ребер, а в простом цикле их количество совпадает.

Слайд 4

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

ТЕОРИЯ ГРАФОВ ПУТЬ, ЦЕПЬ, ЦИКЛ Пример. Определить возможные маршруты и их длину из вершины v0 в вершину v8 в графе (рис. 12) Рисунок 12

Слайд 5

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

ТЕОРИЯ ГРАФОВ ПУТЬ, ЦЕПЬ, ЦИКЛ Решение. Пути: 1) v0v3v8 длиной 2; 5) v0v3v4v5v4v7v8 длиной 6; 2) v0v1v2v3v8 длиной 4; 6) v0v1v2v3v4v7v8 длиной 6; 3) v0v3v4v7v8 длиной 4; 7) v0v1v2v3v4v5v6v7v8 длиной 8; 4) v0v3v4v5v6v7v8 длиной 6; 8) v0v1v2v3v4v7v6v5v4v3v8 длиной 10.

Слайд 6

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

ТЕОРИЯ ГРАФОВ ПУТЬ, ЦЕПЬ, ЦИКЛ Маршрут v0v1v2v3v0 для графа (рис. 12) является простым циклом; маршрут v3v4v5v6v7v4v3 является циклом, но не будет простым, потому что содержит повторяющиеся вершины.

Слайд 7

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

ТЕОРИЯ ГРАФОВ ПУТЬ, ЦЕПЬ, ЦИКЛ Эйлеров цикл – последовательность вершин (может быть и с повторениями), через которые проходит искомый маршрут. Цикл, проходящий через каждую вершину графа в точности один раз, называется гамильтоновым, а соответствующий граф – гамилътоновым графом.

Слайд 8

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

ТЕОРИЯ ГРАФОВ СВЯЗНОСТЬ ГРАФА Вершины v’ и v’’ называются связными, если существует маршрут с началом в вершине v’ и концом в v’’. Граф называется связным, если любые пары его вершин связаны между собой.

Слайд 9

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

ТЕОРИЯ ГРАФОВ СВЯЗНОСТЬ ГРАФА Граф, изображенный на рис. 13 (a) – не связный, а граф на рис. 13 (б) – связный. Рисунок 13

Слайд 10

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

ТЕОРИЯ ГРАФОВ КОЛИЧЕСТВО МАРШРУТОВ Для определения наличия маршрута между двумя вершинами используется матрица смежности. Булево произведение матрицы В с самой собой обозначается через В2. В этой матрице 1 символизирует наличие пути длины 2. По матрице В3 = В * В * В можно определить все пути длины 3, т.е., матрица Вk хранит сведения о путях длины к.

Слайд 11

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

ТЕОРИЯ ГРАФОВ КОЛИЧЕСТВО МАРШРУТОВ Пример. Для графа (рис. 14) определим, какие и в каком количестве существуют пути между вершинами. Рисунок 14

Слайд 12

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

ТЕОРИЯ ГРАФОВ ОСНОВНЫЕ ПОНЯТИЯ Матрица смежности Матрица В2

Слайд 13

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

ТЕОРИЯ ГРАФОВ ОСНОВНЫЕ ПОНЯТИЯ Матрица В3 Матрица В4

Слайд 14

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

ТЕОРИЯ ГРАФОВ КОЛИЧЕСТВО МАРШРУТОВ При использовании алгебраических операций получаем матрицу, которая характеризует не только наличие путей между вершинами, но и количество таких путей.

Слайд 15

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

ТЕОРИЯ ГРАФОВ КОЛИЧЕСТВО МАРШРУТОВ Матрица смежности

Слайд 16

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

ТЕОРИЯ ГРАФОВ КОЛИЧЕСТВО МАРШРУТОВ Матрица А2 Элемент матрицы «говорит» о количестве путей между вершинами, а показатель степени указывает длину пути.

Слайд 17

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

ТЕОРИЯ ГРАФОВ КОЛИЧЕСТВО МАРШРУТОВ Матрица А2 В этом случае может говорить о наличии пути между вершинами длиной 2.

Слайд 18

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

ТЕОРИЯ ГРАФОВ МАТРИЦА ДОСТИЖИМОСТИ Матрица достижимости ориентированного графа – бинарная матрица замыкания по транзитивности. Таким образом, в матрице достижимости хранится информация о существовании путей между вершинами орграфа.

Слайд 19

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

ТЕОРИЯ ГРАФОВ МАТРИЦА ДОСТИЖИМОСТИ Для нахождения матрицы достижимости начинаем работу с построения матрицы смежности. Находим булевы степени этой матрицы: В2, В3, …, Вn Находим матрицу достижимости: В*=ВВ2  …  Вn

Слайд 20

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

ТЕОРИЯ ГРАФОВ МАТРИЦА ДОСТИЖИМОСТИ Матрица смежности Матрица В2

Слайд 21

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

ТЕОРИЯ ГРАФОВ МАТРИЦА ДОСТИЖИМОСТИ Более удобный путь определения матрицы достижимости дает так называемый алгоритм Уоршелла (алгоритм Флойда – Уоршелла) – алгоритм для нахождения расстояний между всеми вершинами орграфа. Разработан в 1962 году Робертом Флойдом и Стивеном Уоршеллом.

Слайд 22

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

ТЕОРИЯ ГРАФОВ МАТРИЦА ДОСТИЖИМОСТИ Алгоритм Уоршелла генерирует последовательность матриц W0…Wn, матрица W0 совпадает с матрицей смежности орграфа, а Wn – искомая матрица достижимости.

Слайд 23

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

ТЕОРИЯ ГРАФОВ АЛГОРИТМ УОРШЕЛЛА Берем k-ый столбец матрицы Wk-1 Строку с номером i(i=1,…,n), у которой на k-ом месте стоит 0, переписываем в i-ую строку марицы Wk . Строку с номером i(i=1,…,n), у которой на k-ом месте стоит 1, объединяем с помощью операции или с k-ой строкой, а результат записываем в i-ую строку марицы Wk .

Слайд 24

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

ТЕОРИЯ ГРАФОВ АЛГОРИТМ УОРШЕЛЛА Пример. Матрица смежности орграфа (рис. 14) Вычисляем матрицу W1. Учитывая первый шаг, рассматриваем 1-ый столбец матрицы W0. Следуя указаниям шага 2, скопируем строки матрицы W0, в первом столбце которой стоят 0.

Слайд 25

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

ТЕОРИЯ ГРАФОВ АЛГОРИТМ УОРШЕЛЛА Вычисляем матрицу W2. Рассматриваем 2-ой столбец матрицы W1. Скопируем строки матрицы W1, во втором столбце которой стоят 0.

Слайд 26

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

ТЕОРИЯ ГРАФОВ АЛГОРИТМ УОРШЕЛЛА Рассчитываем значения в строке 1-ой и 3-ей, выполняя дизъюнкцию k-ой строки (второй) со строками, у которых на k-ом месте стоит 1.

Слайд 27

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

ТЕОРИЯ ГРАФОВ АЛГОРИТМ УОРШЕЛЛА Вычисляем матрицу W3. Рассматриваем 3-ий столбец матрицы W2. Копируем строки, у которых в 3-ем столбце 0: вторую и третью Рассчитываем значения в строке 1-ой и 4-ой, выполняя дизъюнкцию k-ой строки (третьей) со строками, у которых на k-ом месте стоит 1.

Слайд 28

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

ТЕОРИЯ ГРАФОВ АЛГОРИТМ УОРШЕЛЛА Вычисляем матрицу W4. Рассматриваем 4-ый столбец матрицы W3. Копируем строки, у которых в 4-ом столбце 0: вторую Рассчитываем значения в строке 1-ой, 3-ей и 4-ой, выполняя дизъюнкцию k-ой строки (четвертой) со строками, у которых на k-ом месте стоит 1. Полученная матрица является матрицей достижимости – W*.