Главная / Алгоритмы и дискретные структуры /
Графы и алгоритмы / Тест 4
Номер 3
Ответ:
Графы и алгоритмы - тест 4
Упражнение 1:
Номер 1
Ответ:
Номер 1
В процессе выполнения процедуры поиска в ширину вершины графа делятся на новые, открытые и закрытые. Может ли в графе существовать ребро, соединяющее
Ответ:
(1) новую вершину с открытой?
(2) открытую вершину с закрытой?
(3) новую вершину с закрытой?
(4) две открытые вершины?
Номер 2
Ответ:
Алгоритм поиска в ширину применяется к дереву, заданному списками смежности. Какие оценки трудоемкости справедливы в этом случае?
Ответ:
(1)
(2)
(3)
(4)
Алгоритм поиска в ширину применяется к планарному графу, заданному списками смежности. Какие оценки трудоемкости справедливы в этом случае?
Ответ:
(1)
(2)
(3)
(4)
Упражнение 2:
Номер 1
Ответ:
Номер 1
Алгоритм поиска в ширину применяется к планарному графу, заданному матрицей смежности. Какие оценки трудоемкости справедливы в этом случае?
Ответ:
(1)
(2)
(3)
(4)
Номер 2
Ответ:
Поиск в ширину применяется к графу. Какой будет высота BFS-дерева?
Ответ:
(1) 2
(2) 4
(3) 2 или 4
(4) 2, 3 или 4
Номер 3
Ответ:
Пусть h - высота BFS-дерева, построенного для графа G. Какие из следующих утверждений верны?
Ответ:
(1) можно выбрать стартовую вершину так, что будет
(2) h может быть больше, чем диаметр графа.
(3) можно выбрать стартовую вершину так, что будет 
(4) всегда
Упражнение 3:
Номер 1
Ответ:
Номер 1
Для некоторого графа построено BFS-дерево с корнем. Ребро графа
дереву не принадлежит. Какие из следующих соотношений могут выполняться (
обозначает расстояние между вершинами в графе)?
Ответ:
(1) 
(2) 
(3) 
(4) 
Номер 2
Ответ:
Для двудольного графа построено BFS-дерево с корнем
Ответ:
(1)
(2)
(3)
(4)
Номер 3
Ответ:
В каких из следующих случаев можно утверждать, что путь, соединяющий вершины x и y в BFS-дереве, является кратчайшим путем между ними в графе?
Ответ:
(1) x - корень дерева
(2) x и y находятся в дереве на одинаковом расстоянии от корня.
(3) x и y - любые вершины.
(4) вершина x является предком вершины y в BFS-дереве.