Личный кабинет / Мои курсы / ВМ-1 - Дискретная математика (01.03.04, #807)
/Тема 9. Циклы и мосты, цикломатическое число. Фундаментальная система циклов графа.
/Тест по теме "Циклы и мосты, цикломатическое число. Фундаментальная система циклов графа" для групп ПМ-21,22, ИВТ-21,22,23
Тест начат Sunday, 6 November 2022, 02:36
Состояние Завершенные
Завершен Sunday, 6 November 2022, 03:02
Прошло 26 мин. 2 сек.
времени
Баллы 12,00/16,00
Оценка 1,13 из 1,50 (75%)
Вопрос 1
Выполнен
Баллов: 1,00 из 1,00
Чему равно цикломатическое число полного двудольного0 графа с пятью вершинами в одной доле и пятью вершинами в другой?0
Ответ: 16
Вопрос 2
Выполнен
Баллов: 1,00 из 1,00
Найти сумму двух обобщенных циклов неориентированного графа, если известно, что в первый из0них входят ребра с номерами 2,3,4,5,6,8 а во второй – ребра с номерами 4,6,7,9. В ответе перечислить номера ребер получившегося цикла в порядке возрастания без0пробелов и запятых (например, 245). 0
Ответ: 235789
Вопрос 3
Выполнен Баллов: 1,00 из 1,00
Рассматривается граф, полученный в результате0декартового произведения графа |
на граф |
.Какое максимальное |
||
число ребер может содержать простой0цикл на этом графе?0 |
|
|
||
|
|
|
|
|
Ответ: |
8 |
|
|
|
|
|
|
|
|
Вопрос 4
Выполнен
Баллов: 0,00 из 1,00
Неориентированный граф задан матрицей смежности 0
0 0 0 0 0 0
0 0 0 0 1 0
0 0 2 0 1 0
0 0 0 0 0 0
0 1 1 0 2 0
0 0 0 0 0 0
Сколько различных классов эквивалентности по бинарному отношению0достижимости имеется в этом графе?0
Ответ: 3
Вопрос 5
Выполнен
Баллов: 1,00 из 1,00
Сколько ребер являются мостами в полном графе с0шестью вершинами?0
Ответ: 0
Вопрос 6
Выполнен
Баллов: 0,00 из 1,00
Неориентированный граф задан матрицей смежности 0
0 1 1 1
1 0 3 1
1 3 0 1
1 1 1 0
Какова0размерность пространства циклов этого графа?0
Ответ: 6
Вопрос 7
Выполнен
Баллов: 1,00 из 1,00
Неориентированный граф задан матрицей инцидентности 0
0 0 0 0 1 1 0 0
0 1 1 1 0 1 1 0
1 0 1 1 1 0 0 1
1 1 0 0 0 0 0 0
0 0 0 0 0 0 1 1
Рассмотрим путь на графе:
2 2 4 1 3 3 2 7 5 8 3 501 6 2 (подчеркнутые числа соответствуют номерам ребер, остальные –0номерам вершин) Какие из утверждений верные?
(1)Это замкнутый путь
(2)Это цепь
(3)Это простая цепь
(4)Это цикл
(5)Это простой цикл
Ответ дайте в формате последовательности 0 и 1 (например, 00111): на0первом месте запишите 1, если утверждение (1) верное, в противном случае0запишите 0; на втором месте запишите 1, если утверждение (2) верное, в0противном случае запишите 0; и
т.д.0
Ответ: 11010
Вопрос 8
Выполнен
Баллов: 1,00 из 1,00
Известно, что в фундаментальную систему циклов0графа входит 6 циклов. Сколько всего обобщенных циклов на этом графе?0
Ответ: 64
Вопрос 9
Выполнен
Баллов: 1,00 из 1,00
Известно, что в графе 29 вершин и 18 ребер. Какое0наименьшее число компонент связности может иметь такой граф?0
Ответ: 11
Вопрос 10
Выполнен
Баллов: 1,00 из 1,00
Неориентированный граф задан матрицей смежности 0
0 1 3 0
1 2 0 2
3 0 2 1
0 2 1 0
Какова0размерность пространства циклов этого графа?0
Ответ: 6
Вопрос 11
Выполнен
Баллов: 0,00 из 1,00
Диаграмма неориентированного графа состоит из0сторон правильного семиугольника ABCDEFK и шести его диагоналей AC, CE, EA, CK, KB, BF. Какое минимальное число0 ребер нужно удалить из графа, чтобы получить граф с числом связности равным трем?0
Ответ: 8
Вопрос 12
Выполнен
Баллов: 1,00 из 1,00
Граф задан матрицей смежности 0
0 0 0 0 1 0
0 0 0 0 3 0
0 0 0 1 0 0
0 0 1 0 0 0
1 3 0 0 0 1
0 0 0 0 1 0
Сколько компонент связности имеет подграф,0порожденный множеством вершин с номерами 1,2,3,4,6?0
Ответ: 4
Вопрос 13
Выполнен
Баллов: 1,00 из 1,00
Какие утверждения верны?
(1)В связном графе число ребер превышает число вершин.
(2)Если после удалении ребра0число связности графа увеличилось, то удаленное ребро входило в цикл.
(3)Для некоторых графов бинарное отношение достижимости0является отношением порядка.
(Ответ дайте в формате последовательности 0 и 1 (например, 001): на0первом месте запишите 1, если утверждение (1) верное, в противном случае0запишите 0; на втором месте запишите 1, если утверждение (2) верное, в0противном случае запишите 0; и
т.д.0
Ответ: 001
Вопрос 14
Выполнен Баллов: 1,00 из 1,00
Чему равно цикломатическое число полного графа с 250вершинами?0 |
|
|||
|
|
|
|
|
Ответ: |
|
276 |
|
|
|
|
|
|
|
|
|
|
|
|
Вопрос 15 |
|
|
|
|
Выполнен |
|
|
|
|
Баллов: 0,00 из 1,00 |
|
|||
|
|
|
|
|
Граф имеет четыре компоненты связности, каждая из0которых изоморфна полному двудольному графу |
. Из0каждой |
|||
компоненты связности удалили по два ребра. Чему равно число связности0получившегося графа?0 |
|
|||
|
|
|
|
|
Ответ: |
|
6 |
|
|
|
|
|
|
|
Вопрос 16
Выполнен
Баллов: 1,00 из 1,00
Диаграмма неориентированного графа состоит из0сторон правильного семиугольника ABCDEFK и трех его диагоналей AC, EA, BF. Сколько циклов входит в фундаментальную систему циклов графа?0
Ответ: 4
◄ Тест по теме "Циклы и мосты, цикломатическое число. Фундаментальная система циклов графа" для групп ПИН-21-26
Перейти на...
Текст лекции "Деревья" ►