игра брюс 2048
Главная / Алгоритмы и дискретные структуры / Графы и их применение / Тест 11

Графы и их применение - тест 11

Упражнение 1:
Номер 1 
Что называется представлением дерева?

Ответ:

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

 (2) способ раскраски дерева 

 (3) выбор направления обхода дерева 

 (4) подсчет листьев и корневых вершин дерева 

Номер 2 
Какие представления деревьев правильны?

Ответ:

 (1) представление с помощью матрицы смежности 

 (2) представление с помощью списков смежности 

 (3) представление с помощью списка ребер и кода Прюфера 

 (4) дерево задается перечислением пар (vi,vj) или троек (vi,vj,uk), если дополнительно нужна нумерация ребер. Здесь vi,vj - вершины дерева 

Номер 3 
Пусть задано дерево с  пронумерованными вершинами. Спрашивается: сколько существует таких разных деревьев?

Ответ:

 (1) деревьев с n пронумерованными вершинами ровно столько, сколько можно образовать последовательностей вида (v1,v2,...,vn-2) длины n-2, элементы которых выбираются из элементов множества M={1,2,3,...,n-1,n} 

 (2) деревьев с n пронумерованными вершинами ровно столько, сколько можно образовать последовательностей вида (v1,v2,...,vn-2) длины n-2, элементы которых выбираются из элементов множества vi∈M 

 (3) деревьев с n пронумерованными вершинами ровно столько, сколько можно образовать последовательностей вида (v1,v2,...,vn-2) длины 10 

 (4) деревьев с n пронумерованными вершинами ровно столько, сколько можно образовать последовательностей вида (v1,v2,...,vn-2) длины n-2, элементы которых выбираются из элементов множества vi∈5 

Упражнение 2:
Номер 1 
Что нужно сделать, чтобы произвольный граф G  преобразовать в дерево?

Ответ:

 (1) убрать циклы 

 (2) убрать мосты 

 (3) добавить циклы 

 (4) добавить мосты 

Номер 2 
Сколько корневых вершин может быть у дерева?

Ответ:

 (1) одна 

 (2) две 

 (3) нет корневых вершин 

 (4) столько, сколько вершин, для которых максимальное из расстояний до других вершин равно радиусу графа 

Номер 3 
Можно ли построить дерево, используя множество целых чисел в качестве вершин графа?

Ответ:

 (1) можно построить дерево, вершины которого взяты из множества целых чисел 

 (2) можно построить дерево, вершины которого взяты из множества простых чисел 

 (3) можно построить столько деревьев с n вершинами, сколько последовательностей вида (v1,v2,...,vn-2) длины n-2 , элементы которых выбираются из элементов множества M={1,2,3,...,n-1,n} 

 (4) можно построить столько деревьев с вершинами сколько последовательностей вида (v1,v2,...,vn-2) длины n-2 , элементы которых выбираются из элементов множества простых чисел мощностью n 

Упражнение 3:
Номер 1 
Из чего состоит остовной лес?

Ответ:

 (1) из остовных деревьев 

 (2) из компонент, в которых нет циклов 

 (3) из компонент, в которых нет мостов 

 (4) остовной лес - это частный случай остовного дерева 

Номер 2 
Расстоянием d(vx,vy)  между вершинами  графа G  называем длину кратчайшего пути, их  соединяющего. Наибольшее из таких d(vx,vy)  называем диаметром G, наименьшее – радиусом. Может ли  у какой – то вершины дерева максимальное из расстояний до других вершин равняться радиусу?

Ответ:

 (1) да 

 (2) нет 

 (3) для корневых вершин 

 (4) для листьев дерева 

Номер 3 
Любое дерево имеет либо одну, либо две корневые вершины. Как корневые вершины дерева расположены относительно друг друга?

Ответ:

 (1) корневые вершины – смежные 

 (2) корневые вершины не могут быть смежными 

 (3) корневые вершины расположены на расстояние диаметра 

 (4) корневые вершины расположены на расстоянии радиуса 



Главная / Алгоритмы и дискретные структуры / Графы и их применение / Тест 11