1. Главная
  2. Библиотека
  3. Теория вероятностей
  4. Для поиска максимального потока в сети был использован...
Решение задачи на тему

Для поиска максимального потока в сети был использован алгоритм Форда-Фалкерсона. В ходе реализации алгоритма было найдено пять дополняющих цепей с остаточными пропускными способностями 6, 8, 1, 2, 3 единицы соответственно. Чему равна пропускная

  • Теория вероятностей
  • #Теория графов
  • #Теория оптимизации
Для поиска максимального потока в сети был использован алгоритм Форда-Фалкерсона. В ходе реализации алгоритма было найдено пять дополняющих цепей с остаточными пропускными способностями 6, 8, 1, 2, 3 единицы соответственно. Чему равна пропускная

Условие:

Для поиска максимального потока в сети был использован алгоритм Форда-Фалкерсона. Процесс реализации алгоритма, закончившийся нахождением максимального потока, состоял из пяти шагов, в ходе которых были последовательно найдены пять дополняющих цепей с остаточными пропускными способностями 6, 8, 1, 2, 3 единицы соответственно. Чему равна пропускная способность минимального разреза?

Решение:

Шаг 1. По алгоритму Форда-Фалкерсона максимальный поток находится как сумма потоков, добавленных на каждом шаге. Здесь было найдено 5 дополняющих цепей с потоками: 6, 8, 1, 2 и 3 единицы.

Шаг 2. ...

Выбери предмет