Инструкция пользователя

Для запуска программы нужно запустить файл Max_potоk.exe.

Для поиска максимального потока в сети необходимо выполнить следующие действия:

1) ввести количество вершин сети (n) в поле “Количество” и нажать кнопку “Количество вершин”. В зависимости от количества вершин изменятся размеры таблиц, которыми задаются матрицы пропускных способностей и максимального потока сети. Количество вершин не может превышать 10. На рисунках 3.2(а) та 3.2(б) представлен вид этих таблиц при n=8 та n=3 соответственно.

Инструкция пользователя - student2.ru
а

 
  Инструкция пользователя - student2.ru


б

Рис. 3.2.

2) заполнить матрицу пропускных способностей и указать номера вершин, которые будут началом (поле “s=”) и концом (поле “t=”) сети (рис. 3.3). Введение этих данных является обязательным условием для продолжения роботы программы;

Инструкция пользователя - student2.ru

Рис. 3.3.

3) рассчитать поток:

– если для выполнения этого этапа использовать кнопку “Считать поток”, то в таблице для представления матрицы максимального потока результат отображается немедленно, а в поле “Максимальный поток” при этом отображается величина максимального потока (рис. 3.4);

– если использовать кнопку “Итерации”, то в таблице для представления матрицы максимального потока результат отображается постепенно, в зависимости от насыщения и перераспределения потока в сети. Когда поток станет максимальным – кнопка больше не буде исполнять ни одних действий (рис. 3.5). Для выведения величины максимального потока в поле “Максимальный поток” нужно нажать кнопку “Считать поток”;

Инструкция пользователя - student2.ru

Рис. 3.4.

Инструкция пользователя - student2.ru

Рис. 3.5.

С помощью программы можно совершить дополнительные действия:

1) просмотреть пометки какой-либо вершины. Для этого нужно:

- задать вершину, для которой нужно вывести пометки (поле “Вершина”);

- нажать кнопку “Показать пометки”. При этом в поле “Предыдущая вершина” появится имя предыдущей вершины; в поле “Знак” появится знак “+”, если направление дуги совпадает с направлением потока, или “-“ – в противоположном случае; в поле “δ” – величина увеличения потока по данной дуге (рис. 3.6);

Инструкция пользователя - student2.ru

Рис. 3.6.

2) сделать таблицу матрицы максимального потока пустой. Для этого нужно нажать кнопку “Начать сначала”, но таблица матрицы пропускных способностей останется неизменной (рис. 3.7);

3) работать с новой сетью и с новой матрицей пропускных способностей. Для этого нужно ввести новое количество вершин, нажать кнопку “Количество вершин” и обе матрицы и все поля станут пустыми.

Инструкция пользователя - student2.ru

Рис. 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 помечены, но не просмотрены.

Инструкция пользователя - student2.ru

Рис. 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).

Инструкция пользователя - student2.ru

Рис. 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).

Инструкция пользователя - student2.ru

Рис. 3.10. Поток величины 5

25. Стираем все пометки.

26. Присваиваем вершине v1 пометку (+, ∞).

27. Вершины, смежные вершине v1, нельзя пометить, поскольку дуга (v1, v2) насыщена – φ(v1, v2) = φ(е1) = с(е1) = 3, и дуга (v1, v3) тоже насыщена – φ(v1, v3) = φ(е2) = с(е2) = 2. Сток остался непомеченным. Значит, полученный поток максимален.

А теперь найдём максимальный поток с помощью программы. Для этого введём матрицу пропускных способностей в соответствующие поля программы. Матрица имеет следующий вид:

Инструкция пользователя - student2.ru

Результат вычислений оказался тем же. Мы получили максимальный поток величины 5 (рис. 3.11).

Инструкция пользователя - student2.ru

Рис. 3.11.

Наши рекомендации