Главная /
Графы и алгоритмы /
Для некоторого графа с заданным в нем паросочетанием построено дерево достижимости T с корнем в свободной вершине a. Какие из следующих утверждений верны для любого графа, любого паросочетания и любого дерева достижимости?
Для некоторого графа с заданным в нем паросочетанием построено дерево достижимости T
с корнем в свободной вершине a
. Какие из следующих утверждений верны для любого графа, любого паросочетания и любого дерева достижимости?
вопрос
Правильный ответ:
если дерево
T
содержит свободную вершину, отличную от a
, то в графе имеется увеличивающий путь относительно данного паросочетания
если в дереве
T
нет свободных вершин, отличных от a
, то в графе нет увеличивающих путей относительно данного паросочетания
если в дереве
T
нет свободных вершин, отличных от a
, то в графе нет увеличивающих путей относительно данного паросочетания, начинающихся в вершине a
любое дерево достижимости с корнем
a
, построенное для данного паросочетания, имеет то же множество вершин, что и дерево T
Сложность вопроса
50
Сложность курса: Графы и алгоритмы
70
Оценить вопрос
Комментарии:
Аноним
Какой человек находит эти вопросы с интуитом? Это же совсем для даунов
13 дек 2019
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.
- # Сколько имеется абстрактных обыкновенных графов с 4 вершинами и 3 ребрами?
- # Каркасы, построенные для некоторого графа с помощью алгоритмов Прима, Крускала и Дейкстры, имеют соответственно веса a, b и c. Какое из следующих соотношений обязательно выполняются для этих чисел?
- # Какова будет суммарная длина фундаментальных циклов относительно каркаса, построенного с помощью поиска в ширину для графа K7 ?
- # Какие из следующих равенств выполняются для любых графов G1 и G2?
- # Сколько листьев будет в дереве подзадач для задачи о независимом множестве, построенном для графа 3K3?