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

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

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

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

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

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