Личный кабинет / Мои курсы / ВМ-1 - Дискретная математика (01.03.04, #807) / Тема 15. Паросочетания в двудольных графах
/ Тест по теме "Парасочетания в двудольных графах" для групп ПМ-21,22, ИВТ-21,22,23
Тест начат Friday, 16 December 2022, 15:35
Состояние Завершенные
Завершен Friday, 16 December 2022, 16:02
Прошло 26 мин. 30 сек.
времени
Баллы 9,00/10,00
Оценка 1,35 из 1,50 (90%)
Вопрос 1
Выполнен
Баллов: 1,00 из 1,00
Дан двудольный граф с вершинами 1,2,3 в первой доле, вершинами a, b, c во второй доле и ребрами 1a, 1c, 2a, 2b, 3b, 3c. На графе задано паросочетание {1a, 3b}. Сколько на графе имеется увеличивающих данное паросочетание цепей, ведущих из первой доли во вторую?
Ответ: 2
Вопрос 2
Выполнен
Баллов: 1,00 из 1,00
Какие утверждения верны?
(1)Любое наибольшее паросочетание является максимальным.
(2)В полном двудольном графе число вершин, насыщенных произвольным паросочетанием, четно.
(3)Существует граф со ста вершинами, мощность максимального паросочетания которого равна 1.
Ответ дайте в формате последовательности 0 и 1 (например, 001): на первом месте запишите 1, если утверждение (1) верное, в противном случае запишите 0; на втором месте запишите 1, если утверждение (2) верное, в противном случае запишите 0; и т.д.
Ответ: 111
Вопрос 3
Выполнен
Баллов: 1,00 из 1,00
Двудольный обыкновенный граф задан матрицей весов
3 |
4 |
3 |
2 |
1 |
5 |
6 |
3 |
7 |
5 |
2 |
1 |
2 |
3 |
4 |
6 |
Эта матрица была преобразована к виду, пригодному для начала работы алгоритма решения задачи о назначениях (то есть так, чтобы преобразованной матрице соответствовал граф с ребрами неотрицательного веса, в котором каждой вершине инцидентно по крайней мере одно ребро нулевого веса). Чему равна сумма элементов главной диагонали преобразованной матрицы?
Ответ: 8
Вопрос 4
Выполнен
Баллов: 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 |
|
|
|
|
|
Вопрос 5
Выполнен
Баллов: 1,00 из 1,00
Дан полный двудольный граф с вершинами 1,2,3,4,5 в первой доле и a, b, c, d, e во второй. На графе задано паросочетание {1e, 2b, 3c, 4d}. Укажите цепи, которые являются чередующимися относительно этого паросочетания (цепи заданы последовательностью вершин):
(1)2b3d5
(2)1a2c4e
(3)b2c3d4e
(4)1e
Ответ дайте в формате последовательности 0 и 1 (например, 0011): на первом месте запишите 1, если цепь (1) чередующаяся, в противном случае запишите 0; на втором месте запишите 1, если цепь (2) чередующаяся, в противном случае запишите 0; и т.д.
Ответ: 0011
Вопрос 6
Выполнен
Баллов: 1,00 из 1,00
Ориентированный граф задан матрицей смежности
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
Производится поиск в ширину из вершины 1. При этом действует договоренность: концы дуг, выходящие из рассматриваемой на данном шаге вершины, заносятся в очередь в порядке их нумерации в матрице смежности (например, если в очереди находится только вершина 1 и она – начало дуг 13 и 15, то в начале в очередь включаем вершину 3, потом – вершину 5). Перечислите вершины в порядке занесения их в очередь при поиске ширину из вершины 1.
Ответ дайте в формате последовательности чисел без пробелов, скобок и запятых (например, 593…).
Ответ: 1243675
Вопрос 7
Выполнен
Баллов: 1,00 из 1,00
Дерево задано кодом из натуральных чисел 213167. На дереве задано паросочетание {24, 35, 67}. Относительно него сформулированы три утверждения. Верны ли они?
(1)парососочетание наибольшее
(2)паросочетание максимальное
(3)паросочетание совершенное.
Ответ дайте в формате последовательности 0 и 1 (например, 001): на первом месте запишите 1, если утверждение (1) верное, в противном случае запишите 0; на втором месте запишите 1, если утверждение (2) верное, в противном случае запишите 0; и т.д.
Ответ: 010
Вопрос 8
Выполнен
Баллов: 1,00 из 1,00
Дан двудольный граф с вершинами 1,2,3,4 в доле X, вершинами a, b, c, d в доле Y и матрицей весов
0 |
2 |
0 |
0 |
1 |
0 |
3 |
2 |
2 |
0 |
1 |
3 |
2 |
0 |
4 |
1 |
Построен остовный подграф этого графа, содержащий только ребра нулевого веса, в нем выбрано максимальное паросочетание {1a, 3b} и проведена одна итерация алгоритма построения совершенного паросочетания. В результате получено новое весовое отображение графа. Чему равна сумма элементов, стоящих в новой матрице весов на главной диагонали?
Ответ: 0
Вопрос 9
Выполнен
Баллов: 0,00 из 1,00
Дан двудольный граф с вершинами a, b, c, d в доле X и 1,2,3,4 в доле Y, а также ребрами a1, a2, a4, b2, b3, b4, c2, c3, c4, d3. Выбрано максимальное паросочетание, включающее ребра a1, c2, d3, и в результате одной итерации алгоритма построения наибольшего паросочетания в двудольном графе найдено новое паросочетание. Укажите вершины смежные вершинам a, b, c, d, в найденном паросочетании.
Ответ дайте в формате последовательности чисел (например, 1034): на первом месте запишите номер вершины, смежной с вершиной a (если смежной вершины нет, запишите 0); на втором месте запишите номер вершины, смежной с вершиной b (если смежной вершины нет, запишите 0);и т.д.
Ответ: 1423
Вопрос 10
Выполнен
Баллов: 1,00 из 1,00
Дан полный граф с вершинами 1,2,3,4,5. Укажите, являются указанные множества ребер паросочетаниями или нет:
(1)12, 34
(2)12, 13, 14, 15
(3)13
(4)14, 23, 54
Ответ дайте в формате последовательности 0 и 1 (например, 0011): на первом месте запишите 1, если множество (1) является паросочетанием, в противном случае запишите 0; на втором месте запишите 1, если множество (2) является паросочетанием, в противном случае запишите 0; и т.д.
Ответ: 1010
◄ Видеозапись лекции "Паросочетания в двудольных графах"
Перейти на...
Текст лекции "Задание булевых функций графами" ►