🗊Презентация Задача о минимальном разрезе на взвешенном бисвязном графе

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Задача о минимальном разрезе на взвешенном бисвязном графе, слайд №1Задача о минимальном разрезе на взвешенном бисвязном графе, слайд №2Задача о минимальном разрезе на взвешенном бисвязном графе, слайд №3Задача о минимальном разрезе на взвешенном бисвязном графе, слайд №4Задача о минимальном разрезе на взвешенном бисвязном графе, слайд №5Задача о минимальном разрезе на взвешенном бисвязном графе, слайд №6Задача о минимальном разрезе на взвешенном бисвязном графе, слайд №7Задача о минимальном разрезе на взвешенном бисвязном графе, слайд №8Задача о минимальном разрезе на взвешенном бисвязном графе, слайд №9Задача о минимальном разрезе на взвешенном бисвязном графе, слайд №10Задача о минимальном разрезе на взвешенном бисвязном графе, слайд №11Задача о минимальном разрезе на взвешенном бисвязном графе, слайд №12Задача о минимальном разрезе на взвешенном бисвязном графе, слайд №13Задача о минимальном разрезе на взвешенном бисвязном графе, слайд №14Задача о минимальном разрезе на взвешенном бисвязном графе, слайд №15Задача о минимальном разрезе на взвешенном бисвязном графе, слайд №16Задача о минимальном разрезе на взвешенном бисвязном графе, слайд №17Задача о минимальном разрезе на взвешенном бисвязном графе, слайд №18Задача о минимальном разрезе на взвешенном бисвязном графе, слайд №19Задача о минимальном разрезе на взвешенном бисвязном графе, слайд №20Задача о минимальном разрезе на взвешенном бисвязном графе, слайд №21Задача о минимальном разрезе на взвешенном бисвязном графе, слайд №22Задача о минимальном разрезе на взвешенном бисвязном графе, слайд №23Задача о минимальном разрезе на взвешенном бисвязном графе, слайд №24Задача о минимальном разрезе на взвешенном бисвязном графе, слайд №25Задача о минимальном разрезе на взвешенном бисвязном графе, слайд №26Задача о минимальном разрезе на взвешенном бисвязном графе, слайд №27Задача о минимальном разрезе на взвешенном бисвязном графе, слайд №28Задача о минимальном разрезе на взвешенном бисвязном графе, слайд №29Задача о минимальном разрезе на взвешенном бисвязном графе, слайд №30Задача о минимальном разрезе на взвешенном бисвязном графе, слайд №31Задача о минимальном разрезе на взвешенном бисвязном графе, слайд №32Задача о минимальном разрезе на взвешенном бисвязном графе, слайд №33Задача о минимальном разрезе на взвешенном бисвязном графе, слайд №34Задача о минимальном разрезе на взвешенном бисвязном графе, слайд №35Задача о минимальном разрезе на взвешенном бисвязном графе, слайд №36Задача о минимальном разрезе на взвешенном бисвязном графе, слайд №37Задача о минимальном разрезе на взвешенном бисвязном графе, слайд №38
Скачать

Содержание ▲

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

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

Слайд 1


ЗАДАЧА О МИНИМАЛЬНОМ РАЗРЕЗЕ НА ВЗВЕШЕННОМ БИСВЯЗНОМ ГРАФЕ Лекция 9
Описание слайда:
ЗАДАЧА О МИНИМАЛЬНОМ РАЗРЕЗЕ НА ВЗВЕШЕННОМ БИСВЯЗНОМ ГРАФЕ Лекция 9

Слайд 2


СОДЕРЖАНИЕ 1. Формальная постановка и поиск решения задачи о минимальном разрезе между двумя вершинами на взвешенном орграфе. 2. Текущий контроль умения решать задачи на поиск кратчайших путей, максимальных потоков и минимальных разрезов. 3. Формальные постановки и поиск решений задач о минимальном разрезе и максимальной циркуляцией на взвешенном бисвязном орграфе.
Описание слайда:
СОДЕРЖАНИЕ 1. Формальная постановка и поиск решения задачи о минимальном разрезе между двумя вершинами на взвешенном орграфе. 2. Текущий контроль умения решать задачи на поиск кратчайших путей, максимальных потоков и минимальных разрезов. 3. Формальные постановки и поиск решений задач о минимальном разрезе и максимальной циркуляцией на взвешенном бисвязном орграфе.

Слайд 3


задача о минимальном разрезе между двумя вершинами на взвешенном орграфе
Описание слайда:
задача о минимальном разрезе между двумя вершинами на взвешенном орграфе

Слайд 4


Формальная постановка задачи о минимальном разрезе между вершинами s и t
Описание слайда:
Формальная постановка задачи о минимальном разрезе между вершинами 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 равно величине минимального разреза.
Описание слайда:
АЛГОРИТМ ПОИСКА РЕШЕНИЯ ЗАДАЧИ О МИНИМАЛЬНОМ РАЗРЕЗЕ МЕЖДУ ДВУМЯ ВЕРШИНАМИ ПЕРЕБОРОМ 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) ного разреза
Описание слайда:
ПРИМЕР: минимальный разрез для потока из 3-й вершины во 2-ю. Исходный Таблица перебора Дуги минималь- граф G(X,U) ного разреза

