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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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