Geum.ru

Поиск максимальных потоков в сетях

Дипломная работа - Математика и статистика

Другие дипломы по предмету Математика и статистика

тся обязательным условием для продолжения роботы программы;

Рис. 3.3.

 

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

Рис. 3.4.

 

Рис. 3.5.

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

  1. просмотреть пометки какой-либо вершины. Для этого нужно:
  2. задать вершину, для которой нужно вывести пометки (поле “Вершина”);
  3. нажать кнопку “Показать пометки”. При этом в поле “Предыдущая вершина” появится имя предыдущей вершины; в поле “Знак” появится знак “+”, если направление дуги совпадает с направлением потока, или “-“ в противоположном случае; в поле “?” величина увеличения потока по данной дуге (рис. 3.6);

Рис. 3.6.

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

Рис. 3.7.

3.3. Реализация программы

Сравним результаты вычислений с помощью программы и вручную. Для ручного способа вычислений будем использовать алгоритм Форда-Фалкерсона.

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, v<