Поиск максимальных потоков в сетях
Дипломная работа - Математика и статистика
Другие дипломы по предмету Математика и статистика
а, приписанные дугам, отвечают их пропускным способностям, отвечают их пропускным способностям. Нужно для каждой пары узлов сети определить величину максимального потока между ними. Эта задача решается при n 1= 6 1 = 5 итераций алгоритма Гомори-Ху. Если алгоритм Форда-Фалкерсона расстановки пометок применялся бы к каждой паре узлов, то нужно было бы решить пятнадцать задач о максимальном потоке.
Реализуем алгоритм Гомори-Ху на данной сети.
1. Выберем вершины s = v1 и t = v2. Минимальную пропускную способность относительно источника s = v1 и стока t = v2 имеет разрез со сторонами Vs = {v1, v3, v4, v5, v6} и Vt = {v2}. По теореме 1 величина максимального потока между вершинами v1 и v2 равна пропускной способности разреза (Vs, Vt): w12 = w21 = c(Vs, Vt) = 2 + 3 = 5. Объединим вершины с Vs в одну вершину и соединим её с вершиной v2 веткой с пропускной способностью 5 (рис. 2.7).
Рис. 2.7. Первый шаг алгоритма
2. Выберем вершины s = v1 и t = v3. Минимальную пропускную способность относительно источника s = v1 и стока t = v3 имеет разрез со сторонами Vs = {v1} и Vt = {v2, v3, v4, v5, v6}. По теореме 1 величина максимального потока между вершинами v1 и v3 равна пропускной способности разреза (Vs, Vt): w13 = w31 = c(Vs, Vt) = 2 + 4 + 2 = 8. Объединим вершины v3, v4, v5, v6 в одну вершину и соединим её с вершиной v1 веткой с пропускной способностью 8 (рис. 2.8).
Рис 2.8. Второй шаг
3. Выберем вершины s = v4 и t = v3. Минимальную пропускную способность относительно источника s = v4 и стока t = v3 имеет разрез со сторонами Vs = {v4} и Vt = {v1, v2, v3, v5, v6}. По теореме 1 величина максимального потока между вершинами v4 и v3 равна пропускной способности разреза (Vs, Vt): w43 = w34 = c(Vs, Vt) = 2 + 5 + 4 = 11. Объединим вершины v3, v5, v6 в одну вершину и соединим её с вершиной v4 веткой с пропускной способностью 11 (рис. 2.9).
Рис. 2.9. Третий шаг
4. Выберем вершины s = v5 и t = v3. Минимальную пропускную способность относительно источника s = v5 и стока t = v3 имеет разрез со сторонами Vs = {v5} и Vt = {v1, v2, v3, v4, v6}. Величина максимального потока между вершинами v5 и v3 равна пропускной способности разреза (Vs, Vt): w53 = w35 = c(Vs, Vt) = 5 + 4 = 9. Объединим вершины v3, v6 в одну вершину и соединим её с вершиной v5 веткой с пропускной способностью 9 (рис. 2.10).
Рис. 2.10. Четвёртый шаг
5. Выберем вершины s = v6 и t = v3. Минимальную пропускную способность относительно источника s = v6 и стока t = v3 имеет разрез со сторонами Vs = {v6} и Vt = {v1, v2, v3, v4, v5}.
Рис. 2.11. Остаточное дерево разрезов
Величина максимального потока между вершинами v6 и v3 равна пропускной способности разреза (Vs, Vt): w63 = w36 = c(Vs, Vt) = 5 + 6 + 4 = 15. Объединим вершину v3 с вершиной v6 веткой с пропускной способностью 15 (рис. 2.11).
По дереву перерезов, изображённого на рис. 2.11, легко найти остальные величины максимальных потоков. Например, v16 = v61 = 8, поскольку в цепи дерева разрезов, которая соединяет вершины v1 и v2, минимальная пропускная способность веток равна 8. Запишем величины максимальных потоков в виде матрицы:
.
Здесь на пересечение i-строки и j-столбца стоит величина максимального потока между вершинами vi и vj.
3.АВТОМАТИЗАЦИЯ ПОИСКА МАКСИМАЛЬНЫХ ПОТОКОВ В СЕТЯХ
3.1. Описание интерфейса программы
Главное окно программы содержит:
- таблицу для введения матрицы пропускных способностей;
- окно для просмотра матрицы максимального потока;
- поле для введения количества вершин;
- поля для введения начала и конца транспортной сети;
- поле для просмотра величины максимального потока;
- поле для введения номера вершины, пометку которой ми бы хотели увидеть;
- поля для просмотра этих пометок;
- кнопки “Количество вершин”, “Считать поток”, “Итерации”, “Начать сначала”, “Показать пометки” (рис. 3.1).
Рис. 3.1. Главное окно программы
3.2. Инструкция пользователя
Для запуска программы нужно запустить файл Max_potоk.exe.
Для поиска максимального потока в сети необходимо выполнить следующие действия:
- ввести количество вершин сети (n) в поле “Количество” и нажать кнопку “Количество вершин”. В зависимости от количества вершин изменятся размеры таблиц, которыми задаются матрицы пропускных способностей и максимального потока сети. Количество вершин не может превышать 10. На рисунках 3.2(а) та 3.2(б) представлен вид этих таблиц при n=8 та n=3 соответственно.
а
б
Рис. 3.2.