Главная /
Графы и алгоритмы /
Для некоторого графа построено DFS-дерево и вычислены глубинные номера вершин. Какие из следующих утверждений верны?
Для некоторого графа построено DFS-дерево и вычислены глубинные номера вершин. Какие из следующих утверждений верны?
вопросПравильный ответ:
если вершина x не является листом DFS-дерева, то у нее имеется такой сын y, что
если то вершина x - предок вершины y в DFS-дереве
если вершина x - предок вершины в DFS-дереве, то
если и вершины x,y смежны в графе, то вершина x - предок вершины y в DFS-дереве
Сложность вопроса
89
Сложность курса: Графы и алгоритмы
70
Оценить вопрос
Комментарии:
Аноним
Если бы не данные подсказки - я бы не осилил c этими тестами интуит.
07 сен 2020
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.
- # Сколько имеется абстрактных обыкновенных графов с 4 вершинами и 3 ребрами?
- # Для каких из перечисленных графов задача о раскраске может быть решена с помощью одних сжатий по включению?
- # В графе с весовой функцией строится каркас с помощью алгоритма Крускала. Пусть - список всех ребер каркаса в том порядке, в каком они добавлялись при построении. Какие из следующих утверждений верны для любого графа, любой весовой функции и любого ?
- # Для двудольного графа построено DFS-дерево T с корнем a. Ребро графа (x,y) дереву не принадлежит. Какие из следующих соотношений могут выполняться (d обозначает расстояние между вершинами в дереве T)?
- # BC-дерево некоторого графа имеет радиус 2 и содержит 8 вершин, 4 из которых являются листьями. Сколько шарниров у этого графа?