База ответов ИНТУИТ

Графы и алгоритмы

<<- Назад к вопросам

Алгоритм поиска в глубину применяется к лесу, заданному списками смежности. Какие оценки трудоемкости справедливы в этом случае?

(Ответ считается верным, если отмечены все правильные варианты ответов.)
Варианты ответа
O(n)(Верный ответ)
O(m)
O(m+n)(Верный ответ)
O(mn)
Похожие вопросы
Алгоритм поиска в глубину применяется к планарному графу, заданному списками смежности. Какие оценки трудоемкости справедливы в этом случае?
Алгоритм поиска в глубину применяется к планарному графу, заданному матрицей смежности. Какие оценки трудоемкости справедливы в этом случае?
Алгоритм поиска в ширину применяется к дереву, заданному списками смежности. Какие оценки трудоемкости справедливы в этом случае?
Алгоритм поиска в ширину применяется к планарному графу, заданному списками смежности. Какие оценки трудоемкости справедливы в этом случае?
Алгоритм поиска в ширину применяется к планарному графу, заданному матрицей смежности. Какие оценки трудоемкости справедливы в этом случае?
К графу 2C5 применяется описанный в лекции 11 алгоритм решения задачи о независимом множестве со сжатием по включению. Сколько листьев будет в возникающем при этом дереве подзадач?
Какова будет наибольшая из длин фундаментальных циклов относительно каркаса, построенного с помощью поиска в глубину для графа K3,5?
Поиск в глубину применяется к графу K_2 \times O_4 . Какова будет высота DFS-дерева?
Граф G имеет 4 вершины, а в его матрице смежности 8 единиц. Граф H имеет 5 вершин, а в его матрице смежности 12 единиц. Сколько единиц будет в матрице смежности графа G \circ H ?
Какие из следующих утверждений справедливы для любого двусвязного графа?