Инструкция пользователя
Для запуска программы нужно запустить файл Max_potоk.exe. Для поиска максимального потока в сети необходимо выполнить следующие действия: 1) ввести количество вершин сети (n) в поле “Количество” и нажать кнопку “Количество вершин”. В зависимости от количества вершин изменятся размеры таблиц, которыми задаются матрицы пропускных способностей и максимального потока сети. Количество вершин не может превышать 10. На рисунках 3.2(а) та 3.2(б) представлен вид этих таблиц при n=8 та n=3 соответственно.
Рис. 3.2. 2) заполнить матрицу пропускных способностей и указать номера вершин, которые будут началом (поле “s=”) и концом (поле “t=”) сети (рис. 3.3). Введение этих данных является обязательным условием для продолжения роботы программы; Рис. 3.3. 3) рассчитать поток: – если для выполнения этого этапа использовать кнопку “Считать поток”, то в таблице для представления матрицы максимального потока результат отображается немедленно, а в поле “Максимальный поток” при этом отображается величина максимального потока (рис. 3.4); – если использовать кнопку “Итерации”, то в таблице для представления матрицы максимального потока результат отображается постепенно, в зависимости от насыщения и перераспределения потока в сети. Когда поток станет максимальным – кнопка больше не буде исполнять ни одних действий (рис. 3.5). Для выведения величины максимального потока в поле “Максимальный поток” нужно нажать кнопку “Считать поток”; Рис. 3.4. Рис. 3.5. С помощью программы можно совершить дополнительные действия: 1) просмотреть пометки какой-либо вершины. Для этого нужно: - задать вершину, для которой нужно вывести пометки (поле “Вершина”); - нажать кнопку “Показать пометки”. При этом в поле “Предыдущая вершина” появится имя предыдущей вершины; в поле “Знак” появится знак “+”, если направление дуги совпадает с направлением потока, или “-“ – в противоположном случае; в поле “δ” – величина увеличения потока по данной дуге (рис. 3.6); Рис. 3.6. 2) сделать таблицу матрицы максимального потока пустой. Для этого нужно нажать кнопку “Начать сначала”, но таблица матрицы пропускных способностей останется неизменной (рис. 3.7); 3) работать с новой сетью и с новой матрицей пропускных способностей. Для этого нужно ввести новое количество вершин, нажать кнопку “Количество вершин” и обе матрицы и все поля станут пустыми. Рис. 3.7. Реализация программы Сравним результаты вычислений с помощью программы и вручную. Для ручного способа вычислений будем использовать алгоритм Форда-Фалкерсона. 1. Возьмём поток, изображённый на рисунке 3.8 как начальный допустимый поток. Он имеет величину 3. 2. Присвоим источнику, вершине v1, пометку (+, ∞). Вершина v1 помечена, но не просмотрена. 3. Просмотрим вершины, смежные с вершиной v1. Вершине v2 присвоим пометку (+v1, 1), а вершине v3 – пометку (+v1, 1),т.к. φ(v1, v2) = 2 < 3 = с1, φ(v1, v3) = 1 < 2 = с2. Вершина v1 помечена и просмотрена, а вершины v2 и v3 помечены, но не просмотрены. Рис. 3.8. Поток величины 3 4. Просмотрим вершины, смежные с вершиной v2. Из вершин, смежных с вершиной v2, не помечена только вершина v4. Вершине v4 присваиваем пометку (+v2, 1), поскольку φ(v2, v4) = 1 < 3 = с3. 5. Просмотрим вершины, смежные с вершиной v3. Из вершин, смежных с вершиной v3, не помечена только вершина v5. Вершине v5 присваиваем пометку (+v3, 1), поскольку φ(v3, v5) = 2 < 4 = с4. 6. Просмотрим вершины, смежные с вершиной v4. Смежной и непомеченной является вершина v6. Присваиваем ей пометку (+v4, 1), поскольку φ(v4, v6) = 1 < 4 = с5. 7. Просмотрим вершины, смежные с вершиной v5. Смежной и непомеченной является вершина v7. Присваиваем ей пометку (+v5, 1), поскольку φ(v5, v7) = 2 < 3 = с6. 8. Просмотрим вершины, смежные с вершиной v6. Смежной и непомеченной является вершина v8. Присваиваем ей пометку (+v6, 1), поскольку φ(v6, v8) = 2 < 5 = с7. Сток помечен. Переходим к операции Б – увеличению потока. 9. Сток имеет пометку (+v6, 1). Поэтому увеличиваем поток по дуге (v6, v8) на 1. 10. Вершина v6 имеет пометку (+v4, 1). Поэтому увеличиваем поток по дуге (v4, v6) на 1. 11. . Вершина v4 имеет пометку (+v2, 1). Поэтому увеличиваем поток по дуге (v2, v4) на 1. 12. . Вершина v2 имеет пометку (+v1, 1). Поэтому увеличиваем поток по дуге (v1, v2) на 1. Мы получили новый поток величины 4 (рис. 3.9). Рис. 3.9. Поток величины 4 13. Стираем все пометки. 14. Присваиваем вершине v1 пометку (+, ∞). 15. Просмотрим вершины, смежные с вершиной v1. Вершину v2 не помечаем, поскольку φ(v1, v2) = 3 = c(e1), а вершинеv3 присваиваем пометку (+v1, 1). 16. Просмотрим вершины, смежные с вершиной v3. Вершине v2 присваиваем пометку (-v3, 1), поскольку φ(v2, v3) = 1 > 0, l(v) = 1 и min(1, 1) = 1, а вершине v5 припишем пометку (+v3, 1), так как φ(v3, v5) = 2 < 4 = c8. 17. Просмотрим вершины, смежные с вершиной v4. Вершине v6 присваиваем пометку (+v4, 1), поскольку φ(v4, v6) = 3 < 5 = с9. 18. Просмотрим вершины, смежные с вершиной v5. Вершине v7 присваиваем пометку (+v5, 1), поскольку φ(v5, v7) = 2 < 3 = с10. 19. Просмотрим вершины, смежные с вершиной v6. Вершине v8 присваиваем пометку (+v6, 1), поскольку φ(v6, v8) = 3 < 5 = с11. Сток помечен. Переходим к операции Б – увеличению потока. 20. Сток имеет пометку (+v6, 1). Поэтому увеличиваем поток по дуге (v6, v8) на 1. 21. Вершина v6 имеет пометку (+v4, 1). Поэтому увеличиваем поток по дуге (v4, v6) на 1. 22. Вершина v4 имеет пометку (+v2, 1). Поэтому увеличиваем поток по дуге (v2, v4) на 1. 23. Вершина v2 имеет пометку (-v3, 1). Поэтому уменьшаем поток по дуге (v2, v3) на 1. 24. Вершина v3 имеет пометку (+v1, 1). Поэтому увеличиваем поток по дуге (v1, v3) на 1. Получили новый поток величины 5 (рис. 3.10). Рис. 3.10. Поток величины 5 25. Стираем все пометки. 26. Присваиваем вершине v1 пометку (+, ∞). 27. Вершины, смежные вершине v1, нельзя пометить, поскольку дуга (v1, v2) насыщена – φ(v1, v2) = φ(е1) = с(е1) = 3, и дуга (v1, v3) тоже насыщена – φ(v1, v3) = φ(е2) = с(е2) = 2. Сток остался непомеченным. Значит, полученный поток максимален. А теперь найдём максимальный поток с помощью программы. Для этого введём матрицу пропускных способностей в соответствующие поля программы. Матрица имеет следующий вид: Результат вычислений оказался тем же. Мы получили максимальный поток величины 5 (рис. 3.11). Рис. 3.11.
Популярное: Как выбрать специалиста по управлению гостиницей: Понятно, что управление гостиницей невозможно без специальных знаний. Соответственно, важна квалификация... Почему человек чувствует себя несчастным?: Для начала определим, что такое несчастье. Несчастьем мы будем считать психологическое состояние... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (521)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |