🗊Презентация Теория графов путь, цепь, цикл

Категория: Математика
Нажмите для полного просмотра!
Теория графов путь, цепь, цикл, слайд №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.
Описание слайда:
ТЕОРИЯ ГРАФОВ ПУТЬ, ЦЕПЬ, ЦИКЛ Путь (маршрут) – конечная последовательность ребер графа, в котором два соседних ребра соединены общей вершиной. В маршруте одно и тоже ребро может встречаться несколько раз. Путь – это совокупность ребер, которые объединены вершинами таким образом, что можно двигаться по ним вдоль графа. Обозначение маршрута – v0,v1,…vk.

Слайд 2


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

Слайд 3


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

Слайд 4


ТЕОРИЯ ГРАФОВ ПУТЬ, ЦЕПЬ, ЦИКЛ Пример. Определить возможные маршруты и их длину из вершины v0 в вершину v8 в графе (рис. 12) Рисунок 12
Описание слайда:
ТЕОРИЯ ГРАФОВ ПУТЬ, ЦЕПЬ, ЦИКЛ Пример. Определить возможные маршруты и их длину из вершины 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.
Описание слайда:
ТЕОРИЯ ГРАФОВ ПУТЬ, ЦЕПЬ, ЦИКЛ Решение. Пути: 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 является циклом, но не будет простым, потому что содержит повторяющиеся вершины.
Описание слайда:
ТЕОРИЯ ГРАФОВ ПУТЬ, ЦЕПЬ, ЦИКЛ Маршрут v0v1v2v3v0 для графа (рис. 12) является простым циклом; маршрут v3v4v5v6v7v4v3 является циклом, но не будет простым, потому что содержит повторяющиеся вершины.

Слайд 7


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

Слайд 8


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

Слайд 9


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

Слайд 10


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

Слайд 11


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

Слайд 12


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

Слайд 13


ТЕОРИЯ ГРАФОВ ОСНОВНЫЕ ПОНЯТИЯ Матрица В3 Матрица В4
Описание слайда:
ТЕОРИЯ ГРАФОВ ОСНОВНЫЕ ПОНЯТИЯ Матрица В3 Матрица В4

Слайд 14


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

Слайд 15


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

Слайд 16


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

Слайд 17


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

Слайд 18


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

Слайд 19


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

Слайд 20


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

Слайд 21


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

Слайд 22


ТЕОРИЯ ГРАФОВ МАТРИЦА ДОСТИЖИМОСТИ Алгоритм Уоршелла генерирует последовательность матриц W0…Wn, матрица W0 совпадает с матрицей смежности орграфа, а Wn – искомая матрица достижимости.
Описание слайда:
ТЕОРИЯ ГРАФОВ МАТРИЦА ДОСТИЖИМОСТИ Алгоритм Уоршелла генерирует последовательность матриц 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 .
Описание слайда:
ТЕОРИЯ ГРАФОВ АЛГОРИТМ УОРШЕЛЛА Берем 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.
Описание слайда:
ТЕОРИЯ ГРАФОВ АЛГОРИТМ УОРШЕЛЛА Пример. Матрица смежности орграфа (рис. 14) Вычисляем матрицу W1. Учитывая первый шаг, рассматриваем 1-ый столбец матрицы W0. Следуя указаниям шага 2, скопируем строки матрицы W0, в первом столбце которой стоят 0.

Слайд 25


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

Слайд 26


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

Слайд 27


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

Слайд 28


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

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию