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

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

Поиск в глубину применяется к графу $K_2 \times O_4$ . Какова будет высота DFS-дерева?

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

Варианты ответа

2, 3 или 4(Верный ответ)

2 или 4

Похожие вопросы

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

Дан граф

с множеством ребер

. Для каких из перечисленных ниже семейств $\Phi$ подмножеств множества

пара $(E,\Phi )$ является матроидом для любого графа

Дан граф

с множеством вершин

, $\Phi$ - семейство всех независимых множеств вершин этого графа (пустое множество тоже считается независимым). В каких из перечисленных ниже случаев пара $(V,\Phi )$ является матроидом,?

Пусть $(E,\Phi )$ - матроид и на множестве

задана весовая функция

с вещественными значениями. Что произойдет, если к нему применить алгоритм СПО, в котором на первом этапе элементы множества

упорядочиваются не по убыванию, а по возрастанию весов?

Какие из следующих графов изоморфны графу $\overline {C_5 }$ ?

В дереве имеется ровно три листа a,b,c

, причем

. Сколько всего вершин в этом дереве?

Пусть

- ребра с наименьшими весами в некотором взвешенном графе, причем $w(e_1 ) \le w(e_2 )$ . Какие из следующих утверждений верны для любого графа и любой весовой функции?

Дано непустое конечное множество

и семейство его подмножеств $\Phi$ . В каких из перечисленных ниже случаев пара $(E,\Phi )$ является матроидом?

Сколько различных абстрактных двудольных графов можно получить, добавляя одно ребро к графу $C_{12}$ ?

Для некоторого графа построено BFS-дерево с корнем

. Ребро графа (x,y)

дереву не принадлежит. Какие из следующих соотношений могут выполняться (

обозначает расстояние между вершинами в графе)?

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

Поиск в глубину применяется к графу . Какова будет высота DFS-дерева?

Поиск в глубину применяется к графу $K_2 \times O_4$ . Какова будет высота DFS-дерева?