Главная /
Графы и алгоритмы /
Для двудольного графа с заданным в нем паросочетанием построено дерево достижимости T с корнем в свободной вершине a. Какие из следующих утверждений верны?
Для двудольного графа с заданным в нем паросочетанием построено дерево достижимости T с корнем в свободной вершине a. Какие из следующих утверждений верны?
вопрос
Правильный ответ:
если дерево
T содержит свободную вершину, отличную от a, то в графе имеется увеличивающий путь относительно данного паросочетания
если в дереве
T нет свободных вершин, отличных от a, то в графе нет увеличивающих путей относительно данного паросочетания
если в дереве
T нет свободных вершин, отличных от a, то в графе нет увеличивающих путей относительно данного паросочетания, начинающихся в вершине a
любое дерево достижимости с корнем
a, построенное для данного паросочетания, имеет то же множество вершин, что и дерево T Сложность вопроса
66
Сложность курса: Графы и алгоритмы
70
Оценить вопрос
Комментарии:
Аноним
Какой человек ищет данные тесты с интуитом? Это же элементарно (я не ботан)
18 дек 2017
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.
- # Сколько листьев будет в дереве вариантов при применении описанного в лекции 10 переборного алгоритма раскраски вершин к графу C4 ?
- # В графе K7 все ребра некоторого гамильтонова цикла имеют вес 2, а все остальные ребра - вес 5. Каков будет степень корня у дерева, построенного для этого графа с помощью алгоритма Дейкстры?
-
#
Сколько различных абстрактных двудольных графов можно получить, добавляя одно ребро к графу
![math]()
?
- # Какие из следующих графов планарны?
- # Сколько максимальных независимых множеств имеется у графа P5?
?