Алгоритм Флойда-Уоршалла Находит кратчайшие расстояния между всеми парами вершин графа Идея: Строится специальная матрица D, элементы которой – кратчайшие.

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



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

Алгоритмы на графах Волновой метод. Постановка задачи Постановка задачи. Пусть G – неориентированный связный граф, а и b – две его вершины. Требуется.
Теория графов Алгоритмы на графах. Медиана графа Медиана вершина графа, у которой сумма кратчайших расстояний от неё до вершин графа минимальная возможная.
Графы Лекция 2. Графы Неориентированным графом (графом) называется тройка (V, E, ), где V и E конечные множества и {X V : | X | = 2}. Ориентированным.
Графы Волновой метод. Задание графов Пусть граф задан графически. Составить матрицу смежности и матрицу инцидентности для этого графа
Теория графов Основные определения. Задание графов Графический способ – Привести пример графического задания графа, состоящего из вершин А, В и С, связанных.
1 Комбинаторные алгоритмы Задача о k-центрах. 2 Метрическая задача o k центрах Дано: Полный граф G = (V, E), стоимости ребер cost: E Q + такие, что для.
Раскраски графов Раскраска вершин Пусть Г (V,E,Ф) – граф, раскраска вершин Г в n цветов – отображение f : V {1,2,…,n } Правильная раскраска вершин графа.
Комбинаторные алгоритмы Задача о покрытии. Задача о покрытии множествами Дано: Совокупность U из n элементов, и набор подмножеств U, S = {S 1,…, S k },
Теория графов Основные определения. Дуга Пусть имеется множество вершин V={V 1,V 2,…,V n } и пусть на нем задано бинарное отношение Г V×V, – V i Г V j.
Построим четыре произвольные точки : А.. В.С.С.D.D А,А,В,В,С,D (чтобы никакие три из них не лежали на одной прямой). Проведем отрезки:АВ,ВС,CD,DA - последовательно.
Остовные деревья Лекция 4. Задача «Минимальное остовное дерево» Дано: Граф G, веса c: E(G) R. Найти остовное дерево в G наименьшего веса или определить,
Алгоритм Катхилла-Макки. 2 Основные определения Граф можно представить себе состоящим из конечного множества узлов, или вершин, вместе с множеством ребер,
Алгоритм Эдмондса Лекция 11. Идея алгоритма Эдмондса Пусть есть некоторое паросочетание M, построим M-чередующийся лес F. Начинаем с множества S вершин.
Сетевое планирование. Теория графов. Граф Граф это совокупность непустого множества вершин и множества пар вершин. Граф это совокупность непустого множества.
Графы. Деревья Продолжение А.Г.Баханский © Программирование – вторая грамотность. А.П.Ершов Граф (Л.Н.Толстой) Граф (не ориентированный) Граф (ориентированный)
Свойства пределов. 1. Ограниченность функции, имеющей предел. –Определение. –Функция называется ограниченной на множестве D, если –Теорема. Пример. Функция.
1 Приближенные алгоритмы Комбинаторные алгоритмы.
Лекция 9 Отношения, графы Определения. Определение. Пусть а и b объекты. Через (а, b) обозначим упорядоченную пару, состоящую из объектов а и b, взятых.
Алгоритмы на графах. Задача о максимальном потоке в сетях Требуется от источника к стоку передать максимальное количество энергии. В условиях задачи о.
Транксрипт:

Алгоритм Флойда-Уоршалла Находит кратчайшие расстояния между всеми парами вершин графа Идея: Строится специальная матрица D, элементы которой – кратчайшие пути между всевозможными парами вершин графа G. При определении кратчайшего пути выбирается минимум из «прямого» расстояния между смежными вершинами v i и v j и суммарного расстояния при проходе через дополнительную вершину. Затем – более длинные пути и т.д.

Обозначим через длину кратчайшего пути из v i в v j с промежуточными вершинами во множестве {v 1,…,v m }. Алгоритм использует три правила: 1) - вес дуги, соединяющей вершины v i и v j (т.е. первоначально матрица D – это исходная матрица весов).

2) 3) Длина кратчайшего пути из вершины v i в вершину v j : Алгоритм строит матрицу за n шагов, т.е. строится матрица D (1), …, D (n) =D.

Пример. Найдем матрицу кратчайших расстояний для графа. v1v1 5 v2v2 v3v

v 1 v 2 v 3

Элементы матрицы D (1) находим по правилу:

Элементы матрицы D (2) находим по правилу:

Элементы матрицы D (3) находим по правилу:

3.6.7 Раскраска графов А С В D F E

a d f b c e

4*3*2*2=48 b c a d

Раскраской графа G называется окрашивание вершин графа G, такое, что никакие две смежные вершины не окрашены в один цвет. Пусть С G ( ) обозначает количество способов раскраски графа G с использованием цветов, так, что никакие две соседние вершины не окрашены в разные цвета. Для фиксированного графа G это полиномиальная функция от.

Само при этом называется хроматическим числом. Хроматическое число графа – это наименьшее положительное число n, такое что С G (n) 0. Проблема четырёх красок эквивалентна утверждению, что С G (4) 0 для произвольного графа.