Алгоритмы на графах Волновой метод. Постановка задачи Постановка задачи. Пусть G – неориентированный связный граф, а и b – две его вершины. Требуется.

Презентация:



Advertisements
Похожие презентации
Теория графов Алгоритмы на графах. Медиана графа Медиана вершина графа, у которой сумма кратчайших расстояний от неё до вершин графа минимальная возможная.
Advertisements

Алгоритмы на графах Волновой метод. Постановка задачи Постановка задачи. Пусть G – неориентированный связный граф, а и b – две его вершины. Требуется.
Теория графов Основные определения. Дуга Пусть имеется множество вершин V={V 1,V 2,…,V n } и пусть на нем задано бинарное отношение Г V×V, – V i Г V j.
Графы Волновой метод. Задание графов Пусть граф задан графически. Составить матрицу смежности и матрицу инцидентности для этого графа
Теория графов Основные определения. Задание графов Графический способ – Привести пример графического задания графа, состоящего из вершин А, В и С, связанных.
Графы Комбинаторика. Планеты Между девятью планетами солнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам:
ХНУРЭ, кафедра ПО ЭВМ, Тел , Лекции Н.В. Белоус Факультет компьютерных наук Кафедра ПО ЭВМ, ХНУРЭ Компьютерная.
Теория графов. Теория графов – обширный самостоятельный раздел дискретной математики. Используется при проектировании компьютерных сетей, трубопроводов,
1 Комбинаторные алгоритмы Задача о k-центрах. 2 Метрическая задача o k центрах Дано: Полный граф G = (V, E), стоимости ребер cost: E Q + такие, что для.
Графы Лекция 2. Графы Неориентированным графом (графом) называется тройка (V, E, ), где V и E конечные множества и {X V : | X | = 2}. Ориентированным.
Задача о максимальном потоке в сети Алгоритм Фалкерсона-Форда.
Введение в теорию графов. ЗАДАЧА ПРОКЛАДКИ КОММУНИКАЦИЙ
АЛГОРИТМЫ НАХОЖДЕНИЯ КРАТЧАЙШИХ ПУТЕЙ НА ГРАФАХ..
V-множество вершин, E- множество ребер Граф - G(V, Е). Л. Эйлер 1736 г. G(V, Е, f) V,E – множества, отображение инциденции f: Е V&V множества Е в V&V Основы.
Алгоритм Флойда-Уоршалла Находит кратчайшие расстояния между всеми парами вершин графа Идея: Строится специальная матрица D, элементы которой – кратчайшие.
Теория графов Основные определения. Дуга Пусть имеется множество вершин V={V 1,V 2,…,V n } и пусть на нем задано бинарное отношение Г V×V, – V i Г V j.
Алгоритмы на графах. Задача о максимальном потоке в сетях Требуется от источника к стоку передать максимальное количество энергии. В условиях задачи о.
Транспортные сети ХНУРЭ, кафедра ПО ЭВМ, Тел , Лекция 15 Н.В. Белоус Факультет компьютерных наук Кафедра ПО ЭВМ,
ПРАВОСЛАВНЫЙ СВЯТО-ТИХОНОВСКИЙ БОГОСЛОВСКИЙ УНИВЕРСИТЕТ (БОГОСЛОВСКИЙ ФАКУЛЬТЕТ) Презентация по математике на тему: Элементы теории графов.
Домашнее задание «Применение графа» ВСПОМНИМ… Граф Простейшая модель системы.Отображает элементарный состав системы и структуру связей Сеть Граф с возможностью.
Транксрипт:

Алгоритмы на графах Волновой метод

Постановка задачи Постановка задачи. Пусть G – неориентированный связный граф, а и b – две его вершины. Требуется найти цепь, соединяющую вершины а и b и содержащую наименьшее число ребер.

Волновой метод Алгоритм решения задачи волновым методом. Алгоритм решения задачи волновым методом. 1. Помечаем вершину а индексом Вершины, смежные с а и соединенные с а, дугами, инцидентными вершине а, помечаем индексами Вершины, смежные с помеченными индексами 1 и соединенные с ними инцидентными вершинам 1 дугами, помечаем индексами 2.

Волновой метод 4. Аналогично помечаем вершины индексами 3, 4, … 5. Совокупность вершин, помеченных индексом m, обозначим A m. 6. В некоторой момент будет помечена вершина b, пусть b A n. Останавливаем процесс индексации.

Волновой метод 7. По построению можно найти вершину b 1 A n-1, смежную с b, по тем же соображениям существует вершина b 2 A n-2, смежная с b 1, и т.д. 8. Искомая цепь с наименьшим числом ребер получается теперь как последовательность вершин (b, b 1, b 2, …, b n =a), где b i A n-i, то есть нужно двигаться, начиная от конечной вершины b в сторону убывания индекса вершины.

