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

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

Задача о минимальном разрезе на взвешенном бисвязном графе, слайд №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

Слайд 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

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

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