Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

Тесты в moddle / Тема 12. Обходы графов. Раскраска графов / Тест по теме _Обходы графов. Раскраска графов_ для групп ПИН-21-26_ просмотр попытки

.pdf
Скачиваний:
7
Добавлен:
24.11.2023
Размер:
152.29 Кб
Скачать

Личный кабинет / Мои курсы / ВМ-1 - Дискретная математика (общий, #807) / Тема 12. Обходы графов. Раскраска графоов

/ Тест по теме "Обходы графов. Раскраска графов" для групп ПИН-21-26

Тест начат Friday, 24 November 2023, 14:20

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

Завершен Friday, 24 November 2023, 15:16

Прошло 55 мин. 51 сек.

времени

Баллы 15,00/15,00

Оценка 1,50 из 1,50 (100%)

Вопрос 1

Выполнен

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

Дан плоский граф с вершинами 1, 2, 3, 4 и ребрами с концами 1 и 2, 1 и 3, 1 и 4, 2 и 3, 3 и 4. Постройте геометрически двойственный ему граф.

В ответе перечислите в порядке неубывания без пробелов, скобок и запятых степени вершин построенного геометрически двойственного графа.

Ответ: 334

Вопрос 2

Выполнен

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

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

(1)Если хроматическое число графа равно пяти, то граф не имеет плоской укладки.

(2)Если граф гамильтонов, то он и эйлеров.

(3)Если в плоской укладке ненулевого планарного графа границы всех граней состоят из четного числа ребер, то граф двудольный.

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

Ответ: 101

Вопрос 3

Выполнен

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

Дан граф с вершинами 1, 2, 3, 4, 5 и ребрами с концами 1 и 2, 1 и 4, 1 и 5, 4 и 5, 2 и 4, 2 и 3, 3 и 4. Существует ли на графе эйлерова цепь?

Если такой цепи не существует, то в ответе укажите 0; если такая цепь есть, что в ответе укажите сумму номеров вершин, являющихся ее концами.

Ответ: 3

Вопрос 4

Выполнен

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

Найдите хроматические числа графов:

(1)

(2) ненулевой лес с пятью компонентами связности

(3)

В ответе перечислите в соответствующем порядке хроматические числа графов без пробелов, скобок и запятых (пример формата ответа 342)

Ответ: 225

Вопрос 5

Выполнен

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

Укажите графы, на которых есть гамильтонова цепь.

(1)

2) Полный граф с семью вершинами, из которого удалили пять ребер, инцидентных одной из вершин

(3) Граф, полученный в результате декартова произведения двух цепей длины два

Ответ запишите в формате последовательности 0 и 1 без скобок, пробелов и запятых (например, 001): на первом мете запишите 1, если на графе (1) есть гамильтонова цепь, в противном случае запишите 0; на втором месте запишите 1, если на графе (2) есть гамильтонова цепь, в противном случае запишите 0; и т.д.

Ответ: 011

Вопрос 6

Выполнен

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

Укажите графы, на которых есть гамильтонов цикл.

(1)Полный граф с 36 ребрами.

(2)Полный двудольный граф, сумма степеней вершин которого равна 30.

(3)Подграф, порожденный подмножеством из пяти вершин полного двудольного графа

Ответ запишите в формате последовательности 0 и 1 без скобок, пробелов и запятых (например, 001): на первом месте запишите 1, если на графе (1) есть гамильтонов цикл, в противном случае запишите 0; на втором месте запишите 1, если на графе (2) есть гамильтонов цикл, в противном случае запишите 0; и т.д.

Ответ: 100

Вопрос 7

Выполнен

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

Укажите графы, которые являются эйлеровыми.

(1)

 

 

(2)

 

 

(3)

граф, равный декартовому произведению графа

на граф

Ответ запишите в формате последовательности 0 и 1 без скобок, пробелов и запятых (например, 001): на первом меcте запишите 1, если граф (1) эйлеров, в противном случае запишите 0; на втором месте запишите 1, если граф (2) эйлеров, в противном случае запищите 0; и т.д.

Ответ: 010

Вопрос 8

Выполнен

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

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

0

0

1

1

1

0

0

1

1

0

0

1

1

0

0

0

1

1

1

1

0

1

0

0

Чему равно хроматическое число графа?

Ответ: 4

Вопрос 9

Выполнен

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

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

0

1

1

1

1

1

0

1

1

1

1

1

0

0

1

1

1

0

0

1

1

1

1

1

0

Чему равно хроматическое число графа?

Ответ: 4

Вопрос 10

Выполнен

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

Укажите графы, множество ребер которых можно разбить на циклы.

(1)Граф, полученный путем удаления из полного графа с шестью вершинами двух смежных ребер.

(2)Граф, полученный путем удаления из полного графа с пятью вершинами ребер цикла длины 3.

(3)Полный граф с 28 ребрами.

Ответ запишите в формате последовательности 0 и 1 без скобок, пробелов и запятых (например, 001): на первом меcте запишите 1, если для графа (1) разбиение возможно, в противном случае запишите 0; на втором месте запишите 1, если для графа (2) разбиение возможно, в противном случае запишите 0; и т.д.

Ответ: 010

Вопрос 11

Выполнен

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

Дерево имеет бинарный код 0010101011. Сколько ребер этого графа являются перешейками?

Ответ: 0

Вопрос 12

Выполнен

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

Граф представляет собой незамкнутую простую цепь с 24 вершинами. Сколько ребер этого графа являются перешейками?

Ответ: 21

Вопрос 13

Выполнен

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

Укажите бихроматичные графы:

(1)Граф имеет ребра и является двудольным.

(2)Граф полный, число его вершин больше двух.

(3)Граф обыкновенный, связный, у него есть ребра и их число на единицу меньше числа вершин.

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

Ответ: 101

Вопрос 14

Выполнен

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

Дерево имеет код Прюффера 27277. Сколько ребер этого графа являются перешейками?

Ответ: 1

Вопрос 15

Выполнен

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

Выберите графы, которые не являются эйлеровыми, но являются гамильтоновыми.

(1)

(2)

(3)

Ответ запишите в формате последовательности 0 и 1 без скобок, пробелов и запятых (например, 001): на первом месте запишите 1, если граф (1) не эйлеров, но гамильтонов, в противном случае запишите 0; на втором месте запишите 1, если граф

(2) не эйлеров, но гамильтонов в противном случае запишите 0; и т.д.

Ответ: 101

◄ Тест по теме "Обходы графов. Раскраска графов" для групп ПМ-21,22, ИВТ-21,22,23

Перейти на...

Текст лекции "Ориентированные графы: первичные понятия. Отыскание кратчайших путей на графе" ►