Презентация Кратчайшие пути, максимальные потоки и минимальные разрезы на орграфах онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Кратчайшие пути, максимальные потоки и минимальные разрезы на орграфах абсолютно бесплатно. Урок-презентация на эту тему содержит всего 22 слайда. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:22 слайда
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:233.54 kB
- Просмотров:77
- Скачиваний:1
- Автор:неизвестен
Слайды и текст к этой презентации:
№1 слайд
Содержание слайда: Кратчайшие пути, максимальные потоки и минимальные разрезы на орграфах
Лекция 7
№2 слайд
Содержание слайда: СОДЕРЖАТЕЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ О КРАТЧАЙШЕМ ПУТИ
На взвешенном ориентированном графе G(X,U) требуется определить кратчайший путь из i-й вершины в j-ю.
№3 слайд
Содержание слайда: ФОРМАЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ О КРАТЧАЙШЕМ ПУТИ
№4 слайд
Содержание слайда: МЕТОД ПОТЕНЦИАЛОВ
Шаг 1. Вершине присваивается потенциал P(s)=0.
Шаг 2. Всем вершинам множества Х\ присвоить
потенциал, равный ∞.
Шаг 3. Каждой q-й вершине множества Х\
присваивается потенциал P(q):
Шаг 4. Если потенциал хотя бы одной вершины
изменился, то перейти к шагу 3, в противном
случае – к шагу 5.
Шаг 5. Конец алгоритма. Потенциал t-й вершины равен
кратчайшему пути в нее из вершины .
№5 слайд
Содержание слайда: ПРИМЕР 1
Поиск длины кратчайшего пути из 1-й вершины в 4-ю.
№6 слайд
Содержание слайда: ДОСТОИНСТВА И НЕДОСТАТКИ
Достоинства:
Метод потенциалов гарантирует определение кратчайших путей из выбранной вершины во все остальные.
Исключается необходимость перебора всех путей.
Высокое быстродействие.
Легкая программная реализация.
Универсальность: метод применим к ориентированным и неориентированным графам.
Недостатки:
Вес каждой дуги должен быть положительным.
№7 слайд
Содержание слайда: РЕШИТЬ САМОСТОЯТЕЛЬНО
Определить кратчайшие пути из 1-й вершины во все остальные.
№8 слайд
Содержание слайда: МАКСИМАЛЬНЫЕ ПОТОКИ НА ГРАФАХ
Содержательная постановка задачи: требуется определить максимальный однородный поток на графе G(X,U) из вершины s в вершину t, если поток по каждой дуге графа (i,j) не может превышать ее пропускной способности r(i,j)
№9 слайд
Содержание слайда: Формальная постановка задачи о максимальном однородном потоке
Обозначения: f(i,j) – поток по дуге ,
r(i,j) – пропускная способность дуги ;
- вершина – источник;
- вершина – сток.
№10 слайд
Содержание слайда: САМОСТОЯТЕЛЬНО
Дайте иную формальную постановку задачи о максимальном потоке, в которой:
эмиссионная способность источника ограничена;
поглощающая способность стока ограничена;
на графе имеется несколько источников и стоков.
№11 слайд
Содержание слайда: ЧАСТО ИСПОЛЬЗУЕМЫЙ АЛГОРИТМ ПОИСКА МАКСИМАЛЬНОГО ПОТОКА
Шаг 1. Полученный граф G(X,U’) заменяется на G’(X,U’) такой, что:
Шаг 2. Методом потенциалов ищется кратчайший путь L из
Шаг 3. Если длина такого пути равна ∞, то перейти к шагу 9, в противном случае – к шагу 4.
Шаг 4. На графе G(X,U) выбирается дуга (p,q), принадлежащая L, для которой справедливо:
№12 слайд
Содержание слайда: АЛГОРИТМ ПОИСКА МАКСИМАЛЬНОГО ПОТОКА (ПРОДОЛЖЕНИЕ)
Шаг 5. На графе G(X,U) вес всех дуг, принадлежавших пути L, изменяется следующим образом:
Шаг 6. Образовавшиеся дуги с нулевым весом
на G(X,U) отбрасываются.
Шаг 7. Вес r(p,q) добавить к ранее накопленной сумме S.
Шаг 8. Перейти к шагу 1.
Шаг 9. Конец алгоритма. Суммарный вес дуг, найденных на шаге 4 каждой итерации, равен максимальному потоку из источника в сток.
№13 слайд
Содержание слайда: ПРИМЕР 2
a) Граф G(X,U). b) Граф G’(X,U’), S=4. a) b) S=5. c) L=∞.
№14 слайд
Содержание слайда: САМОСТОЯТЕЛЬНО
Сформулируйте достоинства приведенного выше алгоритма.
Сформулируйте недостатки приведенного выше алгоритма.
№15 слайд
Содержание слайда: Пример 3
№16 слайд
Содержание слайда: САМОСТОЯТЕЛЬНО
1. Сформулировать достоинства и недостатки алгоритма поиска максимального потока.
2. Определить максимальный поток из источника в сток на графе G(X,U):
№17 слайд
Содержание слайда: МИНИМАЛЬНЫЕ РАЗРЕЗЫ НА ГРАФАХ
Определения:
1. Разрезом на ориентированном графе G(X, U) называется подмножество дуг, удаление которых разрывает все пути из источника в сток.
2. Минимальным разрезом на взвешенном ориентированном графе G(X, U) называется разрез, суммарный вес дуг которого минимален.
Варианты разрезов вверху выделены красным цветом
№18 слайд
Содержание слайда: Обозначения и определения
Z(i,j) – булева переменная, равная единице, если дуга (i,j) принадлежит минимальному разрезу и равная нулю в противном случае.
- множество дуг, принадлежащих d-у пути, ведущему из вершины-источника в вершину-сток .
№19 слайд
Содержание слайда: Формальная постановка задачи о минимальном разрезе
№20 слайд
Содержание слайда: Поиск минимального разреза перебором
Граф G(X,U)
№21 слайд
Содержание слайда: ТЕОРЕМА ФОРДА-ФАЛКЕРСОНА
Величина минимального разреза на взвешенном ориентированном графе равна величине максимального потока.
№22 слайд
Содержание слайда: САМОСТОЯТЕЛЬНО
Пользуясь теоремой Форда-Фалкерсона определить величину минимального разреза на графе G(X,U):
Скачать все slide презентации Кратчайшие пути, максимальные потоки и минимальные разрезы на орграфах одним архивом:
