Тесты / 14 / Diskretka_test_krinzh_i_tresh

Тест начат

Saturday, 10 December 2022, 18:40

Состояние

Завершенные

Завершен

Saturday, 10 December 2022, 18:53

Прошло

12 мин. 6 сек.

времени

Баллы

8,00/10,00

Оценка

1,20 из 1,50 (80%)

Вопрос 1

Для поиска максимального потока в сети был использован алгоритм Форда-Фалкерсона. Процесс реализации алгоритма, закончившийся

Выполнен

нахождением максимального потока, состоял из девяти шагов, в ходе которых были последовательно найдены девять дополняющих

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

цепей с остаточными пропускными способностями 1, 2, 4, 2, 5, 3, 5, 1, 1 единицы соответственно. Чему равна пропускная способность

1,00

минимального разреза?

Отметить

вопрос

Ответ:

24

Вопрос 2

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

Выполнен

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

Ответ:

32

1,00

Отметить

вопрос

Вопрос 3

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

Выполнен

нулей на прочерки:

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

1,00

Отметить

-

6

2

5

-

вопрос

-

-

4

-

3

-

-

-

2

4

-

-

-

-

6

-

-

-

-

-

-

3

1

2

-

-

-

2

-

1

-

-

-

2

1

-

-

-

-

4

-

-

-

-

-

В сети задан разрез

, где

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

(1) Чему равен поток, текущий из

в

(

)?

Вопрос 4

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

Выполнен

прочерки:

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

1,00

-

5

4

-

4

-

Отметить

-

-

1

-

3

-

вопрос

-

-

-

4

-

2

-

-

-

-

-

3

-

-

6

-

-

7

-

-

-

-

-

-

Вершина с номером 1 является источником, вершина с номером 6 – стоком. В сети задан разрез

, где

Вопрос 5

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

Выполнен

прочерки:

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

1,00

-

6

8

5

2

-

Отметить

-

-

-

-

3

-

вопрос

-

1

-

-

2

6

-

-

1

-

-

5

-

-

-

-

-

9

-

-

-

-

-

-

Вопрос 6

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

Выполнен

прочерки:

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

1,00

Отметить

-

4

7

8

-

-

вопрос

-

-

-

-

-

6

-

4

-

-

4

2

-

-

3

-

6

-

-

-

-

-

-

9

-

-

-

-

-

-

-

3

3

4

-

-

-

-

-

-

-

4

-

1

-

-

3

2

-

-

3

-

1

-

-

-

-

-

-

4

-

-

-

-

-

-

Вопрос 7

С помощью алгоритма Форда-Фалкерсона ищется максимальный поток в сети с источником 1 и стоком 5. На третьем шаге реализации

Выполнен

алгоритма найдена дополняющая цепь к потоку, текущему по сети. Ею оказалась полуцепь, последовательно проходящая через вершины

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

1,2,3,4,5. Все дуги этой полуцепи за исключением дуги (4,3), прямые. Пропускная способность дуги (1,2) равна 8, дуги (2,3) – 9, дуги (4,3) –

1,00

5, дуги (4,5) – 7. Поток, текущий по дуге (1,2) равен 3, по дуге (2,3) – 3, по дуге (4,3) – 2, по дуге (4,5) – 3. Далее в соответствии с алгоритмом

Отметить

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

вопрос

на первом месте запишите поток на дуге (1,2), на втором – на дуге (2,3), на третьем – на дуге (4,3), на четвертом – на дуге (4,5).

Ответ:

5505

Вопрос 8

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

Выполнен

(1)

Пропускная способность разреза может оказаться меньшей чем величина, текущего по сети потока.

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

(2)

На каждом шаге алгоритма Форда-Фалкерсона текущий по сети поток либо остается неизменным, либо увеличивается.

1,00

Отметить

(3)

Для любого разреза

и любого потока верно, что сумма потока на дугах, начала, которых принадлежат , а концы - не

вопрос

меньше, чем сумма потока на дугах, начала, которых принадлежат , а концы - .

Вопрос 9

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

Выполнен

прочерки:

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

1,00

-

9

2

4

-

-

Отметить

-

-

-

-

6

1

вопрос

-

2

-

-

3

-

-

1

-

-

-

9

-

-

-

4

-

8

-

-

-

-

-

-

Вопрос 10

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

Выполнен

прочерки:

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

1,00

-

7

8

6

-

Отметить

вопрос

-

-

5

-

4

-

-

-

3

6

-

-

-

-

5

-

-

-

-

-

-

5

x

1

-

-

-

y

-

3

-

-

-

z

3

-

-

-

-

4

-

-

-

-

-

Закончить обзор

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

Тест по теме "Задача о максимальном потоке

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

максимальном потоке в сети"

в сети" для групп ПИН-21-26 ►

1

2

3

4

5

6

7

8

9