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

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

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

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

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

если

то вершина x - предок вершины y в DFS-дереве

если вершина x не является листом DFS-дерева, то у нее имеется такой сын y, что Dnum(y) = Dnum(x) + 1

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

если вершина x - предок вершины в DFS-дереве, то Dnum(x) < Dnum(y)

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

если

и вершины x,y смежны в графе, то вершина x - предок вершины y в DFS-дереве(Верный ответ)

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

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

Для некоторого графа построено DFS-дерево T с корнем a. Ребро графа (x,y) дереву не принадлежит. Какие из следующих соотношений могут выполняться (d обозначает расстояние между вершинами в дереве T)?

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

Для двудольного графа построено DFS-дерево T с корнем a. Ребро графа (x,y) дереву не принадлежит. Какие из следующих соотношений могут выполняться (d обозначает расстояние между вершинами в дереве T)?

BC-дерево некоторого графа имеет радиус 2 и содержит 8 вершин, 4 из которых являются листьями. Сколько шарниров у этого графа?

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

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

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

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

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

Какие из следующих утверждений верны для системы фундаментальных циклов, построенной относительно некоторого каркаса?

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

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