Задание Найти все кратчайшие цепочки от b до а а b

Условный радиус вершины Если мы не будем останавливать индексацию, то через некоторое количество шагов все вершины графа будут снабжены индексами, причем наибольший из них является условным радиусом графа G относительно вершины а. r a =max d(a, b)

Волновой метод В случае ориентированного графа волновой метод позволяет решить две задачи: Найти длины кратчайших путей от вершины а до остальных вершин графа; Найти длины кратчайших путей от каждой вершины графа до вершины а. При этом в основном алгоритме изменяется только построение множества А n.

Центр и диаметр графа Расстоянием между вершинами a и b называется длина кратчайшей цепи из a в b. Радиус графа определяется как наименьший из условных радиусов вершин графа. Центром графа G называется такая вершина a, что максимальное расстояние между a и любой другой вершиной является наименьшим из всех возможных. Это расстояние называется радиусом графа. Диаметром d связного графа называется максимальное возможное расстояние между любыми двумя его вершинами. Если расстояние между двумя вершинами равно диаметру графа, то кратчайший путь, соединяющий эти вершины, называется диаметральным путем, а подграф, образованный вершинами и ребрами этого пути, – диаметральной цепью.

Задание Найти радиус и диаметр графа

Задание Найти центр, радиус и диаметр графа

Задание Найти радиус, диаметр и центр графа

Задание Найти радиус, диаметр и центр графа

Задание Найти радиус, диаметр и центр графа

Алгоритм Флойда Построим матрицу D 0 размерности |V| x |V|, элементы которой определяются по правилу: d ii 0 = 0; d ij 0 = Weight(v i, v j ), где ij, если в графе существует ребро (дуга) (v i, v j ); d ij 0 = бесконечность, где ij, если нет ребра (дуги) (v i, v j ). m=0

Пример V1V1 V2V2 V3V3 V4V4 V5V5 V1V1 0х332 V2V2 50ххх V3V3 х20х3 V4V4 хх20х V5V5 ххх10 V1 V2 V3 V4 V

Основная часть алгоритма 1. Построим матрицу D m+1 по D m, вычисляя ее элементы следующим образом: d ij m+1 =min{d ij m, d i(m+1) m + d (m+1)j m }, где ij; d ii m+1 =0 (*). Если d im m + d mi m < 0 для какого-то i, то в графе существует цикл (контур) отрицательной длины, проходящий через вершину v i. 2. m:=m+1; если m

Пример m=0 V1V1 V2V2 V3V3 V4V4 V5V5 V1V1 0х332 V2V2 50ххх V3V3 х20х3 V4V4 хх20х V5V5 ххх10 V1V1 V2V2 V3V3 V4V4 V5V5 V1V1 0х332 V2V хх V3V3 х20х3 V4V4 хх20х V5V5 ххх10 V1 V2 V3 V4 V

Пример m=1 V1V1 V2V2 V3V3 V4V4 V5V5 V1V1 0х332 V2V V3V3 х20х3 V4V4 хх20х V5V5 ххх10 V1V1 V2V2 V3V3 V4V4 V5V5 V1V1 0х332 V2V V3V х3 V4V4 хх20х V5V5 ххх10 V1 V2 V3 V4 V

Пример m=2 V1V1 V2V2 V3V3 V4V4 V5V5 V1V1 0х332 V2V V3V V4V4 хх20х V5V5 ххх10 V1V1 V2V2 V3V3 V4V4 V5V5 V1V V2V V3V V4V4 хх20х V5V5 ххх10 V1 V2 V3 V4 V

Пример m=3 V1V1 V2V2 V3V3 V4V4 V5V5 V1V V2V V3V V4V V5V5 ххх10 V1V1 V2V2 V3V3 V4V4 V5V5 V1V V2V V3V V4V V5V5 9+1хх10 V1 V2 V3 V4 V

Пример m=4 V1V1 V2V2 V3V3 V4V4 V5V5 V1V V2V V3V V4V V5V V1V1 V2V2 V3V3 V4V4 V5V5 V1V V2V V3V V4V V5V V1 V2 V3 V4 V

Пример m=5 V1V1 V2V2 V3V3 V4V4 V5V5 V1V V2V V3V V4V V5V

Пример V1V1 V2V2 V3V3 V4V4 V5V5 V1V V2V V3V V4V V5V φ 1 =13 Ψ 1 =31 Q 1 =44 φ 2 =28 Ψ 2 =16 Q 2 =44 φ 3 =16 Ψ 3 =16 Q 3 =32 φ 4 =20 Ψ 4 =16 Q 4 =36 φ 5 =19 Ψ 5 =17 Q 5 =36 Q 3 – медиана.