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

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

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

(Ответ считается верным, если отмечены все правильные варианты ответов.)

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

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

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

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

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

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

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

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

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

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

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

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

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

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