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

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

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

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

если в дереве T нет свободных вершин, отличных от a, то в графе нет увеличивающих путей относительно данного паросочетания

если дерево T содержит свободную вершину, отличную от a, то в графе имеется увеличивающий путь относительно данного паросочетания(Верный ответ)

любое дерево достижимости с корнем a, построенное для данного паросочетания, имеет то же множество вершин, что и дерево T

если в дереве T нет свободных вершин, отличных от a, то в графе нет увеличивающих путей относительно данного паросочетания, начинающихся в вершине a

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

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

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

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

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

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

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

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

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

и любого его подграфа

В графе с весовой функцией

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

В графе с весовой функцией

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