Тесты / 9 / vpvp

Личный кабинет / Мои курсы / ВМ-1 - Дискретная математика (01.03.04, #807)

/Тема 9. Циклы и мосты, цикломатическое число. Фундаментальная система циклов графа.

/Тест по теме "Циклы и мосты, цикломатическое число. Фундаментальная система циклов графа" для групп ПМ-21,22, ИВТ-21,22,23

Тест начат Sunday, 6 November 2022, 02:20

Состояние Завершенные

Завершен Sunday, 6 November 2022, 02:35

Прошло 15 мин. 49 сек.

времени

Баллы 10,00/16,00

Оценка 0,94 из 1,50 (63%)

Вопрос 1

Выполнен

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

Неориентированный граф задан матрицей смежности 0

0 2 1 0

2 0 1 1

1 1 0 1

0 1 1 0

Какова0размерность пространства циклов этого графа?0

Ответ: 4

Вопрос 2

Выполнен

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

Неориентированный граф задан матрицей смежности 0

0 2 0 0 0 0

2 0 0 0 0 0

Сколько различных классов эквивалентности по бинарному отношению0достижимости имеется в этом графе?0

Ответ: 3

Вопрос 3

Выполнен

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

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

(1)Число вершин любого графа не0превышает сумму числа ребер и количества компонент связности.

(2)Если все ребра графа мосты,0то граф не содержит циклов.

(3)Если на множестве вершин произвольного графа ввести0бинарное отношение достижимости, то оно не будет антисимметричным.

(Ответ дайте в формате последовательности 0 и 1 (например, 001): на0первом месте запишите 1, если утверждение (1) верное, в противном случае0запишите 0; на втором месте запишите 1, если утверждение (2) верное, в0противном случае запишите 0; и

т.д.0

Ответ: 110

Вопрос 4

Выполнен

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

Неориентированный граф задан матрицей инцидентности 0

0 0 0 0 0 0 1 1

1 0 1 0 0 1 1 0

0 0 0 0 1 1 0 1

0 0 0 1 1 0 0 0

0 1 1 1 0 0 0 0

1 1 0 0 0 0 0 0

Найти сумму двух обобщенных циклов, в первый из0которых входят ребра с номерами 3,4,5,6, во второй – ребра с номерами 1,2,4,5,6.0В ответе перечислить номера ребер получившегося цикла в порядке возрастания без0пробелов и запятых (например, 245). 0

Ответ: 123

Вопрос 5

Выполнен

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

Чему равно цикломатическое число полного графа с 19 вершинами?0

Ответ: 153

Вопрос 6

Выполнен

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

Граф задан матрицей смежности 0

0 0 0 1 0 0

0 0 0 0 0 1

0 0 2 0 0 0

1 0 0 0 1 0

0 0 0 1 0 2

0 1 0 0 2 0

Сколько компонент связности имеет подграф,0порожденный множеством вершин с номерами 1,2,3,4,6?0

Ответ: 3

Вопрос 7

Выполнен

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

Диаграмма неориентированного графа состоит из0сторон правильного семиугольника ABCDEFK и шести его диагоналей AC, CE, EA, CF, KB, KD. Какое минимальное число0 ребер нужно удалить из графа, чтобы получить граф с большим числом связности?0

Ответ: 8

Вопрос 8

Выполнен

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

Какое наибольшее число мостов может иметь0двудольный граф с двумя вершинами в одной доле и тремя в другой?0

Ответ: 4

Вопрос 9

Выполнен

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

Граф имеет три компоненты связности, первая из0которых есть полный граф с двумя вершинами, вторая – полный граф с тремя вершинами,0третья – полный граф с четырьмя вершинами. Из каждой компоненты связности0удалили по одному ребру. Чему равно число связности получившегося графа?0

Ответ: 4

Вопрос 10

Выполнен

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

Неориентированный граф задан матрицей смежности 0

0 2 1 1

2 0 1 0

1 1 0 1

1 0 1 2

Какова0размерность пространства циклов этого графа?0

Ответ: 4

Вопрос 11

Выполнен

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

Известно, что в фундаментальную систему циклов0графа входит четыре цикла. Сколько всего обобщенных циклов на этом графе?0

Ответ: 16

Вопрос 12

Выполнен

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

Диаграмма неориентированного графа состоит из0сторон правильного семиугольника ABCDEFK и шести его диагоналей CE, EA, KB, KD, BF, FD. Сколько циклов входит в фундаментальную систему циклов графа?0

Ответ: 6

Вопрос 13

Выполнен

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

Известно, что в графе с 11 компонентами связности056 вершин. Какое наименьшее число ребер может иметь такой граф?0

Ответ: 45