Алгоритм Флойда-Уоршалла - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Алгоритм Флойда-Уоршалла. Доклад-сообщение содержит 17 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

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

Слайд 2

Описание слайда:

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

Слайд 3

Описание слайда:

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

Слайд 4

Описание слайда:

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

Слайд 5

Описание слайда:

v1 v2 v3 v1 v2 v3

Слайд 6

Описание слайда:

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

Слайд 7

Описание слайда:

Слайд 8

Описание слайда:

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

Слайд 9

Описание слайда:

Слайд 10

Описание слайда:

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

Слайд 11

Описание слайда:

Слайд 12

Описание слайда:

Слайд 13

Описание слайда:

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

Слайд 14

Описание слайда:

Слайд 15

Описание слайда:

4*3*2*2=48

Слайд 16

Описание слайда:

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

Слайд 17

Описание слайда:

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