Презентация Задача о минимальном разрезе на взвешенном бисвязном графе онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Задача о минимальном разрезе на взвешенном бисвязном графе абсолютно бесплатно. Урок-презентация на эту тему содержит всего 38 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:38 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:315.87 kB
- Просмотров:66
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№1 слайд
Содержание слайда: ЗАДАЧА О МИНИМАЛЬНОМ РАЗРЕЗЕ НА ВЗВЕШЕННОМ БИСВЯЗНОМ ГРАФЕ
Лекция 9
№2 слайд
Содержание слайда: СОДЕРЖАНИЕ
1. Формальная постановка и поиск решения задачи о минимальном разрезе между двумя вершинами на взвешенном орграфе.
2. Текущий контроль умения решать задачи на поиск кратчайших путей, максимальных потоков и минимальных разрезов.
3. Формальные постановки и поиск решений задач о минимальном разрезе и максимальной циркуляцией на взвешенном бисвязном орграфе.
№3 слайд
Содержание слайда: задача о минимальном разрезе между двумя вершинами на взвешенном орграфе
№4 слайд
Содержание слайда: Формальная постановка задачи о минимальном разрезе между вершинами s и t
№5 слайд
Содержание слайда: АЛГОРИТМ ПОИСКА РЕШЕНИЯ ЗАДАЧИ О МИНИМАЛЬНОМ РАЗРЕЗЕ МЕЖДУ ДВУМЯ ВЕРШИНАМИ ПЕРЕБОРОМ
1 Шаг. Выбор ранее не анализировавшегося сочетания дуг. Если такового нет, то перейти к шагу 6.
2 Шаг. Выбранные на предыдущем шаге дуги удаляются из графа G(X,U).
3 Шаг. На полученном графе ищется максимальный поток F из “s” в “t”.
4. Если F=0, то перейти к шагу 5, нет – к шагу 1.
5. Если суммарный вес выделенных дуг Q меньше хранящейся в памяти величины R, то R=Q, перейти к шагу 1, в противном случае сразу перейти к шагу 1.
6. Конец алгоритма. R равно величине минимального разреза.
№6 слайд
Содержание слайда: ПРИМЕР: минимальный разрез для потока из 3-й вершины во 2-ю.
Исходный Таблица перебора Дуги минималь-
граф G(X,U) ного разреза
№7 слайд
Содержание слайда: Решить три задачи самостоятельно
1. Определить 2. Определить 3.Определить
кратчайший максимальный минимальный
путь между поток из задан- разрез между
заданной ной вершины заданной
парой в заданную. парой вершин.
вершин.
№8 слайд
Содержание слайда: ПЕРСОНАЛЬНЫЕ ЗАДАНИЯ 1 - 9
№9 слайд
Содержание слайда: ПЕРСОНАЛЬНЫЕ ЗАДАНИЯ 10 - 18
№10 слайд
Содержание слайда: ПЕРСОНАЛЬНЫЕ ЗАДАНИЯ 19 - 27
№11 слайд
Содержание слайда: Минимальные разрезы в сильносвязных (бисвязных) орграфах
№12 слайд
Содержание слайда: К ИСТОРИИ ВОЗНИКНОВЕНИЯ ПРОБЛЕМЫ
№13 слайд
Содержание слайда: Экономический характер задачи
№14 слайд
Содержание слайда: Содержательная постановка задачи
На взвешенном бисвязном ориентированном графе требуется выделить такое подмножество дуг, для которого справедливо:
1. Удаление дуг выделенного подмножества разрывает на графе все контуры.
2. Суммарный вес дуг выделенного подмножества минимален.
№15 слайд
Содержание слайда: Графовая интерпретация задачи о минимальном разрезе в бисвязном графе
№16 слайд
Содержание слайда: Обозначения и определения
№17 слайд
Содержание слайда: Формальная постановка задачи о минимальном разрезе в бисвязном взвешенном графе
№18 слайд
Содержание слайда: ПРИМЕР 1: постановка задачи
№19 слайд
Содержание слайда: Журнал “IEEE transactions on circuit theory”
№20 слайд
Содержание слайда: Пример применения Метода Лемпела и седербаума
№21 слайд
Содержание слайда: Проверка графа на наличие контуров
№22 слайд
Содержание слайда: РЕШЕНИЕ ЗАДАЧИ ПРИМЕРА 1 ПЕРЕБОРОМ
№23 слайд
Содержание слайда: АЛГОРИТМ РАБОТЫ ГЕНЕРАТОРА сочетаний значений булевых переменных
№24 слайд
Содержание слайда: ДОСТОИНСТВА И НЕДОСТАТКИ АЛГОРИТМА ГЕНЕРАЦИИ всех сочетаний значений вектора булевых переменных
Достоинства:
Генерация всех сочетаний значений булевых переменных гарантирует глобальный оптимум.
Простота алгоритма.
Легкость программной реализации.
Низкие требования к объему памяти компьютера
Легкость распараллеливания алгоритма.
Недостатки:
В ходе работы алгоритма генерируется более
сочетаний различных чисел:
алгоритм избыточен.
№25 слайд
Содержание слайда: САМОСТОЯТЕЛЬНО:
Решить задачу о минимальном разрезе в бисвязном взвешенном орграфе, пользуясь графом персонального задания и приведенным выше алгоритмом.
Составить блок-схему алгоритма поиска минимального разреза на бисвязном графе, включающую генератор перестановок.
Программно реализовать построенный алгоритм.
Построить график зависимости времени счета T от размерности задачи n.
Пользуясь методом наименьших квадратов найти аналитические зависимости T(n).
№26 слайд
Содержание слайда: Задача о максимальной циркуляции - пример
№27 слайд
Содержание слайда: Задача о максимальной циркуляции в бисвязном графе - обозначения
S(i,j) – поток по дуге (i,j) на графе G(X,U);
r(i,j) – пропускная способность дуги (i,j);
A(G) – множество контуров графа G(X,U);
U(ak) – подмножество дуг k-го контура;
S(ak) – циркуляция в k-м контуре;
A(i,j) – подмножество контуров, в состав которых входит дуга (i,j).
№28 слайд
Содержание слайда: Формальная постановка задачи поиска максимальной циркуляции в бисвязном графе
№29 слайд
Содержание слайда: Теорема 1 в.н. буркова
Величина максимальной циркуляции на взвешенном бисвязном орграфе не превышает величины минимального разреза.
№30 слайд
Содержание слайда: пример
Smax=1,5;
Rmin = 2. 1
1
1
1 1
1 1
1 1 1 1
№31 слайд
Содержание слайда: Теорема 2 в.н. буркова
На планарных ориентированных взвешенных сильносвязных графах величина максимальной циркуляции всегда целочислена и равна величине минимального разреза.
№32 слайд
Содержание слайда: самостоятельно
Пользуясь теоремой 2 В.Н. Буркова определить величину минимального разреза на планарном графе G(X,U):
1
1 1 1 1 1
1
1 1
№33 слайд
Содержание слайда: Теорема Буркова № 3
Любой перестановке вершин бисвязного орграфа π={i1, i2, i3, ….in} отвечает разрез, состоящий из дуг, идущих из вершин стоящих слева в перестановке π, в вершины, стоящие в ней справа.
№34 слайд
Содержание слайда: ПРИМЕР
№35 слайд
Содержание слайда: Лемма
Любому разрезу в сильносвязном орграфе G(X,U) отвечает «своя» перестановка вершин π множества Х.
№36 слайд
Содержание слайда: МЕТОД ТИПА ВЕТВЕЙ И ГРАНИЦ С ФРОНТАЛЬНЫМ СПУСКОМ И ВЕТВЛЕНИЕМ ПО ВЕРШИНАМ
G(X,U) Дерево ветвлений
№37 слайд
Содержание слайда: САМОСТОЯТЕЛЬНО
Решить задачу о минимальном разрезе на взвешенном орграфе G(X,U), заданном матрицей M описанным выше методом:
№38 слайд
Содержание слайда: САМОСТОЯТЕЛЬНО
Сравнить эффективность ветвления по дугам с ветвлением по вершинам при решении задачи о минимальном разрезе методами типа ветвей и границ.
Решить задачу о минимальном разрезе в бисвязном взвешенном орграфе, пользуясь графом персонального задания и приведенным выше алгоритмом.
Скачать все slide презентации Задача о минимальном разрезе на взвешенном бисвязном графе одним архивом:
