Разделы презентаций


Графы.ppt

Обозначим через длину кратчайшего пути из vi в vj с промежуточными вершинами во множестве {v1,…,vm}. Алгоритм использует три правила:1)

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

Слайд 1Алгоритм Флойда-Уоршалла
Находит кратчайшие расстояния между всеми парами вершин графа
Идея:

Строится специальная матрица D, элементы которой – кратчайшие пути между

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

Слайд 2Обозначим через

длину кратчайшего

пути из vi в vj с промежуточными вершинами

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





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

Слайд 32)


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




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

, …, D(n) =D.




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

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


v1
5

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

Слайд 5 v1

v2 v3

v1   v2  v3

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










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

Слайд 8





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


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

Слайд 10




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


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

Слайд 133.6.7 Раскраска графов

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

Слайд 15








4*3*2*2=48

4*3*2*2=48

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

смежные вершины не окрашены
в один цвет.
Пусть СG(λ) обозначает количество

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

Слайд 17Само λ при этом называется хроматическим числом.
Хроматическое число графа

– это наименьшее положительное число n, такое что СG(n)≠0.
Проблема четырёх

красок эквивалентна утверждению, что СG(4)≠0 для произвольного графа.

Само λ при этом называется хроматическим числом. Хроматическое число графа – это наименьшее положительное число n, такое

Обратная связь

Если не удалось найти и скачать доклад-презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:

Email: Нажмите что бы посмотреть 

Что такое TheSlide.ru?

Это сайт презентации, докладов, проектов в PowerPoint. Здесь удобно  хранить и делиться своими презентациями с другими пользователями.


Для правообладателей

Яндекс.Метрика