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

Содержание

Слайд 2

СОДЕРЖАНИЕ 1. Формальная постановка и поиск решения задачи о минимальном разрезе

СОДЕРЖАНИЕ

1. Формальная постановка и поиск решения задачи о минимальном разрезе между

двумя вершинами на взвешенном орграфе.
2. Текущий контроль умения решать задачи на поиск кратчайших путей, максимальных потоков и минимальных разрезов.
3. Формальные постановки и поиск решений задач о минимальном разрезе и максимальной циркуляцией на взвешенном бисвязном орграфе.
Слайд 3

ЗАДАЧА О МИНИМАЛЬНОМ РАЗРЕЗЕ МЕЖДУ ДВУМЯ ВЕРШИНАМИ НА ВЗВЕШЕННОМ ОРГРАФЕ Часть 1

ЗАДАЧА О МИНИМАЛЬНОМ РАЗРЕЗЕ МЕЖДУ ДВУМЯ ВЕРШИНАМИ НА ВЗВЕШЕННОМ ОРГРАФЕ

Часть 1

Слайд 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 равно величине минимального разреза.
Слайд 6

ПРИМЕР: МИНИМАЛЬНЫЙ РАЗРЕЗ ДЛЯ ПОТОКА ИЗ 3-Й ВЕРШИНЫ ВО 2-Ю. Исходный

ПРИМЕР: МИНИМАЛЬНЫЙ РАЗРЕЗ ДЛЯ ПОТОКА ИЗ 3-Й ВЕРШИНЫ ВО 2-Ю.

Исходный

Таблица перебора Дуги минималь-
граф G(X,U) ного разреза

1

2

3

2

3

1

2
5
7
1
2 5
7
1

Слайд 7

РЕШИТЬ ТРИ ЗАДАЧИ САМОСТОЯТЕЛЬНО 1. Определить 2. Определить 3.Определить кратчайший максимальный

РЕШИТЬ ТРИ ЗАДАЧИ САМОСТОЯТЕЛЬНО

1. Определить 2. Определить 3.Определить
кратчайший максимальный

минимальный
путь между поток из задан- разрез между
заданной ной вершины заданной
парой в заданную. парой вершин.
вершин.

Часть 2

Слайд 8

ПЕРСОНАЛЬНЫЕ ЗАДАНИЯ 1 - 9

ПЕРСОНАЛЬНЫЕ ЗАДАНИЯ 1 - 9

Слайд 9

ПЕРСОНАЛЬНЫЕ ЗАДАНИЯ 10 - 18

ПЕРСОНАЛЬНЫЕ ЗАДАНИЯ 10 - 18

Слайд 10

ПЕРСОНАЛЬНЫЕ ЗАДАНИЯ 19 - 27

ПЕРСОНАЛЬНЫЕ ЗАДАНИЯ 19 - 27

Слайд 11

Минимальные разрезы в сильносвязных (бисвязных) орграфах Часть 3.


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

Часть 3.

Слайд 12

К ИСТОРИИ ВОЗНИКНОВЕНИЯ ПРОБЛЕМЫ В середине прошлого века развилась полупроводниковая электроника,

К ИСТОРИИ ВОЗНИКНОВЕНИЯ ПРОБЛЕМЫ

В середине прошлого века развилась полупроводниковая электроника, разброс

параметров которой вызвал резкое усложнение радиосхем и широкое применение контуров обратной связи.

Блок № 1

Блок № 2

Блок № n-1

Блок № n

Слайд 13

ЭКОНОМИЧЕСКИЙ ХАРАКТЕР ЗАДАЧИ Отладка блоков электронных схем осуществляется в порядке, позволяющем

ЭКОНОМИЧЕСКИЙ ХАРАКТЕР ЗАДАЧИ

Отладка блоков электронных схем осуществляется в порядке, позволяющем использовать

