Слайд 2
![ТЕОРИЯ ГРАФОВ ПУТЬ, ЦЕПЬ, ЦИКЛ Путь длины k – последовательность,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/212250/slide-1.jpg)
ТЕОРИЯ ГРАФОВ
ПУТЬ, ЦЕПЬ, ЦИКЛ
Путь длины k – последовательность, содержащая k
ребер. Длина пути - количество ребер в нем; каждое ребро считается столько раз, сколько оно встречается в маршруте.
Слайд 3
![ТЕОРИЯ ГРАФОВ ПУТЬ, ЦЕПЬ, ЦИКЛ Путь называется простым или цепью,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/212250/slide-2.jpg)
ТЕОРИЯ ГРАФОВ
ПУТЬ, ЦЕПЬ, ЦИКЛ
Путь называется простым или цепью, если все
его ребра различны. Если все вершины в цепи различны, то она является простой цепью.
Циклом называется путь, в котором v0=vk,.
Простой цикл – цикл, у которого все ребра и все вершины, кроме концов, различны.
В простой цепи число вершин на единицу больше, чем число ребер, а в простом цикле их количество совпадает.
Слайд 4
![ТЕОРИЯ ГРАФОВ ПУТЬ, ЦЕПЬ, ЦИКЛ Пример. Определить возможные маршруты и](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/212250/slide-3.jpg)
ТЕОРИЯ ГРАФОВ
ПУТЬ, ЦЕПЬ, ЦИКЛ
Пример. Определить возможные маршруты и их длину
из вершины v0 в вершину v8 в графе (рис. 12)
Рисунок 12
Слайд 5
![ТЕОРИЯ ГРАФОВ ПУТЬ, ЦЕПЬ, ЦИКЛ Решение. Пути: 1) v0v3v8 длиной](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/212250/slide-4.jpg)
ТЕОРИЯ ГРАФОВ
ПУТЬ, ЦЕПЬ, ЦИКЛ
Решение.
Пути:
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 для графа (рис.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/212250/slide-5.jpg)
ТЕОРИЯ ГРАФОВ
ПУТЬ, ЦЕПЬ, ЦИКЛ
Маршрут v0v1v2v3v0 для графа (рис. 12) является
простым циклом;
маршрут v3v4v5v6v7v4v3 является циклом, но не будет простым, потому что содержит повторяющиеся вершины.
Слайд 7
![ТЕОРИЯ ГРАФОВ ПУТЬ, ЦЕПЬ, ЦИКЛ Эйлеров цикл – последовательность вершин](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/212250/slide-6.jpg)
ТЕОРИЯ ГРАФОВ
ПУТЬ, ЦЕПЬ, ЦИКЛ
Эйлеров цикл – последовательность вершин (может быть
и с повторениями), через которые проходит искомый маршрут.
Цикл, проходящий через каждую вершину графа в точности один раз, называется гамильтоновым, а соответствующий
граф – гамилътоновым графом.
Слайд 8
![ТЕОРИЯ ГРАФОВ СВЯЗНОСТЬ ГРАФА Вершины v’ и v’’ называются связными,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/212250/slide-7.jpg)
ТЕОРИЯ ГРАФОВ
СВЯЗНОСТЬ ГРАФА
Вершины v’ и v’’ называются связными, если существует маршрут
с началом в вершине v’ и концом в v’’. Граф называется связным, если любые пары его вершин связаны между собой.
Слайд 9
![ТЕОРИЯ ГРАФОВ СВЯЗНОСТЬ ГРАФА Граф, изображенный на рис. 13 (a)](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/212250/slide-8.jpg)
ТЕОРИЯ ГРАФОВ
СВЯЗНОСТЬ ГРАФА
Граф, изображенный на рис. 13 (a) – не связный,
а граф на рис. 13 (б) – связный.
Рисунок 13
Слайд 10
![ТЕОРИЯ ГРАФОВ КОЛИЧЕСТВО МАРШРУТОВ Для определения наличия маршрута между двумя](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/212250/slide-9.jpg)
ТЕОРИЯ ГРАФОВ
КОЛИЧЕСТВО МАРШРУТОВ
Для определения наличия маршрута между двумя вершинами используется матрица
смежности. Булево произведение матрицы В с самой собой обозначается через В2. В этой матрице 1 символизирует наличие пути
длины 2. По матрице В3 = В * В * В можно определить все пути длины 3, т.е., матрица Вk хранит сведения о путях длины к.
Слайд 11
![ТЕОРИЯ ГРАФОВ КОЛИЧЕСТВО МАРШРУТОВ Пример. Для графа (рис. 14) определим,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/212250/slide-10.jpg)
ТЕОРИЯ ГРАФОВ
КОЛИЧЕСТВО МАРШРУТОВ
Пример. Для графа (рис. 14) определим, какие и в
каком количестве существуют пути между вершинами.
Рисунок 14
Слайд 12
![ТЕОРИЯ ГРАФОВ ОСНОВНЫЕ ПОНЯТИЯ Матрица смежности Матрица В2](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/212250/slide-11.jpg)
ТЕОРИЯ ГРАФОВ
ОСНОВНЫЕ ПОНЯТИЯ
Матрица смежности Матрица В2
Слайд 13
![ТЕОРИЯ ГРАФОВ ОСНОВНЫЕ ПОНЯТИЯ Матрица В3 Матрица В4](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/212250/slide-12.jpg)
ТЕОРИЯ ГРАФОВ
ОСНОВНЫЕ ПОНЯТИЯ
Матрица В3 Матрица В4
Слайд 14
![ТЕОРИЯ ГРАФОВ КОЛИЧЕСТВО МАРШРУТОВ При использовании алгебраических операций получаем матрицу,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/212250/slide-13.jpg)
ТЕОРИЯ ГРАФОВ
КОЛИЧЕСТВО МАРШРУТОВ
При использовании алгебраических операций получаем матрицу,
которая характеризует не только
наличие путей между вершинами, но и количество таких путей.
Слайд 15
![ТЕОРИЯ ГРАФОВ КОЛИЧЕСТВО МАРШРУТОВ](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/212250/slide-14.jpg)
ТЕОРИЯ ГРАФОВ
КОЛИЧЕСТВО МАРШРУТОВ
Слайд 16
![ТЕОРИЯ ГРАФОВ КОЛИЧЕСТВО МАРШРУТОВ](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/212250/slide-15.jpg)
ТЕОРИЯ ГРАФОВ
КОЛИЧЕСТВО МАРШРУТОВ
Слайд 17
![ТЕОРИЯ ГРАФОВ КОЛИЧЕСТВО МАРШРУТОВ](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/212250/slide-16.jpg)
ТЕОРИЯ ГРАФОВ
КОЛИЧЕСТВО МАРШРУТОВ
Слайд 18
![ТЕОРИЯ ГРАФОВ МАТРИЦА ДОСТИЖИМОСТИ Матрица достижимости ориентированного графа – бинарная](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/212250/slide-17.jpg)
ТЕОРИЯ ГРАФОВ
МАТРИЦА ДОСТИЖИМОСТИ
Матрица достижимости ориентированного графа – бинарная матрица замыкания по
транзитивности. Таким образом, в матрице достижимости хранится информация о существовании путей между вершинами орграфа.
Слайд 19
![ТЕОРИЯ ГРАФОВ МАТРИЦА ДОСТИЖИМОСТИ Для нахождения матрицы достижимости начинаем работу](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/212250/slide-18.jpg)
ТЕОРИЯ ГРАФОВ
МАТРИЦА ДОСТИЖИМОСТИ
Для нахождения матрицы достижимости начинаем работу с построения матрицы
смежности.
Находим булевы степени этой матрицы: В2, В3, …, Вn
Находим матрицу достижимости:
В*=В∨В2 ∨ … ∨ Вn
Слайд 20
![ТЕОРИЯ ГРАФОВ МАТРИЦА ДОСТИЖИМОСТИ Матрица смежности Матрица В2](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/212250/slide-19.jpg)
ТЕОРИЯ ГРАФОВ
МАТРИЦА ДОСТИЖИМОСТИ
Матрица смежности Матрица В2
Слайд 21
![ТЕОРИЯ ГРАФОВ МАТРИЦА ДОСТИЖИМОСТИ Более удобный путь определения матрицы достижимости](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/212250/slide-20.jpg)
ТЕОРИЯ ГРАФОВ
МАТРИЦА ДОСТИЖИМОСТИ
Более удобный путь определения матрицы достижимости дает так
называемый алгоритм Уоршелла (алгоритм Флойда – Уоршелла) – алгоритм для нахождения расстояний между всеми вершинами орграфа. Разработан в 1962 году Робертом Флойдом и Стивеном Уоршеллом.
Слайд 22
![ТЕОРИЯ ГРАФОВ МАТРИЦА ДОСТИЖИМОСТИ Алгоритм Уоршелла генерирует последовательность матриц W0…Wn,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/212250/slide-21.jpg)
ТЕОРИЯ ГРАФОВ
МАТРИЦА ДОСТИЖИМОСТИ
Алгоритм Уоршелла генерирует последовательность матриц W0…Wn, матрица
W0 совпадает
с матрицей смежности орграфа, а Wn – искомая матрица достижимости.
Слайд 23
![ТЕОРИЯ ГРАФОВ АЛГОРИТМ УОРШЕЛЛА Берем k-ый столбец матрицы Wk-1 Строку](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/212250/slide-22.jpg)
ТЕОРИЯ ГРАФОВ
АЛГОРИТМ УОРШЕЛЛА
Берем k-ый столбец матрицы Wk-1
Строку с номером i(i=1,…,n), у
которой на k-ом месте стоит 0, переписываем в i-ую строку марицы Wk .
Строку с номером i(i=1,…,n), у которой на k-ом месте стоит 1, объединяем с помощью операции или с k-ой строкой, а результат записываем в
i-ую строку марицы Wk .
Слайд 24
![ТЕОРИЯ ГРАФОВ АЛГОРИТМ УОРШЕЛЛА](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/212250/slide-23.jpg)
ТЕОРИЯ ГРАФОВ
АЛГОРИТМ УОРШЕЛЛА
Слайд 25
![ТЕОРИЯ ГРАФОВ АЛГОРИТМ УОРШЕЛЛА](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/212250/slide-24.jpg)
ТЕОРИЯ ГРАФОВ
АЛГОРИТМ УОРШЕЛЛА
Слайд 26
![ТЕОРИЯ ГРАФОВ АЛГОРИТМ УОРШЕЛЛА](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/212250/slide-25.jpg)
ТЕОРИЯ ГРАФОВ
АЛГОРИТМ УОРШЕЛЛА
Слайд 27
![ТЕОРИЯ ГРАФОВ АЛГОРИТМ УОРШЕЛЛА](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/212250/slide-26.jpg)
ТЕОРИЯ ГРАФОВ
АЛГОРИТМ УОРШЕЛЛА