Тесты / 14 / YoZh

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

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

Тест начат Friday, 9 December 2022, 20:08

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

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

Прошло 23 мин. 13 сек.

времени

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

Оценка 1,05 из 1,50 (70%)

Вопрос 1

Выполнен

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

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

Ответ: 23

Вопрос 2

Выполнен

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

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

Ответ: 3604

Вопрос 3

Выполнен

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

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

Ответ: 256

Вопрос 4

Выполнен

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

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

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

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

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

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

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

Ответ: 9971

Вопрос 5

Выполнен

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

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

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

Ответ: 17

Вопрос 6

Выполнен

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

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

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

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

z.

Ответ: 612

Вопрос 7

Выполнен

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

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

Вопрос 8

Выполнен

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

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

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

Ответ: 19

Вопрос 9

Выполнен

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

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

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

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

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

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

Ответ: 63

Вопрос 10

Выполнен

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

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

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

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

(3)Пропускную способность0минимального разреза нельзя найти методом полного перебора.

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

Ответ: 110

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

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

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