Слайд 2
СОДЕРЖАНИЕ
1. Формальная постановка и поиск решения задачи о
минимальном разрезе между двумя вершинами на взвешенном орграфе.
2. Текущий
контроль умения решать задачи на поиск кратчайших путей, максимальных потоков и минимальных разрезов.
3. Формальные постановки и поиск решений задач о минимальном разрезе и максимальной циркуляцией на взвешенном бисвязном орграфе.
Слайд 3
ЗАДАЧА О МИНИМАЛЬНОМ РАЗРЕЗЕ МЕЖДУ ДВУМЯ ВЕРШИНАМИ НА
ВЗВЕШЕННОМ ОРГРАФЕ
Часть 1
Слайд 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) ного разреза
1
2
3
2
3
1
2
5
7
1
2 5
7
1
Слайд 7
РЕШИТЬ ТРИ ЗАДАЧИ САМОСТОЯТЕЛЬНО
1. Определить
2. Определить 3.Определить
кратчайший максимальный минимальный
путь между поток из задан- разрез между
заданной ной вершины заданной
парой в заданную. парой вершин.
вершин.
Часть 2
Слайд 9
ПЕРСОНАЛЬНЫЕ ЗАДАНИЯ 10 - 18
Слайд 11
Минимальные разрезы в сильносвязных (бисвязных)
орграфах
Часть 3.
Слайд 12
К ИСТОРИИ ВОЗНИКНОВЕНИЯ ПРОБЛЕМЫ
В середине прошлого века развилась
полупроводниковая электроника, разброс параметров которой вызвал резкое усложнение радиосхем
и широкое применение контуров обратной связи.
Блок № 1
Блок № 2
Блок № n-1
Блок № n
Слайд 13
ЭКОНОМИЧЕСКИЙ ХАРАКТЕР ЗАДАЧИ
Отладка блоков электронных схем осуществляется в
порядке, позволяющем использовать уже проверенные и исправные блоки при
тестировании еще непроверенных. При этом сигналы, поступающие по контурам обратной связи от еще непроверенных блоков, генерируются специальной аппаратурой. Если известна стоимость дополнительной аппаратуры, генерирующей разного рода сигналы, то естественна постановка задачи, в которой требуется такая организация тестирования и отладки электронных схем, при которой затраты на добавочную аппаратуру были бы минимальны.
Слайд 14
СОДЕРЖАТЕЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ
На взвешенном бисвязном ориентированном
графе требуется выделить такое подмножество дуг, для которого справедливо:
1.
Удаление дуг выделенного подмножества разрывает на графе все контуры.
2. Суммарный вес дуг выделенного подмножества минимален.
Слайд 15
ГРАФОВАЯ ИНТЕРПРЕТАЦИЯ ЗАДАЧИ О МИНИМАЛЬНОМ РАЗРЕЗЕ В БИСВЯЗНОМ
ГРАФЕ
2
1
7
4
3
5
6
Красным цветом выделены дуги
одного из разрезов.
Слайд 17
ФОРМАЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ О МИНИМАЛЬНОМ РАЗРЕЗЕ В БИСВЯЗНОМ
ВЗВЕШЕННОМ ГРАФЕ
Слайд 18
ПРИМЕР 1: ПОСТАНОВКА ЗАДАЧИ
1
3
2
4
9
5 3 7 4
3
Слайд 19
ЖУРНАЛ “IEEE TRANSACTIONS ON CIRCUIT THEORY”
60-е годы: статья
Лемпела с Седербаума о новой математике, развитой специально для
решения задачи о минимальном разрезе в сильносвязном графе.
Начало семидесятых: статья Дивиетти и Грассели о том, что «новая математика» - мошенничество, она сводится к алгебре логики.
Такахико Камае (Япония), Неметри (Румыния): методы выделения всех путей и контуров на ориентированных графах.
Слайд 20
ПРИМЕР ПРИМЕНЕНИЯ МЕТОДА ЛЕМПЕЛА И СЕДЕРБАУМА
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;
Подмножество дуг
является разрезом, если после удаления этих дуг последовательное отбрасывание
вершин-источников и вершин-стоков исчерпывает граф.
Слайд 23
АЛГОРИТМ РАБОТЫ ГЕНЕРАТОРА СОЧЕТАНИЙ ЗНАЧЕНИЙ БУЛЕВЫХ ПЕРЕМЕННЫХ
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
Три контура:
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) – поток по дуге (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
2
1
3
4
5
6
Слайд 31
ТЕОРЕМА 2 В.Н. БУРКОВА
На планарных ориентированных взвешенных сильносвязных
графах величина максимальной циркуляции всегда целочислена и равна величине
минимального разреза.
Слайд 32
САМОСТОЯТЕЛЬНО
Пользуясь теоремой 2 В.Н. Буркова определить величину минимального
разреза на планарном графе G(X,U):
1
1 1 1 1 1
1
1 1
1
5
4
3
2
Слайд 33
ТЕОРЕМА БУРКОВА № 3
Любой перестановке вершин бисвязного орграфа
π={i1, i2, i3, ….in} отвечает разрез, состоящий из дуг,
идущих из вершин стоящих слева в перестановке π, в вершины, стоящие в ней справа.
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) отвечает
«своя» перестановка вершин π множества Х.
Слайд 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 описанным выше методом:
