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

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

вопрос

Правильный ответ:

если дерево T содержит свободную вершину, отличную от a, то в графе имеется увеличивающий путь относительно данного паросочетания
если в дереве T нет свободных вершин, отличных от a, то в графе нет увеличивающих путей относительно данного паросочетания
если в дереве T нет свободных вершин, отличных от a, то в графе нет увеличивающих путей относительно данного паросочетания, начинающихся в вершине a
любое дерево достижимости с корнем a, построенное для данного паросочетания, имеет то же множество вершин, что и дерево T
Сложность вопроса
50
Сложность курса: Графы и алгоритмы
70
Оценить вопрос
Очень сложно
Сложно
Средне
Легко
Очень легко
Комментарии:
Аноним
Какой человек находит эти вопросы с интуитом? Это же совсем для даунов
13 дек 2019
Оставить комментарий
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.