Личный кабинет / Мои курсы / ВМ-1 - Дискретная математика (01.03.04, #807) / Тема 15. Паросочетания в двудольных графах
/ Тест по теме "Парасочетания в двудольных графах" для групп ПМ-21,22, ИВТ-21,22,23
Тест начат Friday, 16 December 2022, 16:43
Состояние Завершенные
Завершен Friday, 16 December 2022, 17:09
Прошло 25 мин. 7 сек.
времени
Баллы 9,00/10,00
Оценка 1,35 из 1,50 (90%)
Вопрос 1
Выполнен
Баллов: 1,00 из 1,00
Ориентированный граф задан матрицей смежности
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
Производится поиск в ширину из вершины 1. При этом действует договоренность: концы дуг, выходящие из рассматриваемой на данном шаге вершины, заносятся в очередь в порядке их нумерации в матрице смежности (например, если в очереди находится только вершина 1 и она – начало дуг 13 и 15, то в начале в очередь включаем вершину 3, потом – вершину 5). Перечислите вершины в порядке занесения их в очередь при поиске ширину из вершины 1.
Ответ дайте в формате последовательности чисел без пробелов, скобок и запятых (например, 593…).
Ответ: 1256347
Вопрос 2
Выполнен
Баллов: 1,00 из 1,00
Дан двудольный граф с вершинами 1,2,3,4 в доле X, вершинами a, b, c, d в доле Y и матрицей весов
1 |
6 |
7 |
0 |
0 |
0 |
0 |
3 |
2 |
3 |
4 |
0 |
5 |
1 |
2 |
0 |
Построен остовный подграф этого графа, содержащий только ребра нулевого веса, в нем выбрано максимальное паросочетание {2a, 4d} и проведена одна итерация алгоритма построения совершенного паросочетания. В результате получено новое весовое отображение графа. Чему равна сумма элементов, стоящих в новой матрице весов на главной диагонали?
Ответ: 3
Вопрос 3
Выполнен
Баллов: 1,00 из 1,00
Дерево задано кодом из натуральных чисел 841576. На дереве задано паросочетание {14, 57, 68}. Относительно него сформулированы три утверждения. Верны ли они?
(1)парососочетание наибольшее
(2)паросочетание максимальное
(3)паросочетание совершенное.
Ответ дайте в формате последовательности 0 и 1 (например, 001): на первом месте запишите 1, если утверждение (1) верное, в противном случае запишите 0; на втором месте запишите 1, если утверждение (2) верное, в противном случае запишите 0; и т.д.
Ответ: 010
Вопрос 4
Выполнен
Баллов: 1,00 из 1,00
Дан полный двудольный граф с вершинами 1,2,3,4,5 в первой доле и вершинами a,b,c,d,e во второй. Укажите, являются указанные множества ребер паросочетаниями или нет:
(1)1c, 2b, 4e, 5b
(2)1d, 2a, 3a
(3)2c, 3e, 4b
(4)4a, 1b, 3e, 2c, 5d
Ответ дайте в формате последовательности 0 и 1 (например, 0011): на первом месте запишите 1, если множество (1) является паросочетанием, в противном случае запишите 0; на втором месте запишите 1, если множество (2) является паросочетанием, в противном случае запишите 0; и т.д.
Ответ: 0011
Вопрос 5
Выполнен
Баллов: 0,00 из 1,00
Дерево задано кодом из натуральных чисел 1144. Сколько на этом графе можно определить наибольших паросочетаний? максимальных паросочетаний? совершенных паросочетаний?
Ответ дайте в формате последовательности трех чисел, записав их подряд без пробелов и запятых (например, 572): на первом месте запишите количество наибольших паросочетаний, на втором - максимальных, на третьем - совершенных.
Ответ: 540
Вопрос 6
Выполнен
Баллов: 1,00 из 1,00
Двудольный обыкновенный граф задан матрицей весов
4 |
3 |
5 |
6 |
2 |
4 |
3 |
8 |
5 |
5 |
2 |
4 |
2 |
6 |
5 |
7 |
Эта матрица была преобразована к виду, пригодному для начала работы алгоритма решения задачи о назначениях (то есть так, чтобы преобразованной матрице соответствовал граф с ребрами неотрицательного веса, в котором каждой вершине инцидентно по крайней мере одно ребро нулевого веса). Чему равна сумма элементов главной диагонали преобразованной матрицы?
Ответ: 6
Вопрос 7
Выполнен
Баллов: 1,00 из 1,00
Дан полный граф с вершинами 1,2,3,4,5. На графе задано паросочетание {12, 35}. Укажите цепи, которые являются чередующимися относительно этого паросочетания (цепи заданы последовательностью вершин):
(1)1235
(2)5324
(3)14
(4)4532
Ответ дайте в формате последовательности 0 и 1 (например, 0011): на первом месте запишите 1, если цепь (1) чередующаяся, в противном случае запишите 0; на втором месте запишите 1, если цепь (2) чередующаяся, в противном случае запишите 0; и т.д.
Ответ: 1011
Вопрос 8
Выполнен
Баллов: 1,00 из 1,00
Дан двудольный граф с вершинами 1,2,3,4 в первой доле, вершинами a, b, c, d во второй доле и ребрами 1a, 1b, 1c, 1d, 2a, 2c, 3d. На графе задано паросочетание {2a, 3d}. Сколько на графе имеется увеличивающих данное паросочетание цепей, ведущих из первой доли во вторую?
Ответ: 3
Вопрос 9
Выполнен
Баллов: 1,00 из 1,00
Дан двудольный граф с вершинами 1,2,3,4 в доле X, вершинами a, b, c, d в доле Y и матрицей весов
4 |
3 |
1 |
6 |
2 |
4 |
3 |
8 |
5 |
1 |
2 |
4 |
2 |
6 |
5 |
4 |
Число |
. Даны подмножества A = {1,2,3} и B = {b,c} долей X и Y соответственно. К графу применено (A, B, ) преобразование. |
|
Чему равна сумма элементов главной диагонали преобразованной матрицы? |
||
Ответ: |
|
|
12 |
|
|
|
|
|
Вопрос 10
Выполнен
Баллов: 1,00 из 1,00
Дан двудольный граф с вершинами a, b, c, d в доле X и 1,2,3,4 в доле Y, а также ребрами a1, a3, b1, b2, c1, c2, c4, d3. Выбрано максимальное паросочетание, включающее ребра a3, b1, c4, и в результате одной итерации алгоритма построения наибольшего паросочетания в двудольном графе найдено новое паросочетание. Укажите вершины смежные вершинам a, b, c, d, в найденном паросочетании.
Ответ дайте в формате последовательности чисел (например, 1034): на первом месте запишите номер вершины, смежной с вершиной a (если смежной вершины нет, запишите 0); на втором месте запишите номер вершины, смежной с вершиной b (если смежной вершины нет, запишите 0);и т.д.
Ответ: 1243
◄ Видеозапись лекции "Паросочетания в двудольных графах"
Перейти на...
Текст лекции "Задание булевых функций графами" ►