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

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

Пусть h - высота BFS-дерева, построенного для графа G. Какие из следующих утверждений верны?

(Ответ считается верным, если отмечены все правильные варианты ответов.)

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

можно выбрать стартовую вершину так, что будет h = diam(G)

(Верный ответ)

всегда $rad(G) \le h \le diam(G)$ (Верный ответ)

h может быть больше, чем диаметр графа.

можно выбрать стартовую вершину так, что будет h = rad(G)

(Верный ответ)

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

Пусть h - высота DFS-дерева, построенного для графа G. Какие из следующих утверждений верны?

Пусть $e_1 ,e_2 , \ldots ,e_m$ - список ребер графа в порядке убывания весов. Какие из следующих утверждений верны для любого графа и любой весовой функции?

Какие из следующих утверждений верны для любого взвешенного графа?

Для некоторого графа с заданным в нем паросочетанием построено дерево достижимости T с корнем в свободной вершине a. Какие из следующих утверждений верны для любого графа, любого паросочетания и любого дерева достижимости?

Для некоторого графа построено DFS-дерево и вычислены глубинные номера вершин. Какие из следующих утверждений верны?

Какие из следующих утверждений верны?