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