Тесты / 14 / neputevy

Личный кабинет / Мои курсы / ВМ-1 - Дискретная математика (01.03.04, #807) / Тема 14. Задача о максимальном потоке в сети.

/ Тест по теме "Задача о максимальном потоке в сети" для групп ПМ-21,22, ИВТ-21,22,23

Тест начат Friday, 9 December 2022, 19:36

Состояние Завершенные

Завершен Friday, 9 December 2022, 20:05

Прошло 29 мин. 40 сек.

времени

Баллы 6,00/10,00

Оценка 0,90 из 1,50 (60%)

Вопрос 1

Выполнен

Баллов: 1,00 из 1,00

С помощью алгоритма Форда-Фалкерсона ищется0максимальный поток в сети с источником 1 и стоком 5. На третьем шаге реализации0алгоритма найдена дополняющая цепь к потоку, текущему по сети. Ею оказалась0полуцепь, последовательно проходящая через вершины 1,2,3,4,5. Все дуги этой0полуцепи за исключением дуги (3,2), прямые. Пропускная способность дуги (1,2) равна 6, дуги (3,2) – 4, дуги (3,4) – 8, дуги (4,5) – 7. Поток, текущий по дуге0(1,2) равен 2, по дуге (3,2) – 3, по дуге (3,4) – 6, по дуге (4,5) – 4. Далее в0соответствии с алгоритмом был определен новый поток в сети. Перечислите без0скобок, пробелов и запятых значения нового потока на дугах дополняющей цепи: на0первом месте запишите поток на дуге (1,2), на втором – на дуге (3,2), на0третьем – на дуге (3,4), на четвертом – на дуге (4,5).0

Ответ: 4186

Вопрос 2

Выполнен

Баллов: 1,00 из 1,00

Сеть задана матрицей весов, которая получена из0матрицы смежности графа заменой единиц на веса соответствующих дуг и и нулей на прочерки: 0

Вопрос 3

Выполнен

Баллов: 1,00 из 1,00

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

Ответ: 24

Вопрос 4

Выполнен

Баллов: 0,00 из 1,00

Сеть задана матрицей весов, которая получена из0матрицы смежности графа заменой единиц на веса соответствующих дуг и нулей на прочерки: 0

Вершина с номером 1 является источником, вершина с номером 60– стоком. Чему равна пропускная способность минимального0 разреза?0

Ответ: 14

Вопрос 5

Выполнен

Баллов: 1,00 из 1,00

Сеть задана матрицей весов, которая получена из0матрицы смежности графа заменой единиц на веса соответствующих дуг и нулей на прочерки:

Поток задан матрицей, полученной из матрицы0смежности графа заменой единиц на значения функции потока на соответствующих дугах и нулей на прочерки:0

Ответьте на поставленные вопросы:0

(1)Чему равна остаточная пропускная способность полуцепи, последовательно проходящей через вершины 1, 2, 3, 4, 5, 6?0

(2)Сколько дополняющих к потоку цепей, идущих из источника в сток, начинаются с последовательного прохождения вершин 1, 2, 3?0 Ответ дайте в формате последовательности чисел без пробелов, скобок и запятых (например, 59): на первое место поставьте ответ на вопрос (1), на второе - ответ на вопрос (2).0

Ответ: 12

Вопрос 6

Выполнен

Баллов: 0,00 из 1,00

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

(1)Если в сети найдется разрез, пропускная способность0которого больше величины потока, текущего в сети, то поток не максимальный.

(2)Любое разбиение множества0вершин сети на два подмножества является разрезом.

Ответ дайте в формате последовательности 0 и 1 (например, 001): на0первом месте запишите 1, если утверждение (1) верное, в противном случае0запишите 0; на втором месте запишите 1, если утверждение (2) верное, в0противном случае запишите 0; и т.д.0

Ответ: 000

Вопрос 7

Выполнен

Баллов: 1,00 из 1,00

Сеть задана матрицей весов, которая получена из0матрицы смежности графа заменой единиц на веса соответствующих дуг и заменой нулей на прочерки: 0

Поток задан матрицей, полученной из матрицы0смежности графа заменой единиц на значения функции потока на соответствующих дугах и заменой нулей на прочерки:

(2)Чему равна величина потока, текущего по сети?0

(3)На сколько пропускная способность разреза больше величины потока, текущего по сети?0

(4)Чему равна остаточная пропускная способность цепи, последовательно проходящей через вершины 1,3,2,5?0

Ответ дайте в формате последовательности чисел без пробелов, скобок и запятых (например, 5924): на первое место поставьте ответ на вопрос (1), на второе - ответ на вопрос (2), и т.д.0

Ответ: 0562

Вопрос 8

Выполнен

Баллов: 0,00 из 1,00

Сеть имеет 9 вершин, одна из которых является0источником, а одна – стоком. Сколько разрезов в сети можно определить?0

Ответ: 256

Вопрос 9

Выполнен

Баллов: 1,00 из 1,00

Сеть задана матрицей весов, которая получена из0матрицы смежности графа заменой единиц на веса соответствующих дуг и нули на прочерки: 0

Вершина с номером 1 является источником, вершина с номером 60– стоком. Чему равна величина максимального потока?0

Ответ: 13

Вопрос 10

Выполнен

Баллов: 0,00 из 1,00

Сеть задана матрицей весов, которая получена из0матрицы смежности графа заменой единиц на веса соответствующих дуг и нулей на прочерки:0

Вершина с номером 1 является источником, вершина с номером 50– стоком. Поток задан матрицей, полученной из матрицы смежности графа заменой0единиц на значения функции потока на соответствующих дугах и нулей на прочерки:

Определите, чему равны значения x, y, z. В0ответе перечислите искомые значения без скобок, запятых и пробелов: на первом0месте запишите значение x, на втором – значение y, на третьем – значение

z.

Ответ: 134

◄ Видеозапись лекции "Задача о максимальном потоке в сети"

Перейти на...

Текст лекции "Паросочетания в двудольных графах" ►