Главная / Алгоритмы и дискретные структуры /
Дискретный анализ и теория вероятностей / Тест 3
Дискретный анализ и теория вероятностей - тест 3
Упражнение 1:
Номер 1
Что допускается в простом графе?
Ответ:
 (1) кратные ребра 
 (2) ничего из перечисленного 
 (3) петли 
 (4) ориентация ребер 
Номер 2
Что допускается в псевдографе?
Ответ:
 (1) кратные ребра 
 (2) ничего из перечисленного 
 (3) петли 
 (4) ориентация ребер 
Номер 3
Что допускается в мультиграфе?
Ответ:
 (1) кратные ребра 
 (2) ничего из перечисленного 
 (3) петли 
 (4) ориентация ребер 
Упражнение 2:
Номер 1
В теории графов дерево это - ...
Ответ:
 (1) связанный ациклический граф 
 (2) связанный циклический граф 
 (3) несвязанный ациклический граф 
 (4) несвязанный унициклический граф 
Номер 2
Сколько ребер имеет дерево с 10 вершинами?
Ответ:
 9 
Номер 3
Как у дерева соотносятся число вершин и число ребер?
Ответ:
 (1) число ребер и число вершин равны 
 (2) число ребер на 1 больше числа вершин 
 (3) число ребер на 1 меньше числа вершин 
 (4) число ребер на 2 меньше числа вершин 
 (5) число ребер на 2 больше числа вершин 
Упражнение 3:
Номер 1
Чему равно - количество различных (как графы с занумерованными вершинами) деревьев на вершинах?
Ответ:
 
(1)  
 
(2)  
 
(3)  
 
(4)  
Номер 2
Чему равно - количество различных (как графы с занумерованными вершинами) деревьев на вершинах?
Ответ:
 125 
Номер 3
Чему равно - количество различных (как графы с занумерованными вершинами) деревьев на вершинах?
Ответ:
 16 
Упражнение 4:
Номер 1
На рисунке представлено дерево. Укажите вершину, которую согласно алгоритму в коде Прюфера, следует удалить в первую очередь.
Ответ:
 2 
Номер 2
На рисунке представлено дерево. Укажите код Прюфера, соответствующий данному дереву (записывать как число без запятых и пробелов).
Ответ:
 1455 
Номер 3
На рисунке представлено дерево. Сколько символов содержит код Прюфера, соответствующий данному дереву.
Ответ:
 4 
Упражнение 5:
Номер 1
Сколько ребер у связного унициклического графа с 5 вершинами?
Ответ:
 5 
Номер 2
Сколько циклов содержит связный унициклический граф с 5 вершинами?
Ответ:
 1 
Номер 3
Что допускается в унициклическом графе?
Ответ:
 (1) кратные ребра 
 (2) один цикл 
 (3) циклы 
 (4) ориентация ребер 
Упражнение 6:
Номер 1
Какой граф соответствует коду Прюфера 453376?
Ответ:
 
(1)  
 
(2)  
 
(3)  
Номер 2
Какой граф соответствует коду Прюфера 171716?
Ответ:
 
(1)  
 
(2)  
 
(3)  
Номер 3
Какой граф соответствует коду Прюфера 441666?
Ответ:
 
(1)  
 
(2)  
 
(3)  
Упражнение 7:
Номер 1
Какова асимптотическая оценка количества унициклических графов ?
Ответ:
 
(1)  
 
(2)  
 
(3)  
 
(4)  
Номер 2
Какова точная оценка количества унициклических графов ?
Ответ:
 
(1)  
 
(2)  
 
(3)  
 
(4)  
Номер 3
Чему равна асимптотическая оценка выражения ?
Ответ:
 
(1)  
 
(2)  
 
(3)  
 
(4)  
Упражнение 8:
Номер 1
В формуле оценки количества различных (как графы с занумерованными вершинами) унициклических графов с вершинами и циклом, построенным на вершинах выражение показывает...
Ответ:
 (1) число способов построить цикл на выбранных вершинах 
 (2) число способов зафиксировать вершины для цикла 
 (3) число способов зафиксировать цикл 
 
(4) число различных (как графы с занумерованными вершинами) лесов с
деревьями с общим количеством вершин
, такое, что первое дерево содержит вершину 1, второе – вершину 2, …,
-ое дерево содержит вершину
 
Номер 2
В формуле оценки количества различных (как графы с занумерованными вершинами) унициклических графов с вершинами и циклом, построенным на вершинах выражение показывает...
Ответ:
 (1) число способов построить цикл на выбранных вершинах 
 (2) число способов зафиксировать вершины для цикла 
 (3) число способов зафиксировать цикл 
 
(4) число различных (как графы с занумерованными вершинами) лесов с
деревьями с общим количеством вершин
, такое, что первое дерево содержит вершину 1, второе – вершину 2, …,
-ое дерево содержит вершину
 
