Алгоритм Флойда-Уоршалла

Сентябрь 2, 2022

Главная
Алгебра
Алгоритм Флойда-Уоршалла

Содержание

2. Обозначим через длину кратчайшего пути из vi в vj с промежуточными вершинами во множестве {v1,…,vm}. Алгоритм
3. 2) 3) Длина кратчайшего пути из вершины vi в вершину vj: Алгоритм строит матрицу за n
4. Пример. Найдем матрицу кратчайших расстояний для графа. v1 5
5. v1 v2 v3
6. Элементы матрицы D(1) находим по правилу:
8. Элементы матрицы D(2) находим по правилу:
10. Элементы матрицы D(3) находим по правилу:
13. 3.6.7 Раскраска графов
15. 4*3*2*2=48
16. Раскраской графа G называется окрашивание вершин графа G, такое, что никакие две смежные вершины не окрашены
18. Скачать презентацию

Слайд 2

Обозначим через длину кратчайшего
пути из vi в vj с промежуточными

вершинами во множестве {v1,…,vm}.
Алгоритм использует три правила:
1)
- вес дуги, соединяющей вершины vi и vj (т.е. первоначально матрица D – это исходная матрица весов).

Слайд 3

2)
3) Длина кратчайшего пути из вершины vi в вершину vj:
Алгоритм

строит матрицу за n шагов, т.е. строится матрица D(1) , …, D(n) =D.

Слайд 4

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

Слайд 5

v1 v2 v3

Слайд 6

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

Слайд 7

Слайд 8

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

Слайд 9

Слайд 10

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

Слайд 11

Слайд 12

Слайд 13

3.6.7 Раскраска графов

Слайд 14

Слайд 15

432*2=48

Слайд 16

Раскраской графа G называется
окрашивание вершин графа G, такое, что
никакие две смежные

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