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

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

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

(Отметьте один правильный вариант ответа.)

Варианты ответа

(Верный ответ)

Похожие вопросы

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

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

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

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

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

К графу 2C₅ применяется описанный в лекции 11 алгоритм решения задачи о независимом множестве со сжатием по включению. Сколько листьев будет в возникающем при этом дереве подзадач?

Поиск в глубину применяется к графу $K_2 \times O_4$ . Какова будет высота DFS-дерева?

Что произойдет, если описанный в лекции 8 алгоритм построения эйлерова цикла применить к графу P_n(без предварительной проверки четности степеней)?

Какова будет наибольшая из длин фундаментальных циклов относительно каркаса, построенного с помощью поиска в глубину для графа K_3,5?

Поиск в ширину применяется к графу $P_3 \times P_3$ . Какой будет высота BFS-дерева?