Номер 3
В формуле оценки количества различных (как графы с занумерованными вершинами) унициклических графов с вершинами и циклом, построенным на вершинах выражение показывает...
Ответ:
 (1) число способов построить цикл на выбранных вершинах 
 (2) число способов зафиксировать вершины для цикла 
 (3) число способов зафиксировать цикл 
 
(4) число различных (как графы с занумерованными вершинами) лесов с
деревьями с общим количеством вершин
, такое, что первое дерево содержит вершину 1, второе – вершину 2, …,
-ое дерево содержит вершину
 
Упражнение 9:
Номер 1
В формуле оценки количества различных (как графы с занумерованными вершинами) унициклических графов с вершинами и циклом, построенным на вершинах выражение показывает...
Ответ:
 (1) число способов построить цикл на выбранных вершинах 
 (2) число способов зафиксировать вершины для цикла 
 (3) число способов зафиксировать цикл 
 
(4) число различных (как графы с занумерованными вершинами) лесов с
деревьями с общим количеством вершин
, такое, что первое дерево содержит вершину 1, второе – вершину 2, …,
-ое дерево содержит вершину
 
Номер 2
В формуле оценки количества различных (как графы с занумерованными вершинами) унициклических графов с вершинами и циклом, построенным на вершинах выражение показывает...
Ответ:
 (1) число способов построить цикл на выбранных вершинах 
 (2) число способов зафиксировать вершины для цикла 
 (3) число способов зафиксировать цикл 
 
(4) число различных (как графы с занумерованными вершинами) лесов с
деревьями с общим количеством вершин
, такое, что первое дерево содержит вершину 1, второе – вершину 2, …,
-ое дерево содержит вершину
 
Номер 3
Какова точная оценка количества унициклических графов ?
Ответ:
 
(1) вершинах
 
 
(2) вершинах
 
 
(3) вершинах
 
 
(4) вершинах
 
Упражнение 10:
Номер 1
При построении асимптотической оценки количества различных (как графы с занумерованными вершинами) унициклических графов с вершинами и циклом, построенным на вершинах, величина заменяется на сумму двух слагаемых Чему равна асимптотическая оценка ?
Ответ:
 (1) 0 
 (2) 1 
 
(3)  
 
(4)  
Номер 2
При построении асимптотической оценки количества различных (как графы с занумерованными вершинами) унициклических графов с вершинами и циклом, построенным на вершинах, величина заменяется на сумму двух слагаемых .Выберите операции и свойства, которые использовались для нахождения асимптотической оценки
Ответ:
 
(1) замена
 
 (2) сумма арифметической прогрессии 
 (3) сумма геометрической прогрессии 
 
(4) свойство
 
 
(5) свойство
 
Номер 3
При построении асимптотической оценки количества различных (как графы с занумерованными вершинами) унициклических графов с вершинами и циклом, построенным на вершинах, величина заменяется на сумму двух слагаемых .При указанном интервале суммирования для , что является нижней оценкой величины ?
Ответ:
 
(1)  
 
(2)  
 (3) 0 
 (4) 1 
Упражнение 11:
Номер 1
При построении асимптотической оценки количества различных (как графы с занумерованными вершинами) унициклических графов с вершинами и циклом, построенным на вершинах, величина заменяется на сумму двух слагаемых Чему равна асимптотическая оценка ?
Ответ:
 (1) 0 
 (2) 1 
 
(3)  
 
(4)  
Номер 2
При построении асимптотической оценки количества различных (как графы с занумерованными вершинами) унициклических графов с вершинами и циклом, построенным на вершинах, величина заменяется на сумму двух слагаемых .Выберите операции и свойства, которые использовались для нахождения асимптотической оценки
Ответ:
 
(1) замена
 
 (2) сумма арифметической прогрессии 
 (3) сумма геометрической прогрессии 
 
(4) свойство
 
 
(5) свойство
 
Номер 3
Чему равно значение выражения ?
Ответ:
 
(1)  
 
(2)  
 
(3)  
 
(4)  
Упражнение 12:
Номер 1
Определите число различных (как графы с занумерованными вершинами) лесов с 3 деревьями с общим количеством вершин 6, такое, что первое дерево содержит вершину 1, второе – вершину 2, третье дерево содержит вершину 3.
Ответ:
 108 
Номер 2
Определите число различных (как графы с занумерованными вершинами) лесов с 4 деревьями с общим количеством вершин 6, такое, что первое дерево содержит вершину 1, второе – вершину 2, третье дерево содержит вершину 3, четвертое дерево содержит вершину 4.
Ответ:
 24 
Номер 3
Определите число различных (как графы с занумерованными вершинами) лесов с 2 деревьями с общим количеством вершин 6, такое, что первое дерево содержит вершину 1, второе – вершину 2.
Ответ:
 216