уже проверенные и исправные блоки при тестировании еще непроверенных. При этом сигналы, поступающие по контурам обратной связи от еще непроверенных блоков, генерируются специальной аппаратурой. Если известна стоимость дополнительной аппаратуры, генерирующей разного рода сигналы, то естественна постановка задачи, в которой требуется такая организация тестирования и отладки электронных схем, при которой затраты на добавочную аппаратуру были бы минимальны.
Слайд 14

СОДЕРЖАТЕЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ На взвешенном бисвязном ориентированном графе требуется выделить такое

СОДЕРЖАТЕЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ

На взвешенном бисвязном ориентированном графе требуется выделить такое

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

ГРАФОВАЯ ИНТЕРПРЕТАЦИЯ ЗАДАЧИ О МИНИМАЛЬНОМ РАЗРЕЗЕ В БИСВЯЗНОМ ГРАФЕ 2 1

ГРАФОВАЯ ИНТЕРПРЕТАЦИЯ ЗАДАЧИ О МИНИМАЛЬНОМ РАЗРЕЗЕ В БИСВЯЗНОМ ГРАФЕ

2

1


7

4

3

5

6

Красным цветом выделены дуги одного из разрезов.

Слайд 16

ОБОЗНАЧЕНИЯ И ОПРЕДЕЛЕНИЯ

ОБОЗНАЧЕНИЯ И ОПРЕДЕЛЕНИЯ

Слайд 17

ФОРМАЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ О МИНИМАЛЬНОМ РАЗРЕЗЕ В БИСВЯЗНОМ ВЗВЕШЕННОМ ГРАФЕ

ФОРМАЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ О МИНИМАЛЬНОМ РАЗРЕЗЕ В БИСВЯЗНОМ ВЗВЕШЕННОМ ГРАФЕ

Слайд 18

ПРИМЕР 1: ПОСТАНОВКА ЗАДАЧИ 1 3 2 4 9 5 3 7 4 3

ПРИМЕР 1: ПОСТАНОВКА ЗАДАЧИ

1

3

2

4

9

5 3 7

4

3

Слайд 19

ЖУРНАЛ “IEEE TRANSACTIONS ON CIRCUIT THEORY” 60-е годы: статья Лемпела с

ЖУРНАЛ “IEEE TRANSACTIONS ON CIRCUIT THEORY”

60-е годы: статья Лемпела с Седербаума

о новой математике, развитой специально для решения задачи о минимальном разрезе в сильносвязном графе.
Начало семидесятых: статья Дивиетти и Грассели о том, что «новая математика» - мошенничество, она сводится к алгебре логики.
Такахико Камае (Япония), Неметри (Румыния): методы выделения всех путей и контуров на ориентированных графах.
Слайд 20

ПРИМЕР ПРИМЕНЕНИЯ МЕТОДА ЛЕМПЕЛА И СЕДЕРБАУМА a b C d e

ПРИМЕР ПРИМЕНЕНИЯ МЕТОДА ЛЕМПЕЛА И СЕДЕРБАУМА

a
b
C d
e

Контуры графа

G(X,U): dbc + de + ab.
Разрезы на графе G(X,U):
Слайд 21

ПРОВЕРКА ГРАФА НА НАЛИЧИЕ КОНТУРОВ Если последовательное удаление вершин-источников и вершин-стоков

ПРОВЕРКА ГРАФА НА НАЛИЧИЕ КОНТУРОВ

Если последовательное удаление вершин-источников и вершин-стоков исчерпывает

граф, то он был свободен от контуров.

1

2

3

4

2

4

3

3

4

4

Слайд 22

РЕШЕНИЕ ЗАДАЧИ ПРИМЕРА 1 ПЕРЕБОРОМ Ответ: z(3,4)=1; Подмножество дуг является разрезом,

РЕШЕНИЕ ЗАДАЧИ ПРИМЕРА 1 ПЕРЕБОРОМ

Ответ: z(3,4)=1;

Подмножество дуг
является разрезом, если