Слайд 7


Решить три задачи самостоятельно 1. Определить 2. Определить 3.Определить кратчайший максимальный минимальный путь между поток из задан- разрез между заданной ной вершины заданной парой в заданную. парой вершин. вершин.
Описание слайда:
Решить три задачи самостоятельно 1. Определить 2. Определить 3.Определить кратчайший максимальный минимальный путь между поток из задан- разрез между заданной ной вершины заданной парой в заданную. парой вершин. вершин.

Слайд 8


ПЕРСОНАЛЬНЫЕ ЗАДАНИЯ 1 - 9
Описание слайда:
ПЕРСОНАЛЬНЫЕ ЗАДАНИЯ 1 - 9

Слайд 9


ПЕРСОНАЛЬНЫЕ ЗАДАНИЯ 10 - 18
Описание слайда:
ПЕРСОНАЛЬНЫЕ ЗАДАНИЯ 10 - 18

Слайд 10


ПЕРСОНАЛЬНЫЕ ЗАДАНИЯ 19 - 27
Описание слайда:
ПЕРСОНАЛЬНЫЕ ЗАДАНИЯ 19 - 27

Слайд 11


Минимальные разрезы в сильносвязных (бисвязных) орграфах
Описание слайда:
Минимальные разрезы в сильносвязных (бисвязных) орграфах

Слайд 12


К ИСТОРИИ ВОЗНИКНОВЕНИЯ ПРОБЛЕМЫ
Описание слайда:
К ИСТОРИИ ВОЗНИКНОВЕНИЯ ПРОБЛЕМЫ

Слайд 13


Экономический характер задачи
Описание слайда:
Экономический характер задачи

Слайд 14


Содержательная постановка задачи На взвешенном бисвязном ориентированном графе требуется выделить такое подмножество дуг, для которого справедливо: 1. Удаление дуг выделенного подмножества разрывает на графе все контуры. 2. Суммарный вес дуг выделенного подмножества минимален.
Описание слайда:
Содержательная постановка задачи На взвешенном бисвязном ориентированном графе требуется выделить такое подмножество дуг, для которого справедливо: 1. Удаление дуг выделенного подмножества разрывает на графе все контуры. 2. Суммарный вес дуг выделенного подмножества минимален.

Слайд 15


Графовая интерпретация задачи о минимальном разрезе в бисвязном графе
Описание слайда:
Графовая интерпретация задачи о минимальном разрезе в бисвязном графе

Слайд 16


Обозначения и определения
Описание слайда:
Обозначения и определения

Слайд 17


Формальная постановка задачи о минимальном разрезе в бисвязном взвешенном графе
Описание слайда:
Формальная постановка задачи о минимальном разрезе в бисвязном взвешенном графе

Слайд 18


ПРИМЕР 1: постановка задачи
Описание слайда:
ПРИМЕР 1: постановка задачи

Слайд 19


Журнал “IEEE transactions on circuit theory”
Описание слайда:
Журнал “IEEE transactions on circuit theory”

Слайд 20


Пример применения Метода Лемпела и седербаума
Описание слайда:
Пример применения Метода Лемпела и седербаума

Слайд 21


Проверка графа на наличие контуров
Описание слайда:
Проверка графа на наличие контуров

Слайд 22


РЕШЕНИЕ ЗАДАЧИ ПРИМЕРА 1 ПЕРЕБОРОМ
Описание слайда:
РЕШЕНИЕ ЗАДАЧИ ПРИМЕРА 1 ПЕРЕБОРОМ

Слайд 23


АЛГОРИТМ РАБОТЫ ГЕНЕРАТОРА сочетаний значений булевых переменных
Описание слайда:
АЛГОРИТМ РАБОТЫ ГЕНЕРАТОРА сочетаний значений булевых переменных

Слайд 24


ДОСТОИНСТВА И НЕДОСТАТКИ АЛГОРИТМА ГЕНЕРАЦИИ всех сочетаний значений вектора булевых переменных Достоинства: Генерация всех сочетаний значений булевых переменных гарантирует глобальный оптимум. Простота алгоритма. Легкость программной реализации. Низкие требования к объему памяти компьютера Легкость распараллеливания алгоритма. Недостатки: В ходе работы алгоритма генерируется более сочетаний различных чисел: алгоритм избыточен.
Описание слайда:
ДОСТОИНСТВА И НЕДОСТАТКИ АЛГОРИТМА ГЕНЕРАЦИИ всех сочетаний значений вектора булевых переменных Достоинства: Генерация всех сочетаний значений булевых переменных гарантирует глобальный оптимум. Простота алгоритма. Легкость программной реализации. Низкие требования к объему памяти компьютера Легкость распараллеливания алгоритма. Недостатки: В ходе работы алгоритма генерируется более сочетаний различных чисел: алгоритм избыточен.

