← Все тренажёры Сети и потоки: остаточная сеть и минимальный разрез

Сети и потоки: остаточная сеть и минимальный разрез

Сохранение потока, Форд–Фалкерсон и теорема о максимальном потоке.

20 заданий · Теория графов

Как будете решать?

Режим
Режим

Блок 1. Один верный вариант

1

Какое ограничение выполняет поток на исходной дуге ee?

2

Где требуется закон сохранения потока?

3

Как определяется величина потока при наличии входящих в исток дуг?

4

Дуга имеет ёмкость 7 и поток 3. Какова её прямая остаточная ёмкость?

5

Для чего нужна обратная остаточная дуга?

6

На сколько можно увеличить поток по дополняющему пути?

7

Какие дуги учитываются в ёмкости разреза (S,T)(S,T)?

8

Когда допустимый поток максимален?

9

Что утверждает теорема о максимальном потоке и минимальном разрезе?

10

Какое условие гарантирует завершение метода Форда–Фалкерсона при произвольном выборе дополняющих путей и нулевом старте?

Блок 2. Краткий ответ

11

Остаточные ёмкости дуг дополняющего пути равны 5, 2 и 4. Найдите возможное увеличение потока.

целое число

12

По исходной дуге ёмкости 9 проходит поток 4. Какова ёмкость соответствующей обратной остаточной дуги?

целое число

13

Сеть содержит только дуги s→a:3s\to a:3, a→t:2a\to t:2, s→t:1s\to t:1. Найдите максимальный поток.

целое число

14

Сеть: s→a:3s\to a:3, s→b:2s\to b:2, a→b:1a\to b:1, a→t:2a\to t:2, b→t:3b\to t:3. Найдите максимальный поток.

целое число

15

Из истока выходит суммарный поток 11, в исток входит 3. Найдите величину потока.

целое число

16

Через разрез идут дуги из SS в TT ёмкостей 4 и 6 и дуга из TT в SS ёмкости 9. Чему равна ёмкость разреза?

целое число

Блок 3. Несколько верных вариантов

17

Какие условия входят в допустимость потока?

Отметьте все верные варианты

18

Что верно об остаточной сети?

Отметьте все верные варианты

19

Что гарантирует найденная пара: допустимый поток величины 12 и разрез ёмкости 12?

Отметьте все верные варианты

20

Какие утверждения о разрезе верны?

Отметьте все верные варианты

Завершение теста

Все ответы сохраняются автоматически. Нажмите для отправки на проверку.

Карта заданий (20)

Вход на платформу

Обратная связь

Сообщите об ошибке, задайте вопрос или предложите, что добавить.