Главная / Алгоритмы и дискретные структуры /
Графы и их применение / Тест 2
Номер 3
Ответ:
Графы и их применение - тест 2
Упражнение 1:
Номер 1
Ответ:
Номер 1
Можно получить несколько различных матриц смежности данного графа?
Ответ:
(1) да
(2) нет
(3) только для ориентированного графа
(4) только для графа, степени вершин которого равны 1
Номер 2
Ответ:
Чему равна сумма чисел в любой строке или столбце матрицы смежности?
Ответ:
(1) степени соответствующей вершины
(2) не имеет никакого отношения к степеням вершин графа
(3) степени соответствующей вершины пустого графа
(4) степени соответствующей вершины регулярного графа
Что называется обхватом графа?
Ответ:
(1) длина его кратчайшего цикла
(2) число вершин в графе
(3) число ребер и вершин графа
(4) его радиус
Упражнение 2:
Номер 1
Ответ:
Номер 1
Какой граф называется регулярным?
Ответ:
(1) если множество его вершин можно разбить на два непересекающихся подмножества
V1 и V2 так, что каждое ребро в G соединяет какую-нибудь вершину из V1 с какой-либо вершиной из V2, тогда G называем двудольным графом
(2) граф, у которого все вершины имеют одну и ту же степень, называется регулярным графом
(3) простой граф называется регулярным, если он несвязный
(4) простой граф
G(V,G) называется регулярным, если он связный
Номер 2
Ответ:
Что называется каркасом графа G?
Ответ:
(1) остов дерева
(2) остов
(3) простая цепь, если все ее вершины висячие
(4) вершина с петлей
Номер 3
Ответ:
Какой граф называется регулярным степени r?
Ответ:
(1) граф, у которого все вершины имеют одну и ту же степень
r
(2) если у него число вершин равно числу ребер
(3) если он имеет только висячие вершины
(4) если он не имеет петель
Упражнение 3:
Номер 1
Ответ:
Номер 1
Что называется мостом графа?
Ответ:
(1) все ребра графа
(2) в графе
G называется мостом пара V(G),E(G) , где V(G) - непустое конечное множество элементов, называемых вершинами, а E(G) - конечное семейство неупорядоченных пар элементов из V(G) (не обязательно различных), называемых V(G),E(G) ребрами
(3) такая пара, что
E⊆V×V. Элементы множества E для графа называются дугами
(4) ребро
{a,b} называется мостом графа G, если в графе, полученном после удаления из G ребра {a,b}, вершины a и b оказываются несвязными
Номер 2
Ответ:
Что называется лесом?
Ответ:
(1) полный ориентированный граф, каждая пара вершин которого соединена в точности одним ориентированным ребром
(2) полный ориентированный граф с неориентированными ребрами
(3) ориентированный граф, у которого число вершин строго равно числу ребер
(4) несвязный граф, представляющий объединение деревьев
Номер 3
Ответ:
Какой граф называется помеченным?
Ответ:
(1) если существует такая последовательность ребер, ведущая от
v1 к v2, в которой каждые два соседних ребра имеют общую вершину и никакое ребро не встречается более одного раза
(2) если существует последовательность вершин от
v1 до v2
(3) если его ребра пронумерованы
(4) если все его вершины "помечены" целыми числами от 1 до n