Слайд 25


САМОСТОЯТЕЛЬНО: Решить задачу о минимальном разрезе в бисвязном взвешенном орграфе, пользуясь графом персонального задания и приведенным выше алгоритмом. Составить блок-схему алгоритма поиска минимального разреза на бисвязном графе, включающую генератор перестановок. Программно реализовать построенный алгоритм. Построить график зависимости времени счета T от размерности задачи n. Пользуясь методом наименьших квадратов найти аналитические зависимости T(n).
Описание слайда:
САМОСТОЯТЕЛЬНО: Решить задачу о минимальном разрезе в бисвязном взвешенном орграфе, пользуясь графом персонального задания и приведенным выше алгоритмом. Составить блок-схему алгоритма поиска минимального разреза на бисвязном графе, включающую генератор перестановок. Программно реализовать построенный алгоритм. Построить график зависимости времени счета 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).
Описание слайда:
Задача о максимальной циркуляции в бисвязном графе - обозначения 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 в.н. буркова Величина максимальной циркуляции на взвешенном бисвязном орграфе не превышает величины минимального разреза.
Описание слайда:
Теорема 1 в.н. буркова Величина максимальной циркуляции на взвешенном бисвязном орграфе не превышает величины минимального разреза.

Слайд 30


пример Smax=1,5; Rmin = 2. 1 1 1 1 1 1 1 1 1 1 1
Описание слайда:
пример Smax=1,5; Rmin = 2. 1 1 1 1 1 1 1 1 1 1 1

Слайд 31


Теорема 2 в.н. буркова На планарных ориентированных взвешенных сильносвязных графах величина максимальной циркуляции всегда целочислена и равна величине минимального разреза.
Описание слайда:
Теорема 2 в.н. буркова На планарных ориентированных взвешенных сильносвязных графах величина максимальной циркуляции всегда целочислена и равна величине минимального разреза.

Слайд 32


самостоятельно Пользуясь теоремой 2 В.Н. Буркова определить величину минимального разреза на планарном графе G(X,U): 1 1 1 1 1 1 1 1 1
Описание слайда:
самостоятельно Пользуясь теоремой 2 В.Н. Буркова определить величину минимального разреза на планарном графе G(X,U): 1 1 1 1 1 1 1 1 1

Слайд 33


Теорема Буркова № 3 Любой перестановке вершин бисвязного орграфа π={i1, i2, i3, ….in} отвечает разрез, состоящий из дуг, идущих из вершин стоящих слева в перестановке π, в вершины, стоящие в ней справа.
Описание слайда:
Теорема Буркова № 3 Любой перестановке вершин бисвязного орграфа π={i1, i2, i3, ….in} отвечает разрез, состоящий из дуг, идущих из вершин стоящих слева в перестановке π, в вершины, стоящие в ней справа.

Слайд 34


ПРИМЕР
Описание слайда:
ПРИМЕР

Слайд 35


Лемма Любому разрезу в сильносвязном орграфе G(X,U) отвечает «своя» перестановка вершин π множества Х.
Описание слайда:
Лемма Любому разрезу в сильносвязном орграфе G(X,U) отвечает «своя» перестановка вершин π множества Х.

Слайд 36


МЕТОД ТИПА ВЕТВЕЙ И ГРАНИЦ С ФРОНТАЛЬНЫМ СПУСКОМ И ВЕТВЛЕНИЕМ ПО ВЕРШИНАМ G(X,U) Дерево ветвлений
Описание слайда:
МЕТОД ТИПА ВЕТВЕЙ И ГРАНИЦ С ФРОНТАЛЬНЫМ СПУСКОМ И ВЕТВЛЕНИЕМ ПО ВЕРШИНАМ G(X,U) Дерево ветвлений

Слайд 37


САМОСТОЯТЕЛЬНО Решить задачу о минимальном разрезе на взвешенном орграфе G(X,U), заданном матрицей M описанным выше методом:
Описание слайда:
САМОСТОЯТЕЛЬНО Решить задачу о минимальном разрезе на взвешенном орграфе G(X,U), заданном матрицей M описанным выше методом:

Слайд 38


САМОСТОЯТЕЛЬНО Сравнить эффективность ветвления по дугам с ветвлением по вершинам при решении задачи о минимальном разрезе методами типа ветвей и границ. Решить задачу о минимальном разрезе в бисвязном взвешенном орграфе, пользуясь графом персонального задания и приведенным выше алгоритмом.
Описание слайда:
САМОСТОЯТЕЛЬНО Сравнить эффективность ветвления по дугам с ветвлением по вершинам при решении задачи о минимальном разрезе методами типа ветвей и границ. Решить задачу о минимальном разрезе в бисвязном взвешенном орграфе, пользуясь графом персонального задания и приведенным выше алгоритмом.

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию