Главная /
Графы и алгоритмы /
Какие из следующих утверждений верны?
Какие из следующих утверждений верны?
вопросПравильный ответ:
лист DFS-дерева не может быть шарниром графа.
если (x,y)- обратное ребро, то ни одна отличная от x и y вершина пути, соединяющего x и y в DFS-дереве, не является шарниром
если вершина x является сыном вершины y в DFS-дереве и обе эти вершины - шарниры графа, то ребро (x,y) - перешеек
если (x,y) - обратное ребро, то ни одно ребро пути, соединяющего x и y в DFS-дереве, не является перешейком
Сложность вопроса
54
Сложность курса: Графы и алгоритмы
70
Оценить вопрос
Комментарии:
Аноним
Если бы не данные решения - я бы не осилил c этими тестами интуит.
09 дек 2018
Аноним
Я провалил экзамен, почему я не углядел этот чёртов сайт с ответами по интуит до сессии
02 мар 2018
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.
- # К графу 2C5 применяется описанный в лекции 11 алгоритм решения задачи о независимом множестве со сжатием по включению. Сколько листьев будет в возникающем при этом дереве подзадач?
- # Какое наименьшее число ребер нужно добавить к графу K3,3, чтобы превратить его в хордальный?
- # Пусть - список ребер графа в порядке убывания весов. Какие из следующих утверждений верны для любого графа и любой весовой функции?
- # Каркасы, построенные для некоторого графа с помощью алгоритмов Прима, Крускала и Дейкстры, имеют соответственно веса a, b и c. Какое из следующих соотношений обязательно выполняются для этих чисел?
- # Сколько листьев будет в дереве путей, построенном для графа K4,4?