База ответов ИНТУИТ

Графы и алгоритмы

<<- Назад к вопросам

Поиск в ширину применяется к графу P_3  \times P_3 . Какой будет высота BFS-дерева?

(Отметьте один правильный вариант ответа.)

Варианты ответа
2
2, 3 или 4(Верный ответ)
4
2 или 4
Похожие вопросы
Поиск в глубину применяется к графу K_2  \times O_4 . Какова будет высота DFS-дерева?
Какое наименьшее число ребер нужно удалить из графа P_3  \times P_3 , чтобы превратить его в хордальный?
Дан граф G с множеством ребер E. Для каких из перечисленных ниже семейств \Phi подмножеств множества E пара (E,\Phi ) является матроидом для любого графа G?
Дан граф G с множеством вершин V, \Phi - семейство всех независимых множеств вершин этого графа (пустое множество тоже считается независимым). В каких из перечисленных ниже случаев пара (V,\Phi ) является матроидом,?
Пусть (E,\Phi ) - матроид и на множестве E задана весовая функция w с вещественными значениями. Что произойдет, если к нему применить алгоритм СПО, в котором на первом этапе элементы множества E упорядочиваются не по убыванию, а по возрастанию весов?
Какие из следующих графов изоморфны графу\overline {C_5 }?
В дереве имеется ровно три листа a,b,c, причем d(a,b) = 8, d(a,c) = 9, d(b,c) = 5. Сколько всего вершин в этом дереве?
Пусть e_1 и e_2 - ребра с наименьшими весами в некотором взвешенном графе, причем w(e_1 ) \le w(e_2 ). Какие из следующих утверждений верны для любого графа и любой весовой функции?
Дано непустое конечное множество E и семейство его подмножеств \Phi . В каких из перечисленных ниже случаев пара (E,\Phi ) является матроидом?
Сколько различных абстрактных двудольных графов можно получить, добавляя одно ребро к графу C_{12}?