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

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

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

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

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

5 v 1 v 2 v 3

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

7

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

9

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

11

12

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

14 a d f b c e

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

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

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