Личный кабинет / Мои курсы / ВМ-1 - Дискретная математика (01.03.04, #807) / Тема 14. Задача о максимальном потоке в сети.
/ Тест по теме "Задача о максимальном потоке в сети" для групп ПМ-21,22, ИВТ-21,22,23
Тест начат Saturday, 10 December 2022, 17:41
Состояние Завершенные
Завершен Saturday, 10 December 2022, 17:56
Прошло 15 мин. 31 сек.
времени
Баллы 7,00/10,00
Оценка 1,05 из 1,50 (70%)
Вопрос 1
Выполнен
Баллов: 1,00 из 1,00
Сеть имеет 13 вершин, одна из которых является0источником, а одна – стоком. Сколько разрезов в сети можно определить?0
Ответ: 2048
Вопрос 2
Выполнен
Баллов: 1,00 из 1,00
С помощью алгоритма Форда-Фалкерсона ищется максимальный0поток в сети с источником 1 и стоком 5. На третьем шаге реализации алгоритма найдена0дополняющая цепь к потоку, текущему по сети. Ею оказалась полуцепь,0последовательно проходящая через вершины 1,2,3,4,5. Все дуги этой полуцепи за0исключением дуги (3,2), прямые. Пропускная способность дуги
(1,2) равна 5, дуги0(3,2) – 7, дуги (3,4) – 4, дуги (4,5) – 8. Поток, текущий по дуге (1,2) равен01, по дуге (3,2) – 4, по дуге (3,4) – 2, по дуге (4,5) – 4. Далее в0соответствии с алгоритмом был определен новый поток в сети. Перечислите без0скобок, пробелов и запятых значения нового потока на дугах дополняющей цепи: на0первом месте запишите поток на дуге (1,2), на втором – на дуге (3,2), на0третьем – на дуге (3,4), на четвертом – на дуге (4,5).0
Ответ: 3246
Вопрос 3
Выполнен
Баллов: 1,00 из 1,00
Сеть задана матрицей весов, которая получена из0матрицы смежности графа заменой единиц на веса соответствующих дуг и нули на прочерки: 0
- |
8 |
9 |
8 |
- |
- |
- |
- |
4 |
- |
- |
7 |
- |
- |
- |
2 |
1 |
- |
- |
- |
- |
- |
3 |
6 |
- |
2 |
- |
- |
- |
5 |
- |
- |
- |
- |
- |
- |
Вершина с номером 1 является источником, вершина с номером 60– стоком. Чему равна величина максимального потока?0
Ответ: 17
Вопрос 4
Выполнен
Баллов: 1,00 из 1,00
Для поиска максимального потока в сети был использован0алгоритм Форда-Фалкерсона. Процесс реализации алгоритма, закончившийся0нахождением максимального потока, состоял из 4-х шагов, в ходе которых были0последовательно найдены четыре дополняющие цепи с остаточными пропускными0способностями 3, 5, 8, 2 единицы соответственно. Чему равна пропускная0способность минимального разреза?0
Ответ: 18
Вопрос 5
Выполнен
Баллов: 0,00 из 1,00
Сеть задана матрицей весов, которая получена из0матрицы смежности графа заменой единиц на веса соответствующих дуг и нулей на прочерки: 0
- |
9 |
8 |
- |
- |
- |
- |
- |
- |
4 |
3 |
5 |
- |
2 |
- |
- |
5 |
- |
- |
- |
- |
- |
4 |
6 |
- |
- |
- |
- |
- |
8 |
- |
- |
- |
- |
- |
- |
Вершина с номером 1 является источником, вершина с номером 60– стоком. Чему равна пропускная способность минимального0 разреза?0
Ответ: 15
Вопрос 6
Выполнен
Баллов: 0,00 из 1,00
Сеть задана матрицей весов, которая получена из0матрицы смежности графа заменой единиц на веса соответствующих дуг и нулей на прочерки:0
- |
7 |
3 |
6 |
4 |
- |
- |
4 |
3 |
- |
- |
- |
- |
5 |
9 |
- |
- |
- |
- |
8 |
- |
- |
- |
- |
- |
Вершина с номером 1 является источником, вершина с номером 50– стоком. Поток задан матрицей, полученной из матрицы смежности графа заменой0единиц на значения функции потока на соответствующих дугах и нулей на прочерки:
- |
4 |
3 |
1 |
3 |
- |
- |
2 |
x |
- |
- |
- |
- |
y |
1 |
- |
- |
- |
- |
z |
- |
- |
- |
- |
- |
Определите, чему равны значения x, y, z. В0ответе перечислите искомые значения без скобок, запятых и пробелов: на первом месте запишите значение x, на втором – значение y, на третьем – значение
z.
Ответ: 612
Вопрос 7
Выполнен
Баллов: 0,00 из 1,00
Сеть задана матрицей весов, которая получена из0матрицы смежности графа заменой единиц на веса соответствующих дуг и заменой нулей на прочерки: 0
- |
4 |
- |
3 |
4 |
- |
- |
6 |
5 |
- |
- |
- |
- |
4 |
- |
- |
- |
- |
- |
6 |
- |
- |
- |
- |
- |
Поток задан матрицей, полученной из матрицы0смежности графа заменой единиц на значения функции потока на соответствующих0дугах и заменой нулей на прочерки:
- |
4 |
- |
2 |
3 |
- |
- |
3 |
1 |
- |
- |
- |
- |
3 |
- |
- |
- |
- |
- |
6 |
- |
- |
- |
- |
- |
В сети задан разрез |
, где |
|
|
. |
Ответьте на поставленные вопросы: |
|
|
|
|
(1) Чему равен поток, текущий из |
в |
( |
)?0 |
|
(2)Чему равна величина потока, текущего по сети?0
(3)На сколько пропускная способность разреза больше величины потока?0
(4)Чему равна остаточная пропускная способность цепи, последовательно проходящей через вершины 1,2,4,5?0
Ответ дайте в формате последовательности чисел без пробелов, скобок и запятых (например, 5924): на первое место поставьте ответ на вопрос (1), на второе - ответ на вопрос (2), и т.д.0
Ответ: 2930
Вопрос 8
Выполнен
Баллов: 1,00 из 1,00
Сеть задана матрицей весов, которая получена из0матрицы смежности графа заменой единиц на веса соответствующих дуг и и нулей на прочерки: 0
- |
9 |
7 |
5 |
- |
- |
- |
- |
- |
- |
3 |
- |
- |
4 |
- |
3 |
2 |
7 |
- |
- |
- |
- |
- |
2 |
- |
- |
- |
- |
- |
8 |
- |
- |
- |
- |
- |
- |
Вершина с номером 1 является источником, вершина с номером 60– стоком. В сети задан разрез |
, где |
||
Чему равна пропускная способность этого разреза?0 |
|
||
Ответ: |
|
|
|
30 |
|
|
|
|
|
|
|
Вопрос 9
Выполнен
Баллов: 1,00 из 1,00
Какие утверждения верны?0
(1)Пропускная способность разреза может оказаться меньшей0чем величина, текущего по сети потока.
(2)На каждом шаге алгоритма0Форда-Фалкерсона текущий по сети поток либо остается неизменным, либо0 увеличивается.
(3) Для любого разреза и любого потока верно, что сумма потока на дугах, начала,0которых принадлежат , а концы - не меньше, чем сумма потока0на дугах, начала, которых принадлежат , а концы - .
Ответ дайте в формате последовательности 0 и 1 (например, 001): на0первом месте запишите 1, если утверждение (1) верное, в противном случае0запишите 0; на втором месте запишите 1, если утверждение (2) верное, в0противном случае запишите 0; и
т.д.0
Ответ: 001
Вопрос 10
Выполнен
Баллов: 1,00 из 1,00
Сеть задана матрицей весов, которая получена из0матрицы смежности графа заменой единиц на веса соответствующих дуг и нулей на прочерки:
- |
8 |
7 |
6 |
- |
- |
- |
- |
- |
- |
9 |
- |
- |
4 |
- |
2 |
4 |
- |
- |
- |
- |
- |
- |
9 |
- |
- |
- |
5 |
- |
8 |
- |
- |
- |
- |
- |
- |
Поток задан матрицей, полученной из матрицы0смежности графа заменой единиц на значения функции потока на соответствующих0дугах и нулей на прочерки:0
- |
2 |
6 |
1 |
- |
- |
- |
- |
- |
- |
6 |
- |
- |
4 |
- |
1 |
1 |
- |
- |
- |
- |
- |
- |
6 |
- |
- |
- |
4 |
- |
3 |
- |
- |
- |
- |
- |
- |
Ответьте на поставленные вопросы:0
(1)Чему равна остаточная пропускная способность полуцепи, последовательно проходящей через вершины 1, 4, 5, 6?0
(2)Сколько дополняющих к потоку цепей, идущих из источника в сток, начинаются с последовательного прохождения вершин
1,4?0
Ответ дайте в формате последовательности чисел без пробелов, скобок и запятых (например, 59): на первое место поставьте ответ на вопрос (1), на второе - ответ на вопрос (2).0
Ответ: 43
◄ Видеозапись лекции "Задача о максимальном потоке в сети"
Перейти на...
Тест по теме "Задача о максимальном потоке в сети" для групп ПИН-21-26 ►