Личный кабинет / Мои курсы / ВМ-1 - Дискретная математика (01.03.04, #807) / Тема 15. Паросочетания в двудольных графах
/ Тест по теме "Парасочетания в двудольных графах" для групп ПМ-21,22, ИВТ-21,22,23
Тест начат Friday, 16 December 2022, 16:08
Состояние Завершенные
Завершен Friday, 16 December 2022, 16:38
Прошло 29 мин. 44 сек.
времени
Баллы 10,00/10,00
Оценка 1,50 из 1,50 (100%)
Вопрос 1
Выполнен
Баллов: 1,00 из 1,00
Дан полный граф с вершинами 1,2,3,4,5,6. Укажите, являются указанные множества ребер паросочетаниями или нет:
(1)34, 21, 56
(2)12, 23, 34, 45, 53, 62
(3)14, 25, 34, 54
(4)16, 25, 31
Ответ дайте в формате последовательности 0 и 1 (например, 0011): на первом месте запишите 1, если множество (1) является паросочетанием, в противном случае запишите 0; на втором месте запишите 1, если множество (2) является паросочетанием, в противном случае запишите 0; и т.д.
Ответ: 1000
Вопрос 2
Выполнен
Баллов: 1,00 из 1,00
Дан двудольный граф с вершинами 1,2,3,4 в доле X, вершинами a, b, c, d в доле Y и матрицей весов
3 |
4 |
5 |
2 |
5 |
4 |
2 |
8 |
4 |
5 |
2 |
4 |
2 |
2 |
5 |
7 |
Число |
. Даны подмножества A = {2,3} и B = {b,c,d} долей X и Y соответственно. К графу применено (A, B, ) преобразование. |
|
Чему равна сумма элементов главной диагонали преобразованной матрицы? |
||
Ответ: |
|
|
20 |
|
|
|
|
|
Вопрос 3
Выполнен
Баллов: 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
Вопрос 4
Выполнен
Баллов: 1,00 из 1,00
Дан полный граф с вершинами 1,2,3,4,5. На графе задано паросочетание {12, 34}. Укажите цепи, которые являются чередующимися относительно этого паросочетания (цепи заданы последовательностью вершин):
(1)34
(2)3214
(3)1534
(4)3421
Ответ дайте в формате последовательности 0 и 1 (например, 0011): на первом месте запишите 1, если цепь (1) чередующаяся, в противном случае запишите 0; на втором месте запишите 1, если цепь (2) чередующаяся, в противном случае запишите 0; и т.д.
Ответ: 1101
Вопрос 5
Выполнен
Баллов: 1,00 из 1,00
Ориентированный граф задан матрицей смежности
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
Производится поиск в ширину из вершины 1. При этом действует договоренность: концы дуг, выходящие из рассматриваемой на данном шаге вершины, заносятся в очередь в порядке их нумерации в матрице смежности (например, если в очереди находится только вершина 1 и она – начало дуг 13 и 15, то в начале в очередь включаем вершину 3, потом – вершину 5). Перечислите вершины в порядке занесения их в очередь при поиске ширину из вершины 1.
Ответ дайте в формате последовательности чисел без пробелов, скобок и запятых (например, 593…).
Ответ: 1273564
Вопрос 6
Выполнен
Баллов: 1,00 из 1,00
Дерево задано кодом из натуральных чисел 114467. На дереве задано паросочетание {12, 46, 78}. Относительно него сформулированы три утверждения. Верны ли они?
(1)парососочетание наибольшее
(2)паросочетание максимальное
(3)паросочетание совершенное.
Ответ дайте в формате последовательности 0 и 1 (например, 001): на первом месте запишите 1, если утверждение (1) верное, в противном случае запишите 0; на втором месте запишите 1, если утверждение (2) верное, в противном случае запишите 0; и т.д.
Ответ: 110
Вопрос 7
Выполнен
Баллов: 1,00 из 1,00
Какие утверждения верны?
(1)Любой полный неориентированный граф имеет совершенное паросочетание.
(2)Существует граф со ста вершинами, мощность наибольшего паросочетания которого равна 1.
(3)Любое совершенное паросочетание является наибольшим.
Ответ дайте в формате последовательности 0 и 1 (например, 001): на первом месте запишите 1, если утверждение (1) верное, в противном случае запишите 0; на втором месте запишите 1, если утверждение (2) верное, в противном случае запишите 0; и т.д.
Ответ: 011
Вопрос 8
Выполнен
Баллов: 1,00 из 1,00
Двудольный обыкновенный граф задан матрицей весов
3 |
5 |
6 |
6 |
7 |
8 |
9 |
2 |
3 |
1 |
6 |
6 |
5 |
3 |
4 |
2 |
Эта матрица была преобразована к виду, пригодному для начала работы алгоритма решения задачи о назначениях (то есть так, чтобы преобразованной матрице соответствовал граф с ребрами неотрицательного веса, в котором каждой вершине инцидентно по крайней мере одно ребро нулевого веса). Чему равна сумма элементов главной диагонали преобразованной матрицы?
Ответ: 9
Вопрос 9
Выполнен
Баллов: 1,00 из 1,00
Дан двудольный граф с вершинами 1,2,3 в первой доле, вершинами a, b, c во второй доле и ребрами 1a, 1c, 2a, 2b, 3b, 3c. На графе задано паросочетание {1a, 3b}. Сколько на графе имеется увеличивающих данное паросочетание цепей, ведущих из первой доли во вторую?
Ответ: 2
Вопрос 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
◄ Видеозапись лекции "Паросочетания в двудольных графах"
Перейти на...
Текст лекции "Задание булевых функций графами" ►