после удаления этих дуг последовательное отбрасывание вершин-источников и вершин-стоков исчерпывает граф.
Слайд 23

АЛГОРИТМ РАБОТЫ ГЕНЕРАТОРА СОЧЕТАНИЙ ЗНАЧЕНИЙ БУЛЕВЫХ ПЕРЕМЕННЫХ 1 Ввод числа переменных

АЛГОРИТМ РАБОТЫ ГЕНЕРАТОРА СОЧЕТАНИЙ ЗНАЧЕНИЙ БУЛЕВЫХ ПЕРЕМЕННЫХ

1 Ввод числа переменных n

2

M(i)=0; i=0,1,2,3,…, n

5 M(n)=M(n)+1

Да Нет

Получен новый разрез.

8 M(0)>0

9 Конец алгоритма

Да
Нет

Да
Нет

4 Это разрез?

Слайд 24

ДОСТОИНСТВА И НЕДОСТАТКИ АЛГОРИТМА ГЕНЕРАЦИИ ВСЕХ СОЧЕТАНИЙ ЗНАЧЕНИЙ ВЕКТОРА БУЛЕВЫХ ПЕРЕМЕННЫХ

ДОСТОИНСТВА И НЕДОСТАТКИ АЛГОРИТМА ГЕНЕРАЦИИ ВСЕХ СОЧЕТАНИЙ ЗНАЧЕНИЙ ВЕКТОРА БУЛЕВЫХ ПЕРЕМЕННЫХ

Достоинства:
Генерация

всех сочетаний значений булевых переменных гарантирует глобальный оптимум.
Простота алгоритма.
Легкость программной реализации.
Низкие требования к объему памяти компьютера
Легкость распараллеливания алгоритма.
Недостатки:
В ходе работы алгоритма генерируется более
сочетаний различных чисел:
алгоритм избыточен.
Слайд 25

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

САМОСТОЯТЕЛЬНО:

Решить задачу о минимальном разрезе в бисвязном взвешенном орграфе, пользуясь графом

персонального задания и приведенным выше алгоритмом.
Составить блок-схему алгоритма поиска минимального разреза на бисвязном графе, включающую генератор перестановок.
Программно реализовать построенный алгоритм.
Построить график зависимости времени счета T от размерности задачи n.
Пользуясь методом наименьших квадратов найти аналитические зависимости T(n).
Слайд 26

ЗАДАЧА О МАКСИМАЛЬНОЙ ЦИРКУЛЯЦИИ - ПРИМЕР 1 2 3 4 5

ЗАДАЧА О МАКСИМАЛЬНОЙ ЦИРКУЛЯЦИИ - ПРИМЕР

1
2
3
4
5

Три контура:
a1 = 1,2,3,4,5,1;
a2 = 4,2,3,4;
a3

= 5,3,4,5.

5 8

3 а3 6 12 а2 9

11

а1

а1+ а2 + а3 max;
a1 + a3 <= 3;
a1 + a2 <= 9;
a3 + a2 <=11;
a1>=0; a2>=0; a3>=0.

Слайд 27

ЗАДАЧА О МАКСИМАЛЬНОЙ ЦИРКУЛЯЦИИ В БИСВЯЗНОМ ГРАФЕ - ОБОЗНАЧЕНИЯ S(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

ПРИМЕР

Smax=1,5;
Rmin = 2. 1
1
1
1 1
1 1
1

1 1 1

2

1

3

4

5

6

Слайд 31

ТЕОРЕМА 2 В.Н. БУРКОВА На планарных ориентированных взвешенных сильносвязных графах величина

ТЕОРЕМА 2 В.Н. БУРКОВА

На планарных ориентированных взвешенных сильносвязных графах величина максимальной

циркуляции всегда целочислена и равна величине минимального разреза.
Слайд 32

САМОСТОЯТЕЛЬНО Пользуясь теоремой 2 В.Н. Буркова определить величину минимального разреза на

САМОСТОЯТЕЛЬНО

Пользуясь теоремой 2 В.Н. Буркова определить величину минимального разреза на планарном

графе G(X,U):
1
1 1 1 1 1
1
1 1

1

5

4

3

2

Слайд 33

ТЕОРЕМА БУРКОВА № 3 Любой перестановке вершин бисвязного орграфа π={i1, i2,

ТЕОРЕМА БУРКОВА № 3

Любой перестановке вершин бисвязного орграфа π={i1, i2, i3,

….in} отвечает разрез, состоящий из дуг, идущих из вершин стоящих слева в перестановке π, в вершины, стоящие в ней справа.
Слайд 34

ПРИМЕР 3 2 1 5 3 7 4 9 1 1

ПРИМЕР

3

2

1
5 3 7 4
9
1

1

2

3

π = 1, 2, 3
1 4
3
R=1+4+3=

8.

1

3

2

4 5
9
Π = 2, 3, 1; R=4 + 5 + 9 = 18

1)
2)

Слайд 35

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

ЛЕММА

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

π множества Х.
Слайд 36

МЕТОД ТИПА ВЕТВЕЙ И ГРАНИЦ С ФРОНТАЛЬНЫМ СПУСКОМ И ВЕТВЛЕНИЕМ ПО

МЕТОД ТИПА ВЕТВЕЙ И ГРАНИЦ С ФРОНТАЛЬНЫМ СПУСКОМ И ВЕТВЛЕНИЕМ ПО

ВЕРШИНАМ

G(X,U) Дерево ветвлений

2

4

3

1

S

2

1

2

3

4

2

4

3

3

2

6
1 2 8 7 5 4
3

2 14 13 7
15 7 6
12 6
6

Ответ: π = 1, 4,3,2; R = 6;
W={(1,2); (4,3)}.

Слайд 37

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

САМОСТОЯТЕЛЬНО

Решить задачу о минимальном разрезе на взвешенном орграфе G(X,U), заданном матрицей

M описанным выше методом:
- Предыдущая
Типы туристических костров. Заготовка и хранение дров. Способы разведения и тушение костров
Следующая -
Паронимы

Похожие презентации

Нормативная база УРО МООО «РСО»
The Chidc's leoding maufacturer &amp; cupperfier
Әндірістік тәжрибе бойынша есеп беру NGN
Massachusetts State House
«Ожившая кукла разных систем в известных театрах мира» «Куклы из тряпок, кусков дерева и бумажной массы совершенно явно оживают и действуют самостоятельно: они уже не следуют движениям управляющей ими руки, а напротив, сами ее направляют, у них свои жела
Культура Западной Европы
Sakramenty święte
Презентация "Народные традиции в костюме Снегурочки" - скачать презентации по МХК
Искусство комплимента
Стиль мода в нашей жизни
Энергетическая дипломатия стран Латинской Америки и Карибского бассейна на современном этапе
Маркетинговые возможности
Правила Дорожного Движения (ПДД)
Крито-микенская культура
Религия. Храм. Вера
Социология как наука об обществе
Автор: Макарова Татьяна Павловна, учитель математики высшей категории ГБОУ СОШ №618 г. Москвы
Аэрофлот.Российские авиалинии
Технология производства метанола
Лимфатическая система, systema lymphatica, - часть кровеносной (венозной) системы
Организационная структура Общероссийского Союза Образования
Классификация поверхностей
Язык культуры разнообразен
Система права
Директор МБОУ ДОД ДДТ п.г.т.Уренгой Пуровского района Коба Ирина Александровна
Проектирование свайных фундаментов. (Лекция 22)
Політичні партії, громадсько-політичні об’єднання та рухи
Векторы.Линейные операции
Вы можете прислать нам Вашу презентацию и мы опубликуем ее на сайте.
Обратная связь
Для правообладателей
Email: Нажмите что бы